A fluid heuristic for minimizing makespan in job shops

We describe a single 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 busy at almost all times, while the other machines are paced by the bottleneck machine. We perform 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 ≥ 1, where c is some constant independent of N.