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

Sotskov, Yuri N., Tautenhahn, Thomas, and Werner, Frank. "On the application of insertion techniques for job shop problems with setup times ." RAIRO - Operations Research 33.2 (2010): 209-245. <http://eudml.org/doc/116594>.

@article{Sotskov2010,
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 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 Srj 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. },
author = {Sotskov, Yuri N., Tautenhahn, Thomas, Werner, Frank},
journal = {RAIRO - Operations Research},
keywords = {Job Shop scheduling; setup times; constructive heuristics. ; job shop scheduling; constructive heuristics},
language = {eng},
month = {3},
number = {2},
pages = {209-245},
publisher = {EDP Sciences},
title = {On the application of insertion techniques for job shop problems with setup times },
url = {http://eudml.org/doc/116594},
volume = {33},
year = {2010},
}

TY - JOUR
AU - Sotskov, Yuri N.
AU - Tautenhahn, Thomas
AU - Werner, Frank
TI - On the application of insertion techniques for job shop problems with setup times
JO - RAIRO - Operations Research
DA - 2010/3//
PB - EDP Sciences
VL - 33
IS - 2
SP - 209
EP - 245
AB - 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 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 Srj 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.
LA - eng
KW - Job Shop scheduling; setup times; constructive heuristics. ; job shop scheduling; constructive heuristics
UR - http://eudml.org/doc/116594
ER -