Groupe d’études et de recherche en analyse des décisions

G-2016-34

A neighborhood for complex job shop scheduling problems with regular objective

Due to the limited applicability of the classical job shop scheduling problem in practice, many researchers have been addressing more complex versions of this problem by including additional process features such as time lags, setup times, and buffer limitations and pursuing objectives that are more relevant in practice than the makespan such as total flow time and total weighted tardiness. However, most 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 to a large class of job shop scheduling problems with regular objective. Feasible neighbors are generated by extracting a job from a given solution and reinserting it in a neighbor position. This neighbor generation extends the simple swapping of critical arcs in some sense, a mechanism widely used in the classical job shop but not applicable in more complex job shop problems. The neighborhood is used in a tabu search, and its performance is evaluated with an extensive experimental study using three well-known job shop scheduling problems, the (classical) job shop, the job shop with sequence-dependent setup times, and the blocking job shop, 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.

, 32 pages