Bitte benutzen Sie diese Kennung, um auf die Ressource zu verweisen:
https://doi.org/10.21256/zhaw-3528| Publikationstyp: | Beitrag in wissenschaftlicher Zeitschrift |
| Art der Begutachtung: | Peer review (Publikation) |
| Titel: | A new neighborhood and tabu search for the blocking job shop |
| Autor/-in: | Gröflin, Heinz Klinkert, Andreas |
| DOI: | 10.21256/zhaw-3528 10.1016/j.dam.2009.02.020 |
| Erschienen in: | Discrete Applied Mathematics |
| Band(Heft): | 157 |
| Heft: | 17 |
| Seite(n): | 3643 |
| Seiten bis: | 3655 |
| Erscheinungsdatum: | 2009 |
| Verlag / Hrsg. Institution: | Elsevier |
| ISSN: | 0166-218X 1872-6771 |
| Sprache: | Englisch |
| Schlagwörter: | Tabu search; Blocking; Job shop scheduling; Neighborhood |
| Fachgebiet (DDC): | 500: Naturwissenschaften |
| Zusammenfassung: | 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 |
| Volltext Version: | Publizierte Version |
| Lizenz (gemäss Verlagsvertrag): | Lizenz gemäss Verlagsvertrag |
| Departement: | School of Engineering |
| Organisationseinheit: | Institut für Datenanalyse und Prozessdesign (IDP) |
| Enthalten in den Sammlungen: | Publikationen School of Engineering |
Dateien zu dieser Ressource:
| Datei | Beschreibung | Größe | Format | |
|---|---|---|---|---|
| Groeflin-Klinkert-A-New-Neighborhood-And-Tabu-Search-For-The-Blocking-Job-Shop-DAM-2009.pdf | 895.38 kB | Adobe PDF |  Öffnen/Anzeigen |
Zur Langanzeige
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.
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt, soweit nicht anderweitig angezeigt.