Titlebar

Export bibliographic data
Literature by the same author
plus on the publication server
plus at Google Scholar

 

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

URN to cite this document: urn:nbn:de:bvb:703-opus-8381

Title data

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

[img] PDF
article_opt_online.pdf - Published Version
Available under License Creative Commons BY 3.0: Attribution .

Download (407kB)

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.

Further data

Item Type: Preprint, postprint
Keywords: Reihenfolgeproblem; Kombinatorische Optimierung; Komplexitaet; Approximationsalgorithmus; FPTAS; complexity; job-shop; transversal graph
DDC Subjects: 500 Science > 510 Mathematics
Institutions of the University: Faculties > Faculty of Mathematics, Physics und Computer Science > Department of Mathematics
Faculties
Faculties > Faculty of Mathematics, Physics und Computer Science
Language: English
Originates at UBT: Yes
URN: urn:nbn:de:bvb:703-opus-8381
Date Deposited: 25 Apr 2014 08:34
Last Modified: 28 Mar 2019 10:08
URI: https://epub.uni-bayreuth.de/id/eprint/352

Downloads

Downloads per month over past year