Titlebar

Bibliografische Daten exportieren
Literatur vom gleichen Autor
plus im Publikationsserver
plus bei Google Scholar

 

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

URN zum Zitieren dieses Dokuments: urn:nbn:de:bvb:703-opus-8381

Titelangaben

Schauer, Joachim ; Schwarz, Cornelius:
A generalized job-shop problem with more than one resource demand per task.
Bayreuth , 2011

Volltext

[img] PDF
article_opt_online.pdf - Veröffentlichte Version
Available under License Creative Commons BY 3.0: Namensnennung .

Download (398Kb)

Abstract

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. 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.

Weitere Angaben

Publikationsform: Preprint, Postprint, Working paper, Diskussionspapier
Keywords: Reihenfolgeproblem; Kombinatorische Optimierung; Komplexitaet; Approximationsalgorithmus; FPTAS; complexity; job-shop; transversal graph
Themengebiete aus DDC: 500 Naturwissenschaften und Mathematik > 510 Mathematik
Institutionen der Universität: Fakultäten > Fakultät für Mathematik, Physik und Informatik > Mathematisches Institut
Fakultäten
Fakultäten > Fakultät für Mathematik, Physik und Informatik
Sprache: Englisch
Titel an der UBT entstanden: Ja
URN: urn:nbn:de:bvb:703-opus-8381
Eingestellt am: 25 Apr 2014 08:34
Letzte Änderung: 25 Apr 2014 08:35
URI: https://epub.uni-bayreuth.de/id/eprint/352