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 and technology
- 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: 50
File downloads:
- IWP15_02_diuf.pdf: 133