This dissertation focuses on scheduling problems in a semiconductor wafer fabrication (fab) which produces semiconductor products of a large number of different product types in a low-volume and high-variety setting. In this fab, it is not easy to achieve both meeting due dates of orders and increasing production efficiency because the production environment is very complicated due to various resource constraints. Therefore, it is required to develop new scheduling methodologies that consider those constraints effectively. In this dissertation, we develop scheduling algorithms for the production subsystems with the resource constraints in the fab, and then, we develop a production scheduling methodologies for the entire fab based on the dispatching rule-based approaches.
First, we consider a two-machine flowshop scheduling problem with limited waiting time constraints with the objective of minimizing makespan. By the limited waiting time constraints, the second operation of each job should be started within a certain time period after the first operation of the job is completed. We develop optimal solution properties, upper bounds and lower bounds, and suggest a branch and bound algorithm that is developed using the properties and bounds.
Secondly, two scheduling problems with distinct resource constraints are considered, respectively. We first consider a batch-processing machine scheduling problem with a product-mix ratio constraint with the objective of minimizing makespan. By the product-mix ratio constraint, jobs of multiple product types can be processed simultaneously as a batch according to the predetermined product-mix ratio. We develop an optimal solution algorithm which gives solutions in polynomial time. Then, we consider a batch-processing machine scheduling problem with resource constraints with the objective of minimizing total tardiness. By the resource constraints, a setup operation is incurred to change the resource tank with a new one whenever the amount of remaining capacity of each resource type is less than the amount of resource required to process a batch of that type. We develop optimal solution properties and suggest dynamic programming algorithms in that the properties are used.
Finally, we consider a scheduling problem for the entire semiconductor wafer fab with the limited waiting time constraints and the resource constraints with the objective of minimizing total tardiness. We develop scheduling algorithms for workstations with the limited waiting time constraints and for the ion implant workstation with the resource constraints based on the dispatching-rule based scheduling approaches. In addition, to conduct an empirical research we develop a simulation model based on the real data of the fab.
Performance of the suggested algorithms are evaluated through series of computational tests on test problems which are obtained from real data or generated in such a way that resulting problems reflect the real situations relatively well. Results of the computational tests show that the algorithms suggested in this dissertation give very good solutions in reasonable amount of computation time. Also, the algorithms suggested in this dissertation can be used in real manufacturing systems if they are modified slightly to cope with the practical situations.
본 논문에서는 주문생산 방식에 따라 수많은 종류의 제품을 생산하는 반도체 웨이퍼 제조 시스템에 대한 스케쥴링 문제를 다루고 있다. 해당 반도체 제조 시스템의 제조 환경은 시스템 내부에 존재하는 여러 가지의 자원제약으로 인해 매우 복잡하기 때문에 고객 납기준수율과 생산성을 향상시키는 것은 매우 어려운 문제로 인식되고 있다. 따라서 반도체 산업의 경쟁력 강화를 위해서는, 여러 자원제약을 고려하는 효과적인 스케쥴링 방법론의 개발이 필수적이다. 본 연구에서는 먼저 해당 시스템 내의 여러 단위시스템(subsystem)에 대한 스케쥴링 방법론을 개발하고, 다음으로 전체 시스템에 대한 스케쥴링 방법론을 디스패칭 규칙(dispatching rule)을 사용하는 스케쥴링 방법론에 기반하여 개발하고자 한다.
첫 번째로, 대기시간 제약이 있는 두 대의 설비로 구성된 흐름공정(two-stage flowshop)에서 작업들의 최대종료시간을 최소화하는 스케쥴링 문제를 다루었다. 대기시간 제약이란 어떤 작업의 첫 번째 공정이 종료된 후 일정한 대기시간 내에 반드시 해당 작업의 두 번째 공정이 시작되어야만 하는 제약을 뜻한다. 본 장에서는 최적해의 성질(optimal solution property), 상한(upper bound) 및 하한(lower bound) 계산 방법을 개발하고 이를 이용하는 분지한계법(branch and bound algorithm)을 제시하였다.
다음으로, 서로 다른 자원제약을 가진 두 가지 스케쥴링 문제를 각각 다루었다. 우선 제품군별 구성 제약이 있는 배치설비(batch-processing machine)에서 작업들의 최대종료시간을 최소화하는 스케쥴링 문제를 다루었다. 제품군별 구성 제약이란 하나의 배치를 구성할 때 제품군별로 사전에 정해진 개수의 작업만을 해당 배치에 포함할 수 있는 제약을 말한다. 본 문제에 대하여 다항시간(polynomial time) 내에 최적해를 구할 수 있는 최적해 알고리듬을 제시하였다. 또 자원용량 제약이 있는 배치설비에서 작업들의 총 납기지연을 최소화하는 스케쥴링 문제를 다루었다. 자원용량 제약 하에서는, 어떤 자원의 남은 양이 현재 진행하고자 하는 배치에서 필요로 하는 양보다 적을 경우에 해당 자원을 설비에 공급하는 탱크를 교체하는 준비작업(setup)을 필요로 한다. 본 문제에 대하여 최적해의 성질(optimal solution property)을 개발하고 이를 이용하는 동적계획법(dynamic programming algorithm)을 제시하였다.
마지막으로, 앞서 언급한 제약조건들이 존재하는 전체 반도체 제조 시스템에서 작업들의 총 납기지연을 최소화하는 스케쥴링 문제를 다루었다. 본 문제에 대하여 디스패칭 규칙을 이용한 접근방법에 기반한 스케쥴링 알고리듬을 개발하였으며, 전체 시스템에 대한 시뮬레이션(simulation) 모델을 개발하여 개발된 알고리듬의 성능을 평가하였다.
본 논문에서 제안된 반도체 제조 시스템에 대한 스케쥴링 알고리듬의 성능 은 계산 실험을 통해 기존에 개발된 방법들과 함께 비교 및 평가되었다. 특히, 실제 현장의 문제 또는 실제 현장의 상황을 반영할 수 있도록 생성된 실험 문제들을 이용하여 평가되었다. 실험 결과를 통하여, 제안된 스케쥴링 알고리듬은 논문에서 다루고 있는 문제에 대해 현실적인 시간 내에 최적해 혹은 우수한 해를 찾아낼 수 있음을 확인하였다.
