Research report

The no-wait job shop with regular objective : a method based on optimal job insertion

    01.07.2015

33

English The no-wait job shop problem (NWJS-R) 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 prescribed. Also, sequence-dependent set-up times between consecutive operations on a machine can be present. The problem consists in finding a schedule that minimizes a general regular objective function. We study the so-called optimal job insertion problem in the NWJS-R and prove that this problem is solvable in polynomial time by a very efficient algorithm, generalizing a result we obtained in the case of a makespan objective. We then propose a large neighborhood local search method for the NWJS-R based on the optimal job insertion algorithm and present extensive numerical results that compare favorably with current benchmarks when available.
Collections
Faculty
Faculté des sciences et de médecine
Department
Département d'informatique
Language
  • English
Classification
Computer science
Series statement
  • Internal working papers DIUF ; 15-02
License
License undefined
Identifiers
  • RERO DOC 260775
  • RERO R008437023
Persistent URL
https://folia.unifr.ch/unifr/documents/304920
Statistics

Document views: 13 File downloads:
  • IWP15_02_diuf.pdf: 1