A fluid heuristic for minimizing makespan in job shops

We describe a simple online heuristic for scheduling job shops, We assume there is a fixed set of routes for the jobs, and many jobs, say N, on each route. The heuristic uses safety stocks and keeps the bottleneck machine buoy at almost all times, while the other machines are paced by the bottleneck machine. We perforin a probabilistic analysis of the heuristic, under some assumptions on the distributions, of the processing times. We show that our heuristic produces makespan, which exceeds the optimal makespan by no more than c log N with a probability that exceeds 1-1/N for all N greater than or equal to 1. where c is some constant independent of N.