Back
Document
Journal article

A Neighborhood for Complex Job Shop Scheduling Problems with Regular Objectives

  • Bürgy, Reinhard GERAD & Department of Mathematics and Industrial Engineering, Polytechnique Montréal
    2017
Published in:
  • Journal of Scheduling. - Springer. - 2017, vol. 20, p. 391-422
job shop scheduling
general regular objective
sequence-dependent setup times
blocking job shop
job insertion
neighborhood
tabu search
English Due to the limited applicability in practice of the classical job shop scheduling problem, many researchers have addressed more complex versions of this problem by including additional process features, such as time lags, setup times, and buffer limitations, and have pursued objectives that are more practically relevant than the makespan, such as total flow time and total weighted tardiness. However, most proposed solution approaches are tailored to the specific scheduling problem studied and are not applicable to more general settings. This article proposes a neighborhood that can be applied for a large class of job shop scheduling problems with regular objectives. Feasible neighbor solutions are generated by extracting a job from a given solution and reinserting it into a neighbor position. This neighbor generation in a sense extends the simple swapping of critical arcs, a mechanism that is widely used in the classical job shop but that is not applicable in more complex job shop problems. The neighborhood is embedded in a tabu search, and its performance is evaluated with an extensive experimental study using three standard job shop scheduling problems: the (classical) job shop, the job shop with sequence-dependent setup times, and the blocking job shop, combined with the following five regular objectives: makespan, total flow time, total squared flow time, total tardiness, and total weighted tardiness. The obtained results support the validity of the approach.
Faculty
Faculté des sciences économiques et sociales et du management
Department
Département d'informatique
Language
  • English
Classification
Computer science and technology
License
License undefined
Identifiers
Persistent URL
https://folia.unifr.ch/unifr/documents/309282
Statistics
Document views: 14 File downloads:
  • 2017_Buergy_Neighborhood.pdf: 50