《2016 The flexible blocking job shop with transfer and set-up times》.pdf

J Comb Optim (2011) 22:121–144 DOI 10.1007/s10878-009-9278-x The flexible blocking job shop with transfer and set-up times Heinz Gröflin · Dinh Nguyen Pham · Reinhard Bürgy Published online: 12 November 2009 © Springer Science+Business Media, LLC 2009 Abstract The Flexible Blocking Job Shop (FBJS) considered here is a job shop scheduling problem characterized by the availability of alternative machines for each operation and the absence of buffers. The latter implies that a job, after completing an operation, has to remain on the machine until its next operation starts. Additional features are sequence-dependent transfer and set-up times, the first for passing a job from a machine to the next, the second for change-over on a machine from an op- eration to the next. The objective is to assign machines and schedule the operations in order to minimize the makespan. We give a problem formulation in a disjunc- tive graph and develop a heuristic local search approach. A feasible neighborhood is constructed, where typically a critical operation is moved (keeping or changing its machine) together with some other operations whose moves are “implied”. For this purpose, we develop the theoretical framework of job insertion with local flexibil- ity, based on earlier work of Gröflin and Klinkert on insertion. A tabu search that consistently generates feasible neighbor solutions is then proposed and tested on a larger test set. Numerical results support the validity of our approach and establish first benchmarks for the FBJS. Keywords Job shop scheduling · Flexible machines · Blocking · Setup · Disjunctive graph · Tabu search H. Gröflin ( ) · R. Bürgy Department of Informatics, University of Fribourg, Boulevard de Pérolles 90, 1700 Fribourg, Switzerland e-mail: heinz.groeflin@unifr.ch D.N. Pham FortisBC Inc, Kelown, BC V1Y 7V7, Canada 122 J Comb Optim (2011)