96-04
On the Application of Insertion Techniques for Job Shop Poblems with Setup Times
by Sotskov, Yu. N.; Tautenhahn, T.; Werner, F.
Preprint series: 96-04, Preprints
The paper is published: RAIRO Rech. Oper., Vol. 33, No. 2, 1999, 209 - 245.
Abstract: Constructive heuristics for shop scheduling problems are often based on priority (or dispatching) rules. However, recent work has demonstrated that insertion algorithms thatstep by step insert operations or jobs into partial schedules usually clearly outperformpriority rules. In this paper, we consider various job shop scheduling problems with batchsetup times. For each job a specific technological route and a release date are given.Moreover, the jobs are partitioned into groups. A sequence independent setup time s rjis required on machine j when a job of the r-th group is processed after a job of anothergroup. We consider different types of job availability, namely item and batch availability.As objective function we use both regular and nonregular criteria. For such problems weapply insertion techniques combined with beam search. Especially we consider differentinsertion orders of the operations or jobs. A refined variant of the insertion algorithm ispresented, where several operations are inserted in parallel. The proposed variants havebeen tested on a large collection of test problems and compared with other constructivealgorithms based on priority rules.
Keywords: Job Shop Scheduling, Setup Times, Constructive Heuristics1 Supported by INTAS (Project 93-257) and by Deutsche Forschungsgemeinschaft(Project ScheMA)
The author(s) agree, that this abstract may be stored asfull text and distributed as such by abstracting services.