This thesis focuses on a parallel-machine scheduling problem for jobs with sequence-independent family setup times and history dependent setup times, which can be found often in semiconductor wafer fabrication facilities. Since the parallel-machine scheduling problem (with the objective of minimizing the total weighted flow time of the jobs) is known to be NP-complete, we present heuristic algorithms, in which a simple and systematic scheduling logic is employed. The scheduling logic is related with decisions and information involved in the scheduling problem, which are job selection and production history generation. We propose rules for production history generation and job selection rules including simple priority rules. A series of computational experiments was performed to compare the suggested heuristics with a scheduling method currently used in practice, and results show that the suggested heuristics outperform the existing method.
본 논문은 병렬 작업기계로 구성된 작업장에서 작업물이 여러 개의 작업군으로 구성되어 있으며 생산 이력정보에 의하여 셋업시간이 발생하는 스케쥴링 문제를 다루고 있다. 각각의 작업군에는 동일한 작업시간을 갖는 동일한 특성의 작업물들이 여러 개 존재한다. 본 연구에서는 두가지 종류의 셋업시간을 고려하고 있다. 첫번째는 작업군을 변경 하였을때 발생하는 셋업시간이다. 같은 작업군에 속하는 작업물들이 연속적으로 작업될 때는 셋업시간이 발생하지 않지만 다른 작업군에 속하는 작업물들이 연속적으로 작업될 경우에는 추가로 셋업시간이 소요된다. 두번째는 이력기반 셋업으로 과거에 해당 설비에서의 생산이 이루어졌던 생산이력의 존재 유무에 따라 발생하게 된다. 임의의 작업군이 병렬기계들 중 하나의 기계에서 작업을 하기 위해서는 해당 작업군에 대한 작업조건을 설정하기 위하여 초기 셋업시간이 소요되게 된다. 이러한 초기 셋업이 이루어진 설비는 생산 이력이 이미 생성되어 있으므로, 추후 해당 기계에서 해당 작업군에 대한 이력기반 셋업시간은 필요가 없게 된다.
본 논문에서는 작업물의 총 가중 작업 흐름시간을 최소화 하는 스케쥴링 방법론을 제시하고 있다. 각 작업물은 동적으로 작업장에 도착하게 되며, 모든 작업물은 중요도에 따라 서로 다른 가중치를 가지게 된다. 본 논문에서는 이력정보를 고려한 스케쥴링 로직과 해당 로직에 포함되는 여러 개의 작업 선택규칙과 이력생성을 위한 작업군 선택 규칙을 제안 하고있다. 제안된 방법론들은 일련의 실험을 통해 실제 시스템에서 작업하고 있는 방법과 비교하였으며, 여러 개의 작업선택 규칙과 이력생성을 위한 작업군선택 규칙의 실험 결과를 비교하여 가장 좋은 결과를 갖는 방법론을 제시하였다.
