1. ZHAW digitalcollection
  2. School of Engineering
  3. Publikationen
  4. Publikationen School of Engineering
Full metadata record
DC FieldValueLanguage
dc.contributor.authorGröflin, Heinz-
dc.contributor.authorKlinkert, Andreas-
dc.date.accessioned2018-03-08T15:26:31Z-
dc.date.available2018-03-08T15:26:31Z-
dc.date.issued2007-
dc.identifier.issn0377-2217de_CH
dc.identifier.urihttps://digitalcollection.zhaw.ch/handle/11475/3602-
dc.description.abstractInsertion 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.de_CH
dc.language.isoende_CH
dc.publisherElsevierde_CH
dc.relation.ispartofEuropean Journal of Operational Researchde_CH
dc.rightsLicence according to publishing contractde_CH
dc.subjectInsertionde_CH
dc.subjectSchedulingde_CH
dc.subjectJob shopde_CH
dc.subject.ddc510: Mathematikde_CH
dc.titleFeasible insertions in job shop scheduling, short cycles and stable setsde_CH
dc.typeBeitrag in wissenschaftlicher Zeitschriftde_CH
dcterms.typeTextde_CH
zhaw.departementSchool of Engineeringde_CH
zhaw.organisationalunitInstitut für Datenanalyse und Prozessdesign (IDP)de_CH
dc.identifier.doi10.1016/j.ejor.2005.12.025de_CH
zhaw.funding.euNode_CH
zhaw.issue2de_CH
zhaw.originated.zhawYesde_CH
zhaw.pages.end785de_CH
zhaw.pages.start763de_CH
zhaw.publication.statuspublishedVersionde_CH
zhaw.volume177de_CH
zhaw.publication.reviewPeer review (Publikation)de_CH
Appears in collections:Publikationen School of Engineering

Files in This Item:
There are no files associated with this item.
Show simple item record
Gröflin, H., & Klinkert, A. (2007). Feasible insertions in job shop scheduling, short cycles and stable sets. European Journal of Operational Research, 177(2), 763–785. https://doi.org/10.1016/j.ejor.2005.12.025
Gröflin, H. and Klinkert, A. (2007) ‘Feasible insertions in job shop scheduling, short cycles and stable sets’, European Journal of Operational Research, 177(2), pp. 763–785. Available at: https://doi.org/10.1016/j.ejor.2005.12.025.
H. Gröflin and A. Klinkert, “Feasible insertions in job shop scheduling, short cycles and stable sets,” European Journal of Operational Research, vol. 177, no. 2, pp. 763–785, 2007, doi: 10.1016/j.ejor.2005.12.025.
GRÖFLIN, Heinz und Andreas KLINKERT, 2007. Feasible insertions in job shop scheduling, short cycles and stable sets. European Journal of Operational Research. 2007. Bd. 177, Nr. 2, S. 763–785. DOI 10.1016/j.ejor.2005.12.025
Gröflin, Heinz, and Andreas Klinkert. 2007. “Feasible Insertions in Job Shop Scheduling, Short Cycles and Stable Sets.” European Journal of Operational Research 177 (2): 763–85. https://doi.org/10.1016/j.ejor.2005.12.025.
Gröflin, Heinz, and Andreas Klinkert. “Feasible Insertions in Job Shop Scheduling, Short Cycles and Stable Sets.” European Journal of Operational Research, vol. 177, no. 2, 2007, pp. 763–85, https://doi.org/10.1016/j.ejor.2005.12.025.


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