\input zb-basic
\input zb-ioport
\iteman{io-port 05950650}
\itemau{Gr\"oflin, Heinz; Pham, Dinh Nguyen; B\"urgy, Reinhard}
\itemti{The flexible blocking job shop with transfer and set-up times.}
\itemso{J. Comb. Optim. 22, No. 2, 121-144 (2011).}
\itemab
Summary: 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 operation 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 disjunctive 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 flexibility, based on earlier work of Gr\"oflin 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.
\itemrv{~}
\itemcc{}
\itemut{job shop scheduling; flexible machines; blocking; setup; disjunctive graph; tabu search}
\itemli{doi:10.1007/s10878-009-9278-x}
\end