Three-machine Open Shop Problem with the Minimum Makespan Criterion

국문 초록 (Abstract)

본 논문은 삼중기계 오픈샵 일정계획의 makespan 최소화 문제(O3||Cmax), 즉 최대 총공정시간 최소화 문제를 다룬다. 이중기계 오픈샵 문제의 다항시간 알고리즘과 그 해는 Gonzalez와 Sahni에 의해 이미 도출되었다. Gonzalez와 Sahni는 이러한 문제가 삼중기계 조건으로 확장되었을 때, NP-hard 문제로 분류됨을 증명하였다. 때문에 문제의 복잡도 측면을 고려한다면 보다 효율적인 알고리즘이 구현 가능한 또 다른 NP-hard 분류 범위를 탐색해 볼 필요가 있다.
본 연구는 O3||Cmax 문제의 NP-hard 분류가 가능한 범위를 최대공정시간과 기계부하의 관계를 통해 공식화한다. Li을 i번째 기계의 부하(총공정시간), pmax을 최대공정시간으로 정의하고, 기계의 번호(i)는 부하의 단조감소 순서에 따라 부여한다고 하자. 이때 L₁-L₃ ≥ 2pmax의 조건에서 O3||Cmax 다항시간 알고리즘 문제의 최적해가 도출될 수 있음이 밝혀진 바 있다. 본 연구에서는 ‘hard’ 문제와 ‘easy’ 문제의 명확한 구분을 위해 매개변수분석을 수행한다. 이에 따른 주요한 결과로 2L₁-L₂-L₃ <2pmax의 조건이 만족할 때 일반적인 NP-hard 문제로 분류 가능함을 보여준다. 분석결과는 또한 여전히 일반적인 O3||Cmax 문제의 복잡도가 판단될 수 없는 분류 범위를 도출하였다. 이와 같은 범위에서는 NP-hardness의 범위를 벗어나는 특수한 O3||Cmax 문제를 제안하여 선형시간 조건 하에서 최적해 도출이 가능함을 확인한다.

다국어 초록 (Multilingual 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 L₁-L₃ ≥2pmax. In this paper, we show that the problem is ordinary NP-hard if 2L₁-L₂-L₃ < 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.

목차 (Table of Contents)

• Abstract
• Ⅰ. Introduction
• Ⅱ. Model formulation and notation
• Ⅲ. Complexity of O3
• Cmax in terms of machine loads
• Ⅳ. Conclusion
• References
• 요약