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 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ö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.
Article PDF
Similar content being viewed by others
Explore related subjects
Discover the latest articles, news and stories from top researchers in related subjects.Avoid common mistakes on your manuscript.
References
Brizuela C, Zhao Y, Sannomiya N (2001) No-wait and blocking job-shops: challenging problems for ga’s. In: IEEE international conference on systems, man, and cybernetics, vol 4, pp 2349–2354
Brucker P, Kampmeyer T (2008) Cyclic job shop scheduling problems with blocking. Ann Oper Res 159(1):161–181
Brucker P, Heitmann S, Hurink J, Nieberg T (2006) Job-shop scheduling with limited capacity buffers. OR Spectrum 28:151–176
Glover F, Laguna M (1997) Tabu search. Kluwer, Boston
Gröflin H, Klinkert A (2007) Feasible insertions in job shop scheduling, short cycles and stable sets. Eur J Oper Res 177:763–785
Gröflin H, Klinkert A (2009) A new neighborhood and tabu search for the blocking job shop. Discrete Appl Math 157(17):3643–3655
Heitmann S (2007) Job-shop scheduling with limited buffer capacities. PhD thesis, University Osnabrück, Germany
Klinkert A (2001) Optimization in design and control of automated high-density warehouses. PhD thesis, University of Fribourg, Switzerland
Mascis A, Pacciarelli D (2000) Machine scheduling via alternative graphs. Internal Report RT-DIA-46-2000, Università degli Studi Roma Tre, Dipartimento di Informatica e Automazione, Italy
Mascis A, Pacciarelli D (2002) Job-shop scheduling with blocking and no-wait constraints. Eur J Oper Res 143:498–517
Meloni C, Pacciarelli D, Pranzo M (2004) A rollout metaheuristic for job shop scheduling problems. Ann Oper Res 131:215–235
Nowicki E, Smutnicki C (1996) A fast taboo search algorithm for the job shop problem. Manag Sci 42:797–812
Pham DN (2008) Complex job shop scheduling: Formulations, algorithms and a healthcare application. PhD thesis, University of Fribourg, Switzerland
Thornton HW, Hunsucker JL (2004) A new heuristic for minimal makespan in flow shops with multiple processors and no intermediate storage. Eur J Oper Res 152:96–114
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Gröflin, H., Pham, D.N. & Bürgy, R. The flexible blocking job shop with transfer and set-up times. J Comb Optim 22, 121–144 (2011). https://doi.org/10.1007/s10878-009-9278-x
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10878-009-9278-x