On the application of insertion techniques for job shop problems with setup times

Abstract

Constructive heuristics for shop scheduling problems are often based onpriority (or dispatching) rules. However, recent work has demonstratedthat 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 withsetup times. For each job a specific technological route and a releasedate are given. Moreover, the jobs are partitioned into groups. Asequence 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 techniquescombined with beam search. Especially we consider different insertion orders of the operations or jobs. A refined variant of the insertion algorithmis 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 onpriority rules.