A new neighborhood and tabu search for the blocking job shop

Gröflin, Heinz; Klinkert, Andreas

doi:10.21256/zhaw-3528

Please use this identifier to cite or link to this item: https://doi.org/10.21256/zhaw-3528

Publication type:	Article in scientific journal
Type of review:	Peer review (publication)
Title:	A new neighborhood and tabu search for the blocking job shop
Authors:	Gröflin, Heinz Klinkert, Andreas
DOI:	10.21256/zhaw-3528 10.1016/j.dam.2009.02.020
Published in:	Discrete Applied Mathematics
Volume(Issue):	157
Issue:	17
Page(s):	3643
Pages to:	3655
Issue Date:	2009
Publisher / Ed. Institution:	Elsevier
ISSN:	0166-218X 1872-6771
Language:	English
Subjects:	Tabu search; Blocking; Job shop scheduling; Neighborhood
Subject (DDC):	500: Natural sciences
Abstract:	The Blocking Job Shop is a version of the job shop scheduling problem with no intermediate buffers, where a job has to wait on a machine until being processed on the next machine. We study a generalization of this problem which takes into account transfer operations between machines and sequence-dependent setup times. After formulating the problem in a generalized disjunctive graph, we develop a neighborhood for local search. In contrast to the classical job shop, there is no easy mechanism for generating feasible neighbor solutions. We establish two structural properties of the underlying disjunctive graph, the concept of closures and a key result on short cycles, which enable us to construct feasible neighbors by exchanging critical arcs together with some other arcs. Based on this neighborhood, we devise a tabu search algorithm and report on extensive computational experience, showing that our solutions improve most of the benchmark results found in the literature.
URI:	https://digitalcollection.zhaw.ch/handle/11475/3627
Fulltext version:	Published version
License (according to publishing contract):	Licence according to publishing contract
Departement:	School of Engineering
Organisational Unit:	Institute of Data Analysis and Process Design (IDP)
Appears in collections:	Publikationen School of Engineering

Files in This Item:

File	Description	Size	Format
Groeflin-Klinkert-A-New-Neighborhood-And-Tabu-Search-For-The-Blocking-Job-Shop-DAM-2009.pdf		895.38 kB	Adobe PDF	View/Open

Show full item record

Gröflin, H., & Klinkert, A. (2009). A new neighborhood and tabu search for the blocking job shop. Discrete Applied Mathematics, 157(17), 3643–3655. https://doi.org/10.21256/zhaw-3528

Gröflin, H. and Klinkert, A. (2009) ‘A new neighborhood and tabu search for the blocking job shop’, Discrete Applied Mathematics, 157(17), pp. 3643–3655. Available at: https://doi.org/10.21256/zhaw-3528.

H. Gröflin and A. Klinkert, “A new neighborhood and tabu search for the blocking job shop,” Discrete Applied Mathematics, vol. 157, no. 17, pp. 3643–3655, 2009, doi: 10.21256/zhaw-3528.

GRÖFLIN, Heinz und Andreas KLINKERT, 2009. A new neighborhood and tabu search for the blocking job shop. Discrete Applied Mathematics. 2009. Bd. 157, Nr. 17, S. 3643–3655. DOI 10.21256/zhaw-3528

Gröflin, Heinz, and Andreas Klinkert. 2009. “A New Neighborhood and Tabu Search for the Blocking Job Shop.” Discrete Applied Mathematics 157 (17): 3643–55. https://doi.org/10.21256/zhaw-3528.

Gröflin, Heinz, and Andreas Klinkert. “A New Neighborhood and Tabu Search for the Blocking Job Shop.” Discrete Applied Mathematics, vol. 157, no. 17, 2009, pp. 3643–55, https://doi.org/10.21256/zhaw-3528.