This thesis deals with the development of mixed integer optimization algorithms for the sizing and scheduling of batch processes that are involved in multiproduct or multipurpose plants. The goal is to develop mathematical models and efficient solution techniques.
A new mixed-integer linear program (MILP) model in which makespan is minimized for the multiproduct batch processes are developed. Specifically, the Zero Wait (ZW) scheduling with transfer and sequence-dependent setup times is analyzed. Not only idle times between the successive products but also heads and tails are used to select a possible production sequence with the minimum makespan. To determine the suitable head and tail, new binary variables are defined, and aggregated to the assignment constraints of Traveling Salesman Problems (TSP). Although the number of binary variables increases, the mathematical formulation can yield a very compact MILP model. The effectiveness of the proposed model is demonstrated through several examples. Also, the proposed model is extended to solve the scheduling problems for productions with Single Product Campaigns (SPC) and Mixed Product Campaigns (MPC) explained by Birewar and Grossmann (I&EC R. 28(9), 1333, 1989b).
As in the scheduling problem, the design decisions regarding sizes of the processing units, structure of the batch plant (e.g. use of parallel units), and functionality of various units (e.g. task assignment to various units) will depend on their estimate of the scheduling performance. The problem of simultaneous sizing and scheduling of multiproduct batch processes with one equipment per stage is analyzed. For most of NLP or MINLP formulations, in general, a potential problem is that integer variables cannot be handled by existing solvers. In the case when the solution of the integer variables is not in integer, the solution may be under- or over-estimated. In order to estimate the optimal solution in which integer variables are included, two algorithms, binary and decimal representations, are proposed. Then, the optimal solution for design problems can be provided. Alternate design models including the proposed scheduling algorithm are developed. For the cases when equipment is based on the assumption of continuous or discrete sizes, the design models are formulated as MINLP or MILP, respectively. Thus, the results from the proposed models are compared with those from earlier works, and it is shown that the proposed models are superior to others.
Scheduling problems have received considerable attention in the literature. However, the results obtained are often of limited value in industrial practice since restrictive assumptions are made in most of the studies. Therefore, the scheduling of an industrial manufacturing system for practical large size problems in a high-tech industry which is of much topical interest - semiconductor manufacturing is addressed. The purpose of this study is the development of effective scheduling models for wafer fabrication. The wafer fabrication scheduling is started from novel mathematical formulations considering its complexities, e.g., reentrant flow or batch processing steps in the wafer fab.
This research contributes to the understanding of the scheduling problems of complex processes such as the semiconductor manufacturing system. Also, based on the knowledge obtained from the mathematical models, more efficient algorithms may be developed.
본 논문은 다품종 회분식 공정 이나 혹은 다목적 공정들을 포함하고 있는 회분식 공정의 크기 결정 뿐만 아니라 일정계획을 수립하기 위한 정수 혼합에 관련된 최적화 기법들을 다루고자 한다. 그 목적은 수학적인 모델식과 효율적으로 해를 구하는 방법들을 개발하는데 있다.
다품종 회분식 공정에서의 makespan을 최소화 하는 새로운 선형 혼합 정수계획법(mixed-integer linear programming, MILP)을 개발하였다. 특히, Zero-Wait방안의 일정계획(scheduling)을 수송시간(transfer time) 및 순서에 영향을 받는 준비시간(setup time) 등을 고려하여 수립하였다. 제품들이 생산되는 과정에서 발생하는 각 장치들의 지연시간(idle time) 뿐만 아니라 head 와 tail time들을 이용하여 최소의 makespan을 갖는 조업순서를 결정하였다. 적절한 head 와 tail time들을 결정하기 위하여, 새로운 이진변수(binary variable)들을 정의하고 이 변수들을 traveling salesman problem(TSP)의 제한조건(constraint)에 포함되도록 하였다. 비록 새로운 이진변수에 의하여 모델식의 이진변수들의 개수는 증가하지만 수학적인 모델은 아주 작은 MILP로 수식화되었다. 제안된 모델식의 효용성을 입증하기 위하여 여러개의 예제에 대하여 적용하여 보았다. 또한, 제안된 모델식을 단일 생산방안(single product campaign, SPC)와 혼합 생산방안(mixed product campaign) 등에 확장하여 적용하였다.
일정계획에서와 마찬가지로, 조업장치들의 크기, 회분식 공정의 구조, 여러 장치들의 기능 등을 고려하는 결정하는 설계문제는 일정계획의 성능에 따라 달라질 것이다. 본 연구에서는 장치의 크기와 일정계획을 동시에 고려하는 문제도 해결하는 방안을 연구하고자 한다. 그러나, 일반적으로 대부분의 비선형 혼합 정수 계획법(MINLP)에서는 정수의 변수를 취급할 수 없다. 결국, 정수의 변수가 실수(real)의 해로 얻어질 때, 그때의 해는 최적의 해라는 보장을 할 수가 없는 것이다. 그러므로, 본 연구에서는 정수 변수들을 포함하는 문제의 최적해를 얻기 위하여, 이진 표현법(binary representation, BR) 및 십진 표현법(decimal representation, DR)이라는 두 가지의 기법을 제안하였다. 또한, 위에서 언급한 일정계획의 기법을 적용하여 보다 효율적인 설계 모델식을 개발하였다.
일정계획에 대한 문제는 널리 고려되고 있다는 것을 문헌을 살펴 보면 쉽게 알 수 있다. 그러나 보통 얻어진 결과는 실제의 산업적인 크기 보다 훨씬 적은 경우가 대부분이다. 이것은 많은 이상적인 가정들을 고려하여 연구가 진행되고 있기 때문이다. 그러므로, 본 논문의 6장은 실제 문제의 크기를 갖고 있는 산업의 제조 공정에 일정계획의 적용에 대하여 살펴 볼 것이다. 여기에서 가장 관심이 지대하며, high-tech 산업인 반도체 제조(semiconductor manufacturing)에 대해서 연구할 것이다. 본 연구의 목적은 wafer fabrication에 대한 일정계획을 수립하는 효율적인 model 식의 개발이다. Wafer fabrication에 대한 일정계획은 공정의 대표적인 몇가지의 특성, 재진입의 흐름이나 회분식 조업단계의 존재 등에 대한 기본적인 수학적 모델식을 수립하는 데에서 출발할 것이다.
그러므로, 본 연구는 반도체 제조 공정과 같은 복잡한 공정의 일정계획에 대한 문제점들을 이해할 수 있도록 해주며, 더 나아가서 수학적인 모델식으로 부터 얻어진 지식으로 보다 효율적인 기법들의 개발을 쉽게 해 줄 것이다.
