Publication type: | Article in scientific journal |
Type of review: | Peer review (publication) |
Title: | Feasible Job Insertions in the Multi-Processor-Task Job Shop |
Authors: | Gröflin, Heinz Klinkert, Andreas Pham Dinh, Nguyen |
DOI: | 10.1016/j.ejor.2005.10.077 |
Published in: | European Journal of Operational Research |
Volume(Issue): | 185 |
Issue: | 3 |
Page(s): | 1308 |
Pages to: | 1318 |
Issue Date: | 2008 |
Publisher / Ed. Institution: | Elsevier |
ISSN: | 0377-2217 |
Language: | English |
Subjects: | Insertion; Scheduling; Job shop; Multi-processor |
Subject (DDC): | 510: Mathematics |
Abstract: | The Multi-Processor-Task Job Shop is an extension of the Job Shop problem where an operation of a job requires a set of machines instead of a single machine. Job insertion is the following: given a feasible schedule of n-1 jobs, find a feasible insertion of job n into the schedule such that makespan is minimized. The problem is known to be NP-hard already for the Job Shop case. In this note, a polyhedral description of all feasible insertions is derived, settling an open problem recently proposed by Kis and Hertz. Constrained feasible insertions, satisfying additional constraints, are introduced and a feasibility theorem is established. A lower bound on the job insertion problem is derived and computed by repeatedly invoking the feasibility theorem. Numerical results show high quality of the bounds and short computation times. |
URI: | https://digitalcollection.zhaw.ch/handle/11475/3614 |
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:
There are no files associated with this item.
Show full item record
Gröflin, H., Klinkert, A., & Pham Dinh, N. (2008). Feasible Job Insertions in the Multi-Processor-Task Job Shop. European Journal of Operational Research, 185(3), 1308–1318. https://doi.org/10.1016/j.ejor.2005.10.077
Gröflin, H., Klinkert, A. and Pham Dinh, N. (2008) ‘Feasible Job Insertions in the Multi-Processor-Task Job Shop’, European Journal of Operational Research, 185(3), pp. 1308–1318. Available at: https://doi.org/10.1016/j.ejor.2005.10.077.
H. Gröflin, A. Klinkert, and N. Pham Dinh, “Feasible Job Insertions in the Multi-Processor-Task Job Shop,” European Journal of Operational Research, vol. 185, no. 3, pp. 1308–1318, 2008, doi: 10.1016/j.ejor.2005.10.077.
GRÖFLIN, Heinz, Andreas KLINKERT und Nguyen PHAM DINH, 2008. Feasible Job Insertions in the Multi-Processor-Task Job Shop. European Journal of Operational Research. 2008. Bd. 185, Nr. 3, S. 1308–1318. DOI 10.1016/j.ejor.2005.10.077
Gröflin, Heinz, Andreas Klinkert, and Nguyen Pham Dinh. 2008. “Feasible Job Insertions in the Multi-Processor-Task Job Shop.” European Journal of Operational Research 185 (3): 1308–18. https://doi.org/10.1016/j.ejor.2005.10.077.
Gröflin, Heinz, et al. “Feasible Job Insertions in the Multi-Processor-Task Job Shop.” European Journal of Operational Research, vol. 185, no. 3, 2008, pp. 1308–18, https://doi.org/10.1016/j.ejor.2005.10.077.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.