This paper considers a two-machine flowshop scheduling problem for minimizing mean flowtime. Each job has three non-preemptive operations, where the first and third operations must be processed on the first and second machines, respectively, but the second operation is allowed to be processed on either machine. A lower bound based on SPT rule is derived, which is then used to develop a branch-and-bound algorithm. Also, an efficient simple heuristic algorithm is developed to generate a near-optimal schedule. Numerical experiments are conducted to evaluate the performances of the proposed branch-and-bound and the heuristic algorithm.
본 논문에서는 기계가 두 대인 플로우 샵에서 작업의 평균 플로우 시간을 최소화하는 스케쥴링 문제를 다룬다. 이 때, 각 작업은 세 가지씩의 공정을 거쳐서 완성되는데 첫 번째 공정은 첫 번째 기계에서 공정이 이루어져야만 하고 두 번째 공정은 두 기계의 어느 곳에서나 공정이 이루어질 수 있고 세 번째 공정은 두 번째 기계에서만 공정이 이루어져야만 한다. 본 문제에 대해, SPT 규칙을 기반으로 한 lower-bound가 도출되었고 이는 branch-and-bound 알고리즘을 개발하는데 이용되었다. 또한 문제의 최적해에 근접할 수 있는 효과적이고 쉬운 heuristic 알고리즘도 개발되었으며, 제안된 branch-and-bound 알고리즘과 heuristic알고리즘의 성능을 측정하기 위한 실험이 수행되었다. 실험 결과를 통해 제안된 branch-and-bound 알고리즘이 효율적으로 작동할 뿐만 아니라 큰 문제에 대해서는 제안된 heuristic이 최적해에 가까운 좋은 해를 도출함을 보여주었다. 따라서 본 heuristic의 다양한 응용상황을 예상할 수 있는데, 대표적으로 두 공정 사이에 포장 공정이나 set up 공정이 필요한 상황에 당장 적용이 기대된다. 추가적인 연구 과제로는 다수의 기계를 대상으로 하는 확대된 문제를 고민할 수 있을 것이다.
