| 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.