Wednesday , June 20 2018

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

LCOMS EA 7306, Université de Lorraine
Ile du Saulcy, Metz, 57000, France
{yacine.benziani, imed.kacem, pierre.laroche, anass.nagih}

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

  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 Oij 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.


  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.
  1. ROY, B., B. SUSSMANN, Les Problèmes d’Ordonnancement avec Contraintes Disjonctives, Note ds, vol. 9, 1964.
  2. CARLIER, J., E. PINSON, An Algorithm for Solving the Job-Shop Problem. Management Science, vol. 35, no. 2, 1989, pp. 164-176.
  3. APPLEGATE, D., W. COOK, A Computational Study of the Job-Shop Scheduling Problem, ORSA Journal on Computing, vol. 3(2), 1991, pp. 149-156.
  4. MARTIN, P., D. B. SHMOYS, A New Approach to Computing Optimal Schedules for the Job-Shop Scheduling Problem, In Integer Programming and Combinatorial Optimization, Springer Berlin Heidelberg, 1996, pp. 389-403.
  5. MARTIN, P. D., A Time-Oriented Approach to Computing Optimal Schedules for the Job-Shop     Scheduling Problem, Cornell University, Ithaca, NY, 1996.
  6. Ben MESSAOUD, S., C. CHU, M. L. ESPINOUSE, Characterization and Modelling of Guillotine Constraints, European Journal of Operational Research, vol. 191(1), 2008, pp. 112-126.
  7. BEKRAR, A., I. KACEM, An Exact Method for the 2D Guillotine Strip Packing Problem, Advances in Operations Research, vol. 2009, Article ID 732010, 20 pages, 2009.
  8. PISINGER, D., M. SIGURD, The Two-Dimensional Bin Packing Problem with Variable Bin Sizes and Costs, Discrete Optimization vol. 2(2), 2005, pp. 154-167.
  9. FISHER, H., G. L. THOMPSON, Probabilistic Learning Combinations of Local Job-Shop Scheduling Rules, Muth, J. F., Thompson, G. L. (Eds.), Industrial Scheduling. Prentice-Hall, Englewood Cliffs, NJ, pp. 225-251.
  10. BRUCKER, P., B. JURISCH, A New Lower Bound for the Job-Shop Scheduling Problem, European Journal of Operational Research, vol. 64, no. 2, 1993, pp. 156-167.
  11. BRUCKER, P., B. JURISCH, B. SIEVERS, A Branch and Bound Algorithm for the Job-Shop Scheduling Problem, Discrete Applied Mathematics, vol. 49(1), 1994, pp. 107-127.
  12. BENZIANI, Y., I. KACEM, P. LAROCHE, A. NAGIH, Lower Bounds for the Makespan Minimization in Job Shops, In Networking, Sensing and Control (ICNSC), 10th IEEE International Conference on. IEEE, 2013, pp. 442-445.
  13. LENSTRA, J. K., A. R. KAN, P. BRUCKER, Complexity of Machine Scheduling Problems, Annals of Discrete Mathematics, vol. 1, 1977, pp. 343-362.
  14. LABETOULLE, J., E. L. LAWLER, J. K. LENSTRA, A. H. G. RINNOOY KAN, Preemptive Scheduling of Uniform Machines Subject to Release Dates, in Progress in Combinatorial Optimization, W. R. Pulleyblank, ed., Academic Press, New York, 1984, pp. 245-261.
  15. LI, Y., Y. CHEN, A Genetic Algorithm for Job-Shop Scheduling, Journal of Software, vol. 5(3), 2010, pp. 269-274.
  16. YAMADA, T., R. NAKANO, Genetic Algorithms for Job-Shop Scheduling Problems, Proceedings of Modern Heuristic for Decision Support, UNICOM seminar, 1997, pp. 67-81.
  17. GIFFLER, B., G. L. THOMPSON, Algorithms for Solving Production Scheduling Problems, Operations Research, vol. 8(4), 1960, pp. 487-503.
  18. ADAMS, J., E. BALAS, D. ZAWACK, The Shifting Bottleneck Procedure for Job Shop Scheduling, Management Science, vol. 34(3), 1988, pp. 391-401.
  19. DAVIS, L., Job Shop Scheduling with Genetic Algorithms, Proceedings of the 1st International Conference on Genetic Algorithms. 1985, pp. 136-140.
  20. LAWRENCE, S., Resource Constrained Project Scheduling: An Experimental Investigation of Heuristic Scheduling Techniques, (Supplement), PhD. Thesis Graduate School of Industrial Administration, Carnegie-Mellon University, Pittsburgh, PA, 1984.
  21. FILIP, F. G., G. NEAGU, D. A. DONCIULESCU, Job Shop Scheduling Optimization in Real-Time Production Control, Computers in Industry, vol. 4(4), 1983, pp. 395-403.