An efficient algorithm for operation insertion in a multi-resource job-shop schedule with sequence-dependent setup times
Authors:
- Christian ArtiguesCAChristian Artigues
- Ois RoubellatOROis Roubellat
- 1 January 2002
- journal article
- research article
- Published by Taylor & Francis in Production Planning & Control
- Vol. 13 (2) , 175-186
Abstract
Insertion of an operation inside an existing schedule is the central part of some neighbourhood search methods for off-line job-shop scheduling. It is also a basic tool to integrate unexpected jobs during on-line scheduling. In this paper is presented a new polynomial insertion algorithm of an operation inside a multi-resource job-shop schedule with sequence-dependent setup times. The considered objective is maximum lateness minimization. The algorithm is first described for the classical job-shop scheduling problem. Then, multi-resource requirements are introduced for the operations. Last, sequence-dependent setup times are considered in the multi-resource context. It is shown in the three cases that some dominance properties make the proposed insertion algorithm superior to the enumeration algorithms that can be used alternatively.Keywords
This publication has 8 references indexed in Scilit:
- A polynomial activity insertion algorithm in a multi-resource schedule with cumulative constraints and multiple modesEuropean Journal of Operational Research, 2000
- On the application of insertion techniques for job shop problems with setup timesRAIRO - Operations Research, 1999
- Multi-resource shop scheduling with resource flexibilityEuropean Journal of Operational Research, 1998
- A branch & bound method for the general-shop problem with sequence dependent setup-timesOR Spectrum, 1996
- A new method for workshop real time schedulingInternational Journal of Production Research, 1996
- Impact of sequence-dependent setup time on job shop scheduling performanceInternational Journal of Production Research, 1994
- Exploiting shop floor status information to schedule complex job shopsJournal of Manufacturing Systems, 1994
- n jobs and m machines job-shop problems with sequence-dependent set-up timesInternational Journal of Production Research, 1982