Complexity of Scheduling Problem in Single-Machine Flexible Manufacturing System with Cyclic Transportation and Unlimited Buffers

Marie-Laure Espinouse (), Grzegorz Pawlak () and Malgorzata Sterna ()
Additional contact information
Marie-Laure Espinouse: Université Grenoble Alpes, CNRS, G-SCOP
Grzegorz Pawlak: Poznan University of Technology
Malgorzata Sterna: Poznan University of Technology

Journal of Optimization Theory and Applications, 2017, vol. 173, issue 3, No 16, 1042-1054

Abstract: Abstract The paper concerns complexity studies on the scheduling problem arising in a simple flexible manufacturing system. The system consists of a single machine, one depot (both with unlimited buffers), and one vehicle (automated guided vehicle). The vehicle operates according to the regular metro strategy. This means that it travels in cycles of the constant length, without stops, transporting at most one job at a time between the depot and the machine. The machine executes available jobs in the non-preemptive way. The goal is to minimize the schedule length, i.e., to minimize the number of vehicle cycles necessary to transport and execute all jobs in the system. We prove the strong NP-hardness of this problem and show that any list algorithm has the worst-case performance ratio equal to 2. Moreover, we mention that special cases of the considered problem, with zero transportation times from the depot to the machine and from the machine to the depot, are polynomially solvable.

Keywords: Flexible manufacturing system; Single machine; One depot; One vehicle; NP-hardness proof; Approximation algorithm; 90B35; 11Y16 (search for similar items in EconPapers)
Date: 2017
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-016-1056-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:173:y:2017:i:3:d:10.1007_s10957-016-1056-1

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-016-1056-1

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().