From fluid relaxations to practical algorithms for job shop scheduling: the makespan objective |
| |
Authors: | Dimitris Bertsimas Jay Sethuraman |
| |
Institution: | (1) Boeing Professor of Operations Research, Sloan School of Management and Operations Research Center, Massachusetts Institute of Technology, E53-363, Cambridge, MA 02139, USA, e-mail: dbertsim@mit.edu, US;(2) IEOR Department, Columbia University, New York, NY 10027, USA, e-mail: jay@ieor.columbia.edu, US |
| |
Abstract: | 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 C
max+(I+2)P
max
J
max, where C
max is the lower bound provided by the fluid relaxation, I is the number of distinct job types, J
max is the maximum number of stages of any job-type, and P
max 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.
Received: September 1999 / Accepted: September 2001?Published online March 14, 2002 |
| |
Keywords: | Mathematics Subject Classification (2000): 90B35 90C59 68M20 |
本文献已被 SpringerLink 等数据库收录! |
|