From Fluid Relaxations to Practical Algorithms for High-Multiplicity Job-Shop Scheduling: The Holding Cost Objective

• Published in: Operations research 2003-09, Vol.51 (5), p.798-813
• Main Authors: Bertsimas, Dimitris, Gamarnik, David, Sethuraman, Jay
• Format: Article
• Language: English
• Subjects: Algorithms; Analysis; Carrying costs; Cost efficiency; Error rates; Heuristic methods; Heuristics; Job shops; Machine shops; Optimal solutions; Production scheduling; Production/scheduling, deterministic: approximation algorithms for deterministic job shops; Queueing networks; Queues optimization: asymptotically optimal solutions to queueing networks; Queuing; Scheduling; Scheduling (Management); Studies; Technology application
• ISSN: 0030-364X; 1526-5463
• DOI: 10.1287/opre.51.5.798.16748

We design an algorithm for the high-multiplicity job-shop scheduling problem with the objective of minimizing the total holding cost by appropriately rounding an optimal solution to a fluid relaxation in which we replace discrete jobs with the flow of a continuous fluid. The algorithm solves the fluid relaxation optimally and then aims to keep the schedule in the discrete network close to the schedule given by the fluid relaxation. If the number of jobs from each type grow linearly with N , then the algorithm is within an additive factor O ( N ) from the optimal (which scales as O ( N 2 )); thus, it is asymptotically optimal. We report computational results on benchmark instances chosen from the OR library comparing the performance of the proposed algorithm and several commonly used heuristic methods. These results suggest that for problems of moderate to high multiplicity, the proposed algorithm outperforms these methods, and for very high multiplicity the overperformance is dramatic. For problems of low to moderate multiplicity, however, the relative errors of the heuristic methods are comparable to those of the proposed algorithm, and the best of these methods performs better overall than the proposed method.