3중기계 오픈샵 문제에서의 Makespan 최소화Three-machine Open Shop Problem with the Minimum Makespan Criterion
- Other Titles
- Three-machine Open Shop Problem with the Minimum Makespan Criterion
- Authors
- Inna Drobouchevitch
- Issue Date
- 2016
- Publisher
- 한국생산관리학회
- Keywords
- scheduling; open shop; machine load; computational complexity; 스케줄링; 오픈샵; 기계부하; 계산 복잡도
- Citation
- 한국생산관리학회지, v.27, no.1, pp.87 - 101
- Indexed
- KCI
- Journal Title
- 한국생산관리학회지
- Volume
- 27
- Number
- 1
- Start Page
- 87
- End Page
- 101
- URI
- https://scholar.korea.ac.kr/handle/2021.sw.korea/90847
- DOI
- 10.21131/kopoms.27.1.201602.87
- ISSN
- 1229-831X
- Abstract
- The paper considers the three-machine open shop scheduling problem to minimize the makespan, i.e., the maximum completion time (O3||Cmax). The open shop problem was introduced by Gonzalez and Sahni who gave a polynomial time algorithm for its solution in the case of two machines. They also proved that this problem is NP-hard in the case of three machines. In view of the problem complexity, it is an attractive research goal to search for the widest possible classes of problem instances which admit efficient solutions.
Such problem classes can be formulated in terms of a certain relation between machine loads and maximum operation length. Let Li be the load (the total time of all operations) of the ith machine and let pmax be the maximum operation length. Suppose that the machines are numbered in the non-increasing order of their loads. The O3||Cmax problem is known to be polynomially solvable if L1-L3≥2pmax. In this paper, we show that the problem is ordinary NP-hard if 2L1-L2-L3< 2pmax. We then consider a special case of the O3||Cmax problem that lies outside the known NP-hardness bounds and show that it is solvable in linear time.
- Files in This Item
- There are no files associated with this item.
- Appears in
Collections - Graduate School > Department of Business Administration > 1. Journal Articles
Items in ScholarWorks are protected by copyright, with all rights reserved, unless otherwise indicated.