This thesis focuses on a flexible job-shop scheduling problem with separable sequence-dependent setup time in semiconductor manufacturing. In this problem, all the jobs require five serial operations which can be performed by one of three identical multi-purpose machines. Each machine needs a setup time between different types of operations. Scheduling problems at the photolithography process in semiconductor wafer fabrication facilities are typical examples for this problem. For the problem with the objectives of minimizing mean flow time and mean tardiness, we develop a priority rule-based scheduling method and a two-stage scheduling method considering job release times and due dates. In these methods, the operations are assigned to machines and then the sequence of operations is determined on each machine. To evaluate performance of the suggested scheduling method, we perform computational experiments with randomly generated data sets reflecting real situations relatively well. Results of the computational experiments shows that the proposed methods perform better than existing methods developed in other researches and a method used in a real semiconductor manufacturing system.
본 논문은 순서에 종속적인 준비 시간이 존재하는 유연 Job-shop 시스템에서의 스케쥴링 문제를 다루고 있다. 시스템이 매우 복잡하고 다양한 조건을 필요로 하는 반도체 제조 공정의 경우 효율적인 생산 계획을 세움으로써 큰 비용 절감 효과를 기대할 수 있으므로 효율적인 생산 계획 스케쥴링이 매우 중요한 문제가 되고 있다. 일반적으로 Job-shop 시스템의 스케쥴링 문제가 이미 NP-hard 문제로 알려져 있으므로 각각의 Workstation 에 여러 대의 machine 이 존재하는 유연 Job-shop 시스템을 고려하는 본 문제 또한 NP-hard 문제임을 알 수 있다. 이러한 문제의 복잡성 때문에 기존의 다른 연구에서는 주로 makespan을 최소화하는 것을 목표로 metaheuristic 을 이용하여 유연 Job-shop 시스템의 스케쥴링 문제를 풀었다. 본 논문에서는 평균 flow time 과 평균 tardiness를 최소화 하는 것을 목표로 충분히 빠른 시간 안에 큰 문제를 다룰 수 있도록 우선순위를 부여하는 알고리즘과 계층적인 알고리즘을 기초로 하는 두 가지 휴리스틱을 제안하고 있다. 제안된 두 휴리스틱의 성능 평가를 위해 실제 반도체 공정의 조건을 반영하여 임의로 생성한 다양한 data set을 이용하여 실험을 수행하였고 그 결과 빠른 시간 내에 좋은 해를 찾을 수 있었다. 두 휴리스틱 중에서는 우선순위를 부여하는 휴리스틱보다 두 가지 목적식을 계층적으로 다루는 휴리스틱이 더 좋은 해를 주는 것으로 나타났다.