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

1. Introduction

The job shop scheduling problem consists in organizing a set I of n jobs to be processed on a set M of m machines. A job I is a set of μ_j operations O_ij to be processed on machines without interruption in a predetermined order. The aim is to minimize the sum of the completion times of the last job operations.

The job shop scheduling problem (JSS) is NP-hard even for three machines [1]. It has been widely studied, in particular to minimize the makespan. The first formulation leading to an exact method for the job shop problem was due to Roy and Sussmann [2]. This formulation is based on the disjunctive programming model and the well-known disjunctive graph representation. Carlier and Pinson [3] used this formulation and develop a branch-and-bound method to solve the problem. They used also the one-machine relaxation to obtain a lower bound. The disjunctive programming model can be turned into a mixed integer problem by introducing a binary variable. This new model was used by Applegate and Cook [4]. They used both the disjunctive and mixed integer formulation and applied a cutting plane approach to obtain an initial solution of the problem by solving the relaxed problem, and then they added valid inequalities by dropping the disjunctive constraints and relaxing the binary variables. Another way to model the job shop is the packing formulation which is a model for the job shop feasibility problem. It consists to say “Does there exist a set of job schedules such that no two schedules require the same machine at the same time” where the job schedule is an assignment of operation starting times of one job such that no operation starts before the ending of its predecessors. Martin and Shmoys [5] used this formulation to introduce a lower bound based on the fractional packing. The last model is based on the time oriented approach. It was used by Martin [6] and Martin and Shmoys [5] to develop a branch-and-bound algorithm to solve the problem.

In this paper, a new mixed integer programming (MIP) formulation of the job shop is proposed, and some new inequalities are added to obtain a better lower bound. Moreover, two genetic algorithms are tested, and finally the lower bound and the upper bound are used both to improve a branch-and-bound algorithm used to solve optimally the problem. Finally, the numerical experiments and the obtained results are presented and discussed.

REFERENCES

1. GAREY, M. R., D. S. JOHNSON, R. SETHI, The Complexity of Flowshop and Jobshop Scheduling, Mathematics of Operations Research, vol. 1, issue 2, 1976, pp. 117-129.