In this dissertation, we consider three topics on flowshop scheduling problems in semiconductor wafer fabrication facilities (fabs). We consider two important characteristics of production in the fabs, i.e., existences of re-entrant flows and two classes of jobs with different urgencies. While each job visits each machine once in a typical flowshop, in a re-entrant flowshop, each job should visit the machines two or more times and hence there are re-entrant flows. In the two-machine re-entrant flowshop considered in this thesis, all jobs should be processed two times on each machine, and hence each job should be processed on machine 1 and machine 2, and then on machine 1 and machine 2 again. Also, as in semiconductor manufacturing systems, jobs are classified into two classes according to the urgencies of jobs: normal jobs and urgent jobs.
First, we consider a two-machine re-entrant flowshop scheduling problem with sequence-dependent setup times with the objective of minimizing total tardiness of jobs. We give a mathematical formulation, and develop dominance properties and a lower bound for the problem. Then, we propose a branch and bound (B&B) algorithm using these dominance properties and the lower bound. Also, we suggest several heuristics to obtain an initial upper bound for the B&B algorithm.
Secondly, we focus on a two-machine flowshop scheduling problem in which there are two classes of jobs with different urgencies, i.e., urgent jobs and normal (not urgent) jobs. The objective of this problem is to minimize a weighted sum of total tardiness of urgent jobs and the maximum completion time of normal jobs. We develop dominance properties, a lower bound and upper bounds for the problem. Then, we suggest a B&B algorithm using these dominance properties and bounds.
Finally, we consider a two-machine re-entrant flowshop scheduling problem with two classes of jobs. The objective of this problem is to minimize a weighted sum of total tardiness of urgent jobs and the maximum completion time of normal jobs. Because of complexity of (or difficulty of solving to optimality) the problem, we develop several heuristic algorithms.
Performance of the suggested algorithms in these three topics are evaluated through series of computational tests on instances which are obtained from real data or generated randomly but in such a way that resulting instances reflect the real situations relatively well. Results of the computational tests show that the algorithms suggested in this research give optimal solutions or very good solutions in a reasonable amount of computation time. The algorithms suggested in this research are expected to be used for real-world problems if they are modified to cope with the practical situations.
본 논문에서는 여러 가지 제약 조건 및 생산 특성이 존재하는 반도체 웨이퍼 제조 시스템에 대한 생산 일정 계획 문제를 다루고 있다. 반도체 웨이퍼 제조 시스템의 경우 재 투입, 긴급 주문, 대기 시간 제약, 작업 준비 시간 등 여러 가지 제약 조건으로 인해 가장 복잡한 생산 시스템 중에 하나로 알려져 있다. 따라서 반도체 제조 공정에서의 납기 준수율 및 생산성을 향상 시키는 것은 매우 어려운 문제로 인식되어 왔다. 하지만 반도체 산업의 경쟁 심화로 인해 이러한 여러 제약 및 특성을 고려한 효과적인 일정계획을 구해내는 방법론의 연구가 필수적으로 요구가 되고 있다. 본 연구에서는 반도체 웨이퍼 제조 공정의 대표적인 특성으로 알려져 있는 재 투입과 긴급 주문 등을 고려하여 반도체 웨이퍼 제조 공정 내의 단위 시스템에 대한 일정계획 방법론을 개발하고자 한다.
재 투입이 있는 흐름공정이란 일반적인 흐름공정의 확장된 형태이다. 일반적인 흐름공정에서는 제품이 순차적으로 위치하고 있는 각 기계들에서의 해당 공정을 거치면서 가공이 이루어지며 마지막 기계에서의 해당 공정이 완료 될 때 그 제품의 작업 또한 완료 된다. 하지만, 재 투입이 있는 흐름공정에서는 제품이 마지막 기계에서의 해당공정을 완료한 후 흐름공정의 이전 공정에 있는 기계에 재 투입되어 처음에 수행했던 공정과 유사한 혹은 동일한 공정들을 다시 수행하게 된다. 또한 긴급 주문이란, 고객의 요구사항이나 전체적인 생산 일정상의 이유로 해당 주문이 공정에 도착했을 시 최대한 납기 지연이 없이 작업을 수행해 줘야 하는 주문을 의미한다. 그리고 이러한 긴급 주문의 납기는 주문이 대기 없이 공정을 거쳤을 때의 완료 시점으로 정의 된다. 반도체 공정에서는 이러한 긴급 주문이 수시로 발생 하고 있고 이로 인해 주문들을 긴급 주문과 일반 주문으로 나누어서 작업들을 수행하고 있다. 따라서 본 연구에서는 이와 같은 긴급 주문을 고려한 일정 계획에 대해서도 연구를 수행 하였다.
먼저, 논문의 2장에서는 두 대의 기계들로 이루어지고 한 번의 재 투입이 있고 두 번째 기계에서 순서 의존 작업 준비 시간 (sequence-dependent setup time)이 존재 하는 흐름 공정에서의 작업들의 총 납기 지연 시간을 최소화하는 일정계획 문제를 다루었다. 본 장에서는 최적해(optimal solution)를 구하기 위하여 분지 한계 방법(branch and bound algorithm)을 개발하였다. 이를 위해 본 장에서는 최적해의 우월 성질(dominance property), 하한(lower bound) 및 휴리스틱 방법을 이용한 상한 (upper bound) 계산 방법들을 개발하고 이를 바탕으로 최적해를 구해내는 분지 한계 방법을 개발 하였다.
다음으로, 논문의 3장에서는 주문(작업)들이 긴급도에 따라 두 종류, 즉 일반 주문(normal job)과 긴급 주문(urgent job)으로 나뉘어 있고 두 대의 기계로 이루어진 흐름공정에서 일반 주문의 최대 작업 종료 시간과 긴급 주문의 총 납기 지연 시간의 가중합을 최소화 하는 일정 계획 문제를 다루었다. 본 장에서는 논문의 2장과 마찬가지로 최적해를 구하기 위하여 최적해가 갖는 특별한 성질을 먼저 밝히고, 하한 및 상한 계산 방법을 개발하였다. 또한 이러한 방법들을 바탕으로 분지 한계 방법을 개발하였다.
마지막으로, 논문의 4장에서는 주문들이 긴급도에 따라 두 종류, 즉 일반 주문(normal job)과 긴급 주문(urgent job)으로 나뉘어 있고, 두 대의 기계들로 이루어져 있으며 한 번의 재 투입이 존재하는 흐름 공정에서의 일정계획 문제를 다루었다. 본 일정 계획문제의 목적 함수는 3장에서 다룬 문제와 마찬가지로 일반 주문의 최대 작업 종료 시간과 긴급 주문의 총 납기 지연 시간의 가중합을 최소화 하는 것이다. 본 장에서 제시한 문제를 해결하기 위해 여러 휴리스틱 방법론들을 개발하였다.
본 논문에서 개발된 분지 한계 방법 및 휴리스틱 방법들은 현장의 상황을 반영하여 생성된 여러 실험 문제들을 푸는 실험을 통하여 그 효과를 검증하였다. 그리고 이러한 실험을 통하여, 본 논문에서 개발된 방법들이 현실적인 시간 내에 반도체 웨이퍼 제조공정에 존재하는 문제들에 대해 최적 또는 최적에 가까운 일정계획들을 잘 구해 낼 수 있음을 검증 하였다.
