A generalized job-shop problem with more than one resource demand per task

We study a generalized job-shop problem called the Laser Sharing Problem with fixed tours (LSP-T) where the tasks may need more than one resource simultaneously. This fact will be used to model possible collisions between industrial robots. For three robots we will show that the special case where only one resource is used by more than one robot is already NP-hard. This also implies that one machine scheduling with chained min delay precedence constraints is NP-hard for at least three chains. OnWe study a generalized job-shop problem called the Laser Sharing Problem with fixed tours (LSP-T) where the tasks may need more than one resource simultaneously. This fact will be used to model possible collisions between industrial robots. For three robots we will show that the special case where only one resource is used by more than one robot is already NP-hard. This also implies that one machine scheduling with chained min delay precedence constraints is NP-hard for at least three chains. On the positive side, we present a polynomial algorithm for the two robot case and a pseudo-polynomial algorithm together with an FPTAS for an arbitrary but constant number of robots. This gives a sharp boundary of the complexity status for a constant number of robots.show moreshow less

Download full text files

Export metadata

  • Export Bibtex
  • Export RIS
  • frontdoor_exportcitavi

Additional Services

    Share in Twitter Search Google Scholar
Metadaten
Institutes:Mathematik
Author: Joachim Schauer, Cornelius Schwarz
Creating Corporation:Universität Bayreuth, Mathematisches Institut
Contributing Corporation:Universität Graz, Institut für Statistik und Operations Research
Year of Completion:2011
SWD-Keyword:Approximationsalgorithmus; Kombinatorische Optimierung; Komplexitaet; Reihenfolgeproblem
Tag:FPTAS; complexity; job-shop; transversal graph
Dewey Decimal Classification:510 Mathematik
URN:urn:nbn:de:bvb:703-opus-8381
Document Type:Preprint
Language:English
Date of Publication (online):04.04.2011