Paper Info
Title
A study on local search neighborhoods for the job shop scheduling problem with total weighted tardiness objective
Abstract
In this paper we consider the job shop scheduling problem with total weighted tardiness objective (JSPTWT). This objective reflects the goal to achieve a high service level which is of increasing importance in many branches of industry. The paper concentrates on a class of baseline heuristics for this problem, known as neighborhood search techniques. An approach based on disjunctive graphs is developed to capture the general structure of neighborhoods for the JSPTWT. Existing as well as newly designed neighborhoods are formulated and analyzed. The performance and search ability of the operators (as well as combinations thereof) are compared in a computational study. Although no dominant operator is identified, a transpose-based perturbation on multiple machines turns out as a promising choice if applied as the only operator. Combining operators improves the schedule quality only slightly. But, the implementation of operators within a meta-heuristic enables to produce a higher schedule quality. A structural classification of neighborhood operators and some new analytical results are presented as well.
Year
DOI
Venue
2016
10.1016/j.cor.2015.07.011
Computers & Operations Research
Keywords
Field
DocType
Job shop scheduling,Total weighted tardiness,Disjunctive graph model,Neighborhoods,Heuristics
Mathematical optimization,Service level,Tardiness,Job shop scheduling,Transpose,Flow shop scheduling,Heuristics,Operator (computer programming),Local search (optimization),Mathematics
Journal
Volume
Issue
ISSN
66
C
0305-0548
Citations 
PageRank 
References 
15
0.72
7
Authors
2
Name
Order
Citations
PageRank
Jens Kuhpfahl1221.50
Christian Bierwirth258638.75