From fluid relaxations to practical algorithms for job shop scheduling: the makespan objective

• Published in: Mathematical programming 2002-03, Vol.92 (1), p.61-102
• Main Authors: Bertsimas, Dimitris, Sethuraman, Jay
• Format: Article
• Language: English
• Subjects: Algorithms; Bottlenecks; Digital Object Identifier; Employment; Heuristic; Job shops; Linear programming; Operations research; Scheduling
• ISSN: 0025-5610; 1436-4646
• DOI: 10.1007/s101070100272

We design an algorithm, called the fluid synchronization algorithm (FSA), for the job shop scheduling problem with the objective of minimizing the makespan. We round an optimal solution to a fluid relaxation, in which we replace discrete jobs with the flow of a continuous fluid, and use ideas from fair queueing in the area of communication networks in order to ensure that the discrete schedule is close to the one implied by the fluid relaxation. FSA produces a schedule with makespan at most Cmax+(I+2)PmaxJmax, where Cmax is the lower bound provided by the fluid relaxation, I is the number of distinct job types, Jmax is the maximum number of stages of any job-type, and Pmax is the maximum processing time over all tasks. We report computational results based on all benchmark instances chosen from the OR library when N jobs from each job-type are present. The results suggest that FSA has a relative error of about 10% for N=10, 1% for N=100, 0.01% for N=1000. In comparison to eight different dispatch rules that have similar running times as FSA, FSA clearly dominates them. In comparison to the shifting bottleneck heuristic whose running time and memory requirements are several orders of magnitude larger than FSA, the shifting bottleneck heuristic produces better schedules for small N (up to 10), but fails to provide a solution for larger values of N.