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
Pages: 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): 500: Natural sciences and 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.
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.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.