This thesis considers four scheduling problems concerned with systems having a batch processing machine. The batch processing machine processes a number of jobs together in a batch. These problems are individually described below in more detail.
First, a scheduling problem is considered for a single burn-in oven in semiconductor manufacturing industry where the oven is a batch processing machine and each batch processing time is represented by the largest processing time among those of all the jobs contained in the batch. The objective measure of the problem is the maximum completion time (makespan) of all jobs, for which a dynamic case is analyzed using a branch-and-bound algorithm and several heuristics. The worst case error performance ratios of the heuristics are also derived. For an instance of the dynamic problem case where each job belongs to one of a fixed number of families, a dynamic programming algorithm is proposed in a polynomial time complexity for a situation where the number of job families is given(fixed).
Second, a single burn-in oven scheduling problem is considered for all jobs available at time zero with a given common due date to find the optimal schedule which minimizes the sum of earliness-tardiness. In the analysis, some optimal dominance properties are characterized, based upon which two heuristic algorithms including just a simple heuristic and a tabu-search-incorporated heuristic are derived.
Third, a scheduling problem for a two-machine flowshop system with a batch processing machine incorporated is considered to find the optimal schedule which minimizes the maximum completion time. In the analysis, some solution dominance properties are characterized, based upon which the dynamic programming procedure is derived for the solution finding. Another scheduling problem is also investigated for a single batch processing machine with dynamic job arrivals allowed.
Finally, a stochastic batching problem is considered for a batch process where various numbers of jobs are allowed to process together in each batch and jobs arrive randomly but not in a specified pattern. The objective of the problem is to determine the optimal size (number of jobs) of each batch with respect to the measure of minimizing the mean queueing time of jobs. For the problem, a multi-layer perceptron neural network model is proposed to make real-time batching control.
본 논문은 뱃치 공정 설비를 갖춘 시스템에서의 생산일정계획 문제를 다루었다. 뱃치 공정 설비는 여러 개의 작업을 하나의 뱃치로 묶어서 동시에 가공하는 설비를 말한다. 이러한 뱃치 공정 설비는 공정 기술의 발달로 많은 산업(특히, 반도체 제조 산업 등)에서 이용되고 있다. 따라서, 뱃치 공정 설비에서의 생산일정계획은 전체 산업 시스템의 생산성 향상을 위한 중요한 경영상의 문제인 것이다.
본 논문에서는 먼저, 반도체 제조 산업에서 이용되고 있는 번-인 오븐(Burn-in oven)에서의 생산일정계획 문제를 다루었다. 번-인 오븐은 뱃치 공정 설비로서, 한 뱃치의 가공 시간이 그 뱃치에 포함된 작업의 가공 시간 중 가장 큰 값이 되는 독특한 성질을 가지고 있다. 이 문제에서의 목적 함수는 가장 큰 작업 완료 시간을 가지는 작업의 작업 완료 시간(최대 작업 완료 시간, Makespan)을 최소화하는 것이다. 모든 작업이 도착해 있는 경우(Static case), 최적 스케쥴을 제공하는 최적해 성질을 규명하고, 모든 작업의 도착 시간이 다른 경우(Dynamic case), 최적해 성질을 규명하여, 이를 기초로 한 분지한계법(Branch-and-bound algorithm)과 여러 개의 발견적 기법(Heuristic)들을 제시하였다. 또한, 제시한 발견적 기법의 성능평가를 위해 한계분석(Worst-case analysis)과 수치 자료를 이용한 실험을 병행하였다. 그리고, 모든 작업의 도착 시간이 다르고, 각 작업이 하나의 그룹(family)에 속하는 상황의 문제도 다루었다. 여러 개의 작업들이 같은 그룹에 속했다는 것은 그 작업들의 가공 시간이 같다는 의미이다. 이 문제에 대해 최적해 성질을 규명하고, 이를 기초로 최적 스케쥴을 제공하는 동적계획법(Dynamic programming algorithm)을 제시하였다. 이 동적계획법은 그룹의 수가 적다면, 다항(Polynomial) 시간 만에 최적 스케쥴을 제공한다.
다음으로, 앞서 설명한 번-인 오븐에서 모든 작업들이 공통 납기 시간을 가지는 경우, 총 조기/지연 달성 비용(Earliness-tardiness)을 최소화하는 문제를 다루었다. 최적해 성질을 규명하였고, 이를 기초로 한 두가지 발견적 기법을 제시하였다. 이 두가지 발견적 기법의 성능평가를 위해 수치 자료 실험을 수행하였다.
다음으로, 두 대의 설비 중 한 대의 설비가 뱃치 공정 설비인 흐름 공정 시스템(flowshop)에서 최대 작업 완료 시간을 최소화하는 문제를 다루었다. 이 문제에서의 뱃치 공정 설비는 앞서의 번-인 공정과는 달리 뱃치 가공 시간이 일정하다. 위에서 언급한 그룹이 존재하고, 연속적으로 가공되는 작업들이 다른 그룹에 속한다면 셋업(Setup)이 발생하게 된다. 이 문제에 대해 최적해 성질을 규명하고, 이를 기초로 최적 스케쥴을 제공하는 동적계획법을 제시하였다. 그리고, 각 작업의 도착 시간이 다른 경우에 단일 뱃치 공정 설비에서의 최대 작업 완료 시간을 최소화하는 문제도 다루었다.
끝으로, 작업 도착 시간에 대한 정보가 없는 경우, 뱃치 공정 설비에서 작업들의 평균 지연 시간(Mean waiting time)을 최소화하는 문제에 대해 신경회로망(Neural network)을 기초로 한 발견적 기법을 제시하였다. 특히, 제어(control) 문제에 많이 이용되고 있는 다층 퍼셉트론 신경회로망 모형을 이용하였다. 이 발견적 기법의 성능평가를 위해 기존에 연구되어 왔던 최소 뱃치 크기(minimum batch size) 정책과 모의 실험을 수행하였다.
