Back
Fulltext
Journal article

Optimal job insertion in the no-wait job shop

csal

  • Bürgy, Reinhard Department of Informatics, University of Fribourg, Boulevard de Pérolles 90, 1700, Fribourg, Switzerland
  • Gröflin, Heinz Department of Informatics, University of Fribourg, Boulevard de Pérolles 90, 1700, Fribourg, Switzerland
    2013
Published in:
  • Journal of Combinatorial Optimization. - Springer US; http://www.springer-ny.com. - 2013, vol. 26, no. 2, p. 345-371
English The no-wait job shop (NWJS) considered here is a version of the job shop scheduling problem where, for any two operations of a job, a fixed time lag between their starting times is given. Also, sequence-dependent set-up times between consecutive operations on a machine can be present. The NWJS problem consists in finding a schedule that minimizes the makespan. We address here the so-called optimal job insertion problem (OJI) in the NWJS. While the OJI is NP-hard in the classical job shop, it was shown by Gröflin & Klinkert to be solvable in polynomial time in the NWJS. We present a highly efficient algorithm with running time $\mathcal {O}(n^{2}\cdot\max\{n,m\})$ for this problem. The algorithm is based on a compact formulation of the NWJS problem and a characterization of all feasible insertions as the stable sets (of prescribed cardinality) in a derived comparability graph. As an application of our algorithm, we propose a heuristic for the NWJS problem based on optimal job insertion and present numerical results that compare favorably with current benchmarks
Collections
Language
  • English
Classification
Computer science and technology
License
License undefined
Springer Science+Business Media, LLC, 2012
Identifiers
Persistent URL
https://sonar.ch/global/documents/306766
Statistics
Document views: 31 File downloads:
  • Fulltext: 0