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

What is it about?

Constructive heuristics for shop scheduling problems are often based on priority 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 setup times. For each job a specific technological route and a release date are given. Moreover, the jobs are partitioned into groups. We use both regular and nonregular optimization criteria. For such problems we apply insertion techniques combined with beam search. 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.

Featured Image