Zurück zu den Preprints des Jahres 1996


1996-04

On the Application of Insertion Techniques for Job Shop Poblems with Setup Times

by Sotskov, Yu. N., Tautenhahn, T., Werner, F..


Series: 1996-04, Preprints

MSC:
90B35 Scheduling theory, deterministic

Abstract:
Constructive heuristics for shop scheduling problems are often based on priority (or
dispatching) rules. However, recent work has demonstrated that insertion algorithms that
step by step insert operations or jobs into partial schedules usually clearly outperform
priority rules. In this paper, we consider various job shop scheduling problems with batch
setup 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 rj
is required on machine j when a job of the r-th group is processed after a job of another
group. 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 we
apply insertion techniques combined with beam search. Especially we consider different
insertion orders of the operations or jobs. A refined variant of the insertion algorithm is
presented, where several operations are inserted in parallel. The proposed variants have
been tested on a large collection of test problems and compared with other constructive
algorithms based on priority rules.

Keywords:
Job Shop Scheduling, Setup Times, Constructive Heuristics1 Supported by INTAS (Project 93-257) and by Deutsche Forschungsgemeinschaft(Project ScheMA)

This paper was published in:
RAIRO Rech. Oper., Vol. 33, No. 2, 1999, 209 - 245.