Exact and Heuristic Methods for Minimizing the Total Completion Time in Job-shops

Yacine BENZIANI, Imed KACEM, Pierre LAROCHE, Anass NAGIH
LCOMS EA 7306, Université de Lorraine
Ile du Saulcy, Metz, 57000, France
{yacine.benziani, imed.kacem, pierre.laroche, anass.nagih}@univ-lorraine.fr

Abstract: 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.

Keywords: Job Shop; Total completion time; Scheduling problem; Mixed Integer Programming; Strip Packing.

>>Full text
CITE THIS PAPER AS:
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