Three-machine Open Shop Problem with the Minimum Makespan Criterion
0
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
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.
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.
참고문헌 (20)
- 김대철, "소아정신과 치료실의 최적 구성방안", 한국생산관리학회지, 25(2), pp.147~163 (2014), 한국생산관리학회
- 박유진, "반도체 장비 데이터 통신 네트워크의 성능평가에 관한 연구", 한국생산관리학회지, 26(3), pp.329~350 (2015), 한국생산관리학회
- 서연정, "물류자동화 시스템의 도입에 사용되는 기업의 전략 유형과 이들이 기업의 운영성과에 미치는 영향", 한국생산관리학회지, 26(4), pp.375~402 (2015), 한국생산관리학회
- Adiri, I., "Open-Shop Scheduling Problems with Dominated Machines", Naval Research Logistics, 36(3), pp.273~281 (1989)
- Bárány, I., "Nearly Optimum Solution of Multimachine Scheduling Problems", Szigma, 15, pp.177~191 (1982)
- Drobouchevitch, I. G., "A Polynomial Algorithm for the Three-Machine Open Shop with a Bottleneck Machine", Annals of Operations Research, 92, pp.185~214 (1999)
- Fiala, T., "An Algorithm for the Open-Shop Problem", Mathematics of Operations Research, 8(1), pp.100~109 (1983)
- Garey, M. R., "Computers and Intractability: A Guide to the Theory of NP-Completeness" (1979), W.H. Freeman
- Gonzalez, T, "Open Shop Scheduling to Minimize Finish Time", Journal of the Association for Computing Machinery, 23(4), pp.665~679 (1976)
- Kashyrskikh, K. N., "Polynomially Solvable Case of the Two-Stage Three-Machine Open Shop problem", Diskretnyi Analiz i Issledovanie Operatsii, Seriya 1, 8(1), pp.23~39 (2001)
- Kononov, A., "When the Difference in Machine Loads Leads to Efficient Scheduling in Open Shops", Annals of Operations Research, 92, pp.211~239 (1999)
- Kononov, A., "A Complete 4-Parametric Complexity Classification of Short Shop Scheduling Problems", Journal of Scheduling, 15, pp.427~446 (2012)
- Koulamas, C., "The Three-Machine Proportionate Open Shop and Mixed Shop Minimum Makespan Problems", European Journal of Operational Research, 243, pp.70~74 (2015)
- Kyparisis, G. J., "Open Shop Scheduling with Maximal Machines", Discrete Applied Mathematics, 78, pp.175~187 (1997)
- Lawler, E. L., "Handbook in Operations Research and Management Science, Vol.4, Logistics of Production and Inventory", pp.445~521 (1993), Elsevier Science Publishers B. V
- Leung, J. Y.-T., "Handbook of Scheduling:Algorithms, Models, and Performance Analysis", pp.2004, Chapman & Hall
- Liu, C. Y., "Scheduling Ordered Open Shops", Computers & Operations Research, 14, pp.257~264 (1987)
- Lopez, P, "Production Scheduling" (2008), ISTE Ltd and John Wiley & Sons, Inc
- Sevastianov, S. V., "A Polynomial-Time Open-Shop Problem with an Arbitrary Number of Machines", Cybernetics and Systems Analysis, 28(6), pp.918~933 (1992)
- Williamson, D. P., "Short Shop Schedules", Operations Research, 45, pp.288~294 (1997)