Title: Feasible Job Insertions in the Multi-Processor-Task Job Shop
Authors : Gröflin, Heinz
Klinkert, Andreas
Pham Dinh, Nguyen
Published in : European Journal of Operational Research
Volume(Issue) : 185
Issue : 3
Pages : 1308
Pages to: 1318
Publisher / Ed. Institution : Elsevier
Issue Date: 2008
License (according to publishing contract) : Licence according to publishing contract
Type of review: Peer review (Publication)
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.
Departement: School of Engineering
Organisational Unit: Institute of Data Analysis and Process Design (IDP)
Publication type: Article in scientific Journal
DOI : 10.1016/j.ejor.2005.10.077
ISSN: 0377-2217
URI: https://digitalcollection.zhaw.ch/handle/11475/3614
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.