Optimization Models for Capacity Estimation and Scheduling Problems in Semiconductor Wafer Fabrication Lines = 반도체 웨이퍼 제조 라인에서의 용량 추정 및 일정계획 문제에 대한 최적화 모형 및 해법

국문 초록 (Abstract)

반도체 웨이퍼 제조는 수백 개의 공정 단계와 수천 대의 설비로 구성된 복잡하고 자본 집약적인 공정이다. 운영 효율성을 극대화하기 위해서는 정확한 생산 용량을 추정하고 추정된 용량을 바탕으로 설비를 효율적으로 운영하는 것이 중요하다. 이를 위해 많은 연구들이 이루어져 왔지만, 공정의 규모와 복잡성으로 인해 여전히 어려운 과제로 남아 있다. 본 논문에서는 반도체 웨이퍼 제조 라인의 생산 용량 추정 및 일정 계획 문제를 효과적으로 해결하기 위한 새로운 최적화 모형과 해법을 제안한다.

우선, 반도체 웨이퍼 제조 라인의 생산 용량 추정 문제를 다룬다. 생산 용량 추정 문제는 목표 제품 믹스와 사이클 타임 하에서의 달성 가능한 처리량을 산출하는 것이다. 전통적인 최적화 모형은 외생적 리드 타임 파라미터를 사용하여 구조가 단순하고 활용이 용이하지만, 부하량에 따른 리드 타임 변화를 적절히 반영하기 어려워 공정의 동적 특성을 충분히 고려하지 못하는 한계가 있다. 이를 해결하기 위해 유연한 리드 타임 기반으로 한 새로운 최적화 모형을 제안한다. 제안된 모형은 공정 단계 내 재공품을 시간의 흐름에 따라 여러 상태로 구분하고, 재공품이 즉시 설비에서 처리되지 못할 경우 누적될 수 있도록 설계되었다. 이를 통해, 외생적 리드 타임을 적용하면서도 부하량 증가에 따른 리드 타임 변화를 반영할 수 있도록 한다. 또한, 대기 행렬 이론을 활용하여 목표 사이클 타임을 만족시키기 위한 리드 타임 파라미터를 추정하는 방법을 제시한다. 마지막으로, 시뮬레이션 모형을 활용한 계산 실험을 통해 제안된 모형이 기존 모형보다 공정을 더욱 정확하게 반영하며, 목표 사이클 타임과 제품 믹스 조건 하에서 생산 용량을 효과적으로 추정할 수 있음을 확인한다.

다음으로, 설비의 예방 유지 보수 일정 계획 문제를 탐구한다. 공정 단계별 처리량의 총합을 최대화하는 예방 유지 보수 작업 시작 시점을 결정하는 예방 유지 보수 일정 계획 문제를 해결하기 위한 최적화 모형을 제안한다. 제안된 최적화 모형은 전체 계획 기간을 여러 개의 이산적인 시간 구간으로 나누고, 예방 유지 보수 작업이 수행될 시점을 결정하는 방식으로 구성된다. 또한, 예방 유지 보수 작업의 종료 시점에 해당하는 시간 구간이 달라지는 작업 시작 시점인 임계 시점 개념을 도입하여, 임계 시점 전후의 작업 시작 여부에 따라 각 시간 구간에서의 작업 수행 시간이 결정되도록 설계되었다. 아울러, 대규모 문제를 효율적으로 해결하기 위해 선형 완화 문제를 먼저 풀고, 도출된 최적해를 기반으로 작업 시작 시점을 점진적으로 고정해 나가는 선형 완화 기반 휴리스틱 알고리듬을 제안한다. 마지막으로, 계산 실험을 수행하여 제안된 해법이 실제 운영 환경에서 효과적으로 활용될 수 있음을 확인한다.

마지막으로, 병렬 다중 챔버 설비에서의 웨이퍼-로트 일정 계획 문제를 다룬다. 공정 단계별 생산 목표 충족량을 최대화하는 챔버별 생산 일정을 결정하는 웨이퍼-로트 일정 계획 문제를 정의하고, 이를 해결하기 위한 최적화 모형을 제안한다. 또한, 모형의 가능해를 분석하여 성능을 향상시키기 위한 유효 부등식을 도입한다. 대규모 문제를 효과적으로 해결하기 위해 근사 동적 계획법 알고리듬을 제안한다. 제안된 알고리듬은 상태 가치 함수의 추정치를 활용하여 전체 상태 공간의 일부만 탐색하는 방식으로 계산 효율성을 높인다. 또한, 가치 함수를 효과적으로 추정하기 위해 상태의 목적 함수 값에 대한 상한과 하한을 계산하는 방법을 함께 제안한다. 하한 계산을 위해서는 주어진 상태에서 종료 상태까지 반복적으로 의사 결정을 수행하여 가능해를 구하는 휴리스틱 알고리즘을 적용하고, 상한 계산을 위해서는 문제의 일부 제약을 완화한 문제의 최적해를 통해 상한 값을 계산하는 여러 가지 모형을 제안한다. 마지막으로 실제 운영 환경의 특징을 반영한 계산 실험을 수행하여 제안된 해법의 효과성을 입증한다.

다국어 초록 (Multilingual Abstract)

A semiconductor wafer fabrication line (fab) is a highly complex and capital-intensive production system that involves hundreds of steps and thousands of pieces of equipment. To maximize operational efficiency, it is crucial to accurately estimate production capacity and operate equipment accordingly. However, the large scale and complexity of the fab make these tasks particularly challenging. In this dissertation, we propose novel optimization models and algorithms to address capacity estimation and scheduling problems.

First, we consider the problem of production capacity estimation. Capacity estimation involves determining the maximum achievable throughput of a fab during a given planning horizon in consideration of both product mix and target cycle time. Traditional optimization models using exogenous lead time variables are simple and easy to implement, but they fail to adequately capture the dynamic nature of the system, particularly lead time variations due to workload fluctuations. To overcome this limitation, we propose a new optimization model based on flexible lead time. The proposed model classifies work-in-process (WIP) into multiple states over time and is designed to allow WIP to accumulate when it cannot be immediately processed by the equipment. This enables the model to reflect lead time variations due to increased workload while maintaining the use of exogenous lead time. In addition, we present a method for estimating lead time parameters to satisfy the target cycle time by utilizing queuing theory. The results of the computational experiments using a simulation model demonstrate that the proposed model more accurately represents the fab and effectively estimates production capacity under target cycle time and product mix than existing models.

Next, we investigate the preventive maintenance (PM) scheduling problem, which aims to determine start times of PM tasks that maximize total throughput across all process steps. To address this, we propose a mixed-integer programming (MIP) model that incorporates a flexible-lead-time-based optimization model for capacity estimation. The planning horizon is divided into discrete time periods, and the period in which each PM task is performed is determined accordingly. We introduce the concept of critical time, which represents the boundary point where the set of periods for performing the PM task changes. This enables the PM duration in each period to be defined based on whether the task starts before or after the critical time. To efficiently solve large-sized instances, we develop a heuristic algorithm based on linear programming (LP) relaxation of the MIP model. Through computational experiments, we demonstrate the effectiveness of the proposed model and algorithm in practical applications.

Finally, we address a wafer-lot scheduling problem (WLSP) for parallel multi-chamber equipment. This equipment can process multiple wafers simultaneously, with each chamber handling one wafer at a time. To process a wafer, the corresponding lot must be loaded into a cassette module, which remains occupied until all wafers in the lot are processed, thereby limiting cassette module availability. Each wafer lot requires a specific process step, with target production quantities set for each step. The WLSP aims to maximize the fulfillment of these target quantities within the planning horizon while satisfying operational constraints. We show that the WLSP is strongly NP-hard and present an MIP model based on a two-level tour structure. To enhance performance, we derive valid inequalities that strengthen the LP relaxation bounds of the model. In addition, we propose approximate dynamic programming algorithms incorporating several bounding methods. Specifically, we devise three models to compute upper bounds and introduce a roll-out heuristic to obtain lower bounds. The effectiveness of the proposed model and algorithms is demonstrated through computational experiments on practically sized instances that reflect real-world fab characteristics.

목차 (Table of Contents)

• Abstract i
• Contents v
• List of Tables ix
• List of Figures xi
• Chapter 1 Introduction 1
• 1.1 Backgrounds 1
• 1.2 Literature Review 6
• 1.2.1 Capacity Planning 6
• 1.2.2 Production Planning 8
• 1.2.3 Scheduling 11
• 1.3 Research Motivations and Contributions 13
• 1.4 Outline of the Dissertation 16
• Chapter 2 Capacity Estimation for Wafer Fabrication Lines 19
• 2.1 Introduction 19
• 2.2 Literature Review 22
• 2.3 Problem Definition 27
• 2.4 Optimization Model 28
• 2.5 Estimating Lead Time Parameters 38
• 2.6 Comparison with Existing Models 41
• 2.6.1 Mathematical Formulations of Existing Models 42
• 2.6.2 Capacity Consumption 44
• 2.6.3 Lead Time Under Congestion 47
• 2.7 Computational Experiments 52
• 2.7.1 Experimental Settings 52
• 2.7.2 Experimental Results 58
• 2.8 Summary 76
• Chapter 3 Preventive Maintenance Scheduling for Wafer Fabrication Lines 79
• 3.1 Introduction 79
• 3.2 Literature Review 82
• 3.3 Problem Definition 86
• 3.4 Optimization Model 88
• 3.5 LP-based Fixing Heuristic Algorithm 93
• 3.6 Computational Experiments 95
• 3.6.1 Experimental Settings 95
• 3.6.2 Experimental Results 97
• 3.7 Summary 104
• Chapter 4 Wafer-Lot Scheduling for Parallel Multi-Chamber Equipment 105
• 4.1 Introduction 105
• 4.2 Literature Review 111
• 4.3 Problem Definition 117
• 4.3.1 Problem Description 118
• 4.3.2 Computational Complexity 119
• 4.4 Optimization Model 120
• 4.4.1 Mathematical Formulation 121
• 4.4.2 Valid Inequalities 126
• 4.5 Approximate Dynamic Programming Algorithm 128
• 4.5.1 Dynamic Programming Model 128
• 4.5.2 Computing Upper Bounds 133
• 4.5.3 Computing Lower Bounds 140
• 4.5.4 Value Function Approximation 142
• 4.5.5 Proposed ADP Algorithm 143
• 4.6 Computational Experiments 145
• 4.6.1 Test Instances 146
• 4.6.2 Experimental Settings 149
• 4.6.3 Experimental Results for MIP Models 152
• 4.6.4 Experimental Results for ADP Algorithms 154
• 4.6.5 Performance Comparison of MIP and ADP 158
• 4.6.6 Managerial Insights 163
• 4.7 Summary 164
• Chapter 5 Conclusion 165
• 5.1 Summary and Contributions 165
• 5.2 Future Research Directions 168
• Bibliography 173
• Appendix A Dispatching Weight Factors in Chapter 2 189
• Appendix B Sensitivity Analysis for the XLT Model in Chapter 2 193
• Appendix C Sorting Criteria for Wafer Bundles Used in Roll-out
• Heuristic in Chapter 4 199
• 국문초록 201