Titlebar

Bibliografische Daten exportieren
Literatur vom gleichen Autor
plus auf ERef Bayreuth
plus bei Google Scholar

 

Job-shop scheduling in a body shop

Titelangaben

Schauer, Joachim ; Schwarz, Cornelius:
Job-shop scheduling in a body shop.
In: Journal of Scheduling. Bd. 16 (April 2013) Heft 2 . - S. 215-229.
ISSN 1094-6136
DOI: https://doi.org/10.1007/s10951-012-0300-2

Volltext

Link zum Volltext (externe URL): Volltext

Weitere URLs

Abstract

We study a generalized job-shop problem called the body shop scheduling problem (BSSP). This problem arises from the industrial application of welding in a car body production line, where possible collisions between industrial robots have to be taken into account. BSSP corresponds to a job-shop problem where the operations of a job have to follow alternating routes on the machines, certain operations of different jobs are not allowed to be processed at the same time and after processing an operation of a certain job a machine might be unavailable for a given time for operations of other jobs. As main results we will show that for three jobs and four machines the special case where only one machine is used by more than one job is already NP-hard. This also implies that the single machine scheduling problem that asks for a makespan minimal schedule of three chains of operations with delays between the operations of a chain is NP-hard. On the positive side, we present a polynomial algorithm for the two job case and a pseudo-polynomial algorithm together with an FPTAS for an arbitrary but constant number of jobs. Hence for a constant number of jobs we fully settle the complexity status of the problem.

Weitere Angaben

Publikationsform: Artikel in einer Zeitschrift
Begutachteter Beitrag: Ja
Keywords: Job-shop; FPTAS; Complexity; Transversal graph
Institutionen der Universität: Fakultäten > Fakultät für Mathematik, Physik und Informatik
Fakultäten > Fakultät für Mathematik, Physik und Informatik > Mathematisches Institut
Fakultäten > Fakultät für Mathematik, Physik und Informatik > Mathematisches Institut > Lehrstuhl Wirtschaftsmathematik
Fakultäten > Fakultät für Mathematik, Physik und Informatik > Mathematisches Institut > Lehrstuhl Wirtschaftsmathematik > Lehrstuhl Wirtschaftsmathematik - Univ.-Prof. Dr. Jörg Rambau
Fakultäten
Titel an der UBT entstanden: Ja
Themengebiete aus DDC: 000 Informatik,Informationswissenschaft, allgemeine Werke > 004 Informatik
500 Naturwissenschaften und Mathematik > 510 Mathematik
Eingestellt am: 21 Nov 2014 08:37
Letzte Änderung: 01 Dec 2014 12:40
URI: https://eref.uni-bayreuth.de/id/eprint/3784