Flow Shops with Machine Maintenance: Ordered and Proportionate Cases
SCIE
SCOPUS
- Title
- Flow Shops with Machine Maintenance: Ordered and Proportionate Cases
- Authors
- Choi, BC; Lee, K; Leung, JYT; Pinedo, ML
- Date Issued
- 2010-11
- Publisher
- ELSEVIER SCIENCE BV
- Abstract
- We consider the m-machine ordered flow shop scheduling problem with machines subject to maintenance and with the makespan as objective. It is assumed that the maintenances are scheduled in advance and that the jobs are resumable. We consider permutation schedules and show that the problem is strongly NP-hard; it remains NP-hard in the ordinary sense even in the case of a single maintenance. We show that if the first (last) machine is the slowest and if maintenances occur only on the first (last) machine, then sequencing the jobs in the LPT (SPT) order yields an optimal schedule for the m-machine problem. As a special case of the ordered flow shop, we focus on the proportionate flow shop where the processing times of any given job on all the machines are identical. We prove that the proportionate flow shop problem with two maintenance periods is NP-hard, while the problem with a single maintenance period can be solved in polynomial time. Furthermore, we show that the optimal algorithm for the single maintenance case is a 3/2-approximation algorithm for the two maintenance case. In our conclusion we discuss also the computational complexity of other objective functions. (C) 2010 Elsevier B.V. All rights reserved.
- URI
- https://oasis.postech.ac.kr/handle/2014.oak/36385
- DOI
- 10.1016/J.EJOR.2010.04.018
- ISSN
- 0377-2217
- Article Type
- Article
- Citation
- EUROPEAN JOURNAL OF OPERATIONAL RESEARCH, vol. 207, no. 1, page. 97 - 104, 2010-11
- Files in This Item:
- There are no files associated with this item.
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.