In this thesis, we consider a scheduling problem in the subsystem (foaming and inspection) of a refrigerator manufacturing systems, in which makespan is to be minimized. We focuses on the subsystem (foaming and inspection), which is considered bottleneck in a refrigerator manufacturing systems. This problem is a two-machine flowshop scheduling problem in which there should be delay time between the operations on the first and second machines for each job. For the problem with the objective of minimizing makespan, we develop dominance properties (adjacent job-pair 4 cases and non-adjacent job 1 case), two lower bounds and three heuristic algorithms, and use these to develop a branch and bound algorithm. To evaluate the performance of the algorithm, computational experiments are performed on randomly generated test problems. Results of the experiments show that the suggested branch and bound algorithm can solve problems with up to 200 jobs in a reasonable amount of CPU time.
본 논문은 두 단계로 이루어진 흐름공정에 있어서 두 번째 단계의 공정을 시작하기 전 Job별로 각각 다른 시간을 지체한 후 가야 하는 시스템에 있어서 스케줄링 문제를 다루고 있다. 대표적인 예로는 냉장고 제조공정에 있어서 발포공정를 거친 후 검사공정으로 가기 전, 발포공정에서 주입한 화학물질이 반응을 끝날 때까지 기다린 후 검사공정으로 가야 하는 시스템을 꼽을 수 있다. 발포공정에서 주입한 화학 물질은 Job별로 양이 틀리므로 지체해야 하는 시간 역시 Job별로 틀림을 알 수 있다.
본 논문에서는 이 문제에 대한 최적의 해를 구하기 위하여 5개의 Dominance Property와 (인접한 작업에 대한 4개, 인접하지 않은 작업에 대한 1개) 2개의 Lowerbound 그리고 3개의 Upperbound heuristic를 개발하여 Branch and Bound Algorithm을 구현하였다. 이 알고리즘을 다양한 문제에 대해서 실험하고 평가한 결과, 제안된 알고리즘이 효율적으로 작동하여 200개 작업까지의 문제를 수긍할 만한 시간 안에 풀 수 있다는 것을 보여주었다.
