In this paper we consider the total completion time minimization in a job-shop. We propose a new mathematical formulation based on a strip packing model. This formulation is enhanced by introducing some valid inequalities in order to compute an efficient lower bound. It is also exploited to derive an exact method; branch-and-bound algorithm which uses an improved solution of a genetic algorithm. The proposed algorithms are tested on standard benchmarks and the results are satisfactory in term of solution quality and the distance to the optimal solution.
Job Shop; Total completion time; Scheduling problem; Mixed Integer Programming; Strip Packing.
Yacine BENZIANI, Imed KACEM, Pierre LAROCHE, Anass NAGIH, "Exact and Heuristic Methods for Minimizing the Total Completion Time in Job-shops", Studies in Informatics and Control, ISSN 1220-1766, vol. 23(1), pp. 31-40, 2014. https://doi.org/10.24846/v23i1y201404
All articles published by Studies in Informatics and Control (SIC) are published in accordance with the terms and conditions of the Creative Commons Attribution License (CC BY-NC-SA 4.0).