| Publikationstyp: | Beitrag in wissenschaftlicher Zeitschrift |
| Art der Begutachtung: | Peer review (Publikation) |
| Titel: | Feasible Job Insertions in the Multi-Processor-Task Job Shop |
| Autor/-in: | Gröflin, Heinz Klinkert, Andreas Pham Dinh, Nguyen |
| DOI: | 10.1016/j.ejor.2005.10.077 |
| Erschienen in: | European Journal of Operational Research |
| Band(Heft): | 185 |
| Heft: | 3 |
| Seite(n): | 1308 |
| Seiten bis: | 1318 |
| Erscheinungsdatum: | 2008 |
| Verlag / Hrsg. Institution: | Elsevier |
| ISSN: | 0377-2217 |
| Sprache: | Englisch |
| Schlagwörter: | Insertion; Scheduling; Job shop; Multi-processor |
| Fachgebiet (DDC): | 510: Mathematik |
| Zusammenfassung: | 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 |
| 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:
Es gibt keine Dateien zu dieser Ressource.
Zur Langanzeige
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.
Alle Ressourcen in diesem Repository sind urheberrechtlich geschützt, soweit nicht anderweitig angezeigt.