From Fluid Relaxations to Practical Algorithms for Job Shop Scheduling: the Holding Cost Objective

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 in $N$. 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 more 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 overall better than the proposed method.