Title: Feasible insertions in job shop scheduling, short cycles and stable sets
Authors : Gröflin, Heinz
Klinkert, Andreas
Published in : European Journal of Operational Research
Volume(Issue) : 177
Issue : 2
Pages : 763
Pages to: 785
Publisher / Ed. Institution : Elsevier
Issue Date: 2007
License (according to publishing contract) : Licence according to publishing contract
Type of review: Peer review (Publication)
Language : English
Subjects : Insertion; Scheduling; Job shop
Subject (DDC) : 500: Natural sciences and mathematics
Abstract: Insertion problems arise in scheduling when additional activities have to be inserted into a given schedule. This paper investigates insertion problems in a general disjunctive scheduling framework capturing a variety of job shop scheduling problems and insertion types. First, a class of scheduling problems is introduced, characterized by disjunctive graphs with the so-called short cycle property, and it is shown that in such problems, the feasible selections correspond to the stable sets of maximum cardinality in an associated conflict graph. Two types of insertion problems are then identified where the underlying disjunctive graph is through- or bi-connected. For these cases, it is shown that the short cycle property holds and the conflict graph is bipartite, allowing to derive a polyhedral characterization of all feasible insertions. An efficient method for deciding whether there exists a feasible insertion, and a lower and upper bound procedure for the minimum makespan insertion problem are developed. For bi-connected graphs, this procedure solves the insertion problem to optimality. The obtained results are applied to three extensions of the classical Job Shop, the Multi-Processor Task, Blocking and No-Wait Job Shop, and two types of insertions, job and block insertion.
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.12.025
ISSN: 0377-2217
URI: https://digitalcollection.zhaw.ch/handle/11475/3602
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.