In this thesis, we consider a scheduling problem in a semiconductor test facility, in which tardiness of orders is to be minimized. We focus on the loading/unloading workstation and the burn-in workstation, which may be considered bottleneck workstations in the test facility. In the loading/ unloading workstation, there are unrelated parallel machines, while there are identical parallel batch-processing machines called chambers in the burn-in workstation. Each chamber can process up to B boards simultaneously. A set of wafers is loaded on a board in the loading workstation, before a set of boards can be processed together in the burn-in workstation. We present four types of heuristic algorithms for scheduling problems in the burn-in workstations: extended list scheduling algorithms; look-ahead list scheduling algorithms; algorithms based on an existing heuristic developed for a single machine tardiness problem; and local search algorithms. Also, we develop several algorithms for the loading/unloading workstations. To evaluate performance of the algorithms, a series of computational experiments are performed on randomly generated test problems and results show that the suggested heuristic algorithms work well and outperform the existing rule currently used in a real system.
본 논문은 반도체 검사설비에서의 납기지연 최소화를 위한 일정계획 문제를 다루고 있다. 반도체 검사설비 중 병목작업장으로 로딩/언로딩 작업장과 번인 작업장으로 구성된다. 로딩/언로딩 작업장은 이종 병렬 기계들로 구성되어 있고, 번인 작업장은 배치 작업이 가능한 동종 병렬 기계로 구성되어 있다. 번인 작업장의 동종 병렬 기계는 챔버라고 불리우며, B개 보드의 동시 작업이 가능하다. 웨이퍼 집단은 로딩 작업장에서 보드에 적화되고, 적화된 보드는 번인 작업장으로 운반되어 챔버에 의해 동시 작업이 수행된다. 본 논문에서는 번인 작업장에서의 일정계획을 위한 네 개 범주의 알고리즘을 개발하였다. 이는 extended list scheduling algorithms, look-ahead list scheduling algorithms, 단일 기계 납기 문제에 대한 현존 알고리즘을 기반으로 하는 알고리즘, 그리고 local search 알고리즘이다. 또한 본 논문에서는 로딩/언로딩 작업장을 위한 세 개 범주의 알고리즘을 개발하였다. 마지막으로 이 논문에서 제안한 알고리즘의 성능평가를 위하여 무작위의 문제를 생성하여 테스트를 실시한 결과, 현재 시스템에 사용 중인 일정계획 방법보다 좋은 해를 얻을 수 있었다.
