This thesis considers three scheduling problems concerned with systems incorporating batch processing machines. Each of the batch processing machines can process a number of jobs together in batch. These problems are individually described below in detail.
First, a scheduling problem is considered for a multi-stage flowshop of batch processing machines where each batch processing machine can process a batch of jobs simultaneously so that all jobs contained in each batch are released together to the next machine after their processing. With respect to any regular measure of performance, several solution properties are characterized to exploit a problem reduction procedure for removing dominated machines. The reduction procedure is incorporated into two efficient heuristic solution algorithms for minimizing two corresponding regular measures of performance including "makespan" and "sum of completion times".
Second, a scheduling problem is considered for a flowshop composed of two batch processing machines. The problem is investigated for three cases each being concerned with one of three due date related measures including "maximum tardiness", "the number of tardy jobs" and "total tardiness". In the analysis, several solution properties are characterized, based on which the efficient polynomial time algorithms are developed for minimizing the corresponding due date related measures.
Finally, a scheduling problem is considered for a two-machine flowshop where a discrete processing machine is followed by a batch processing machine and a finite number of jobs arrive dynamically at the first machine. In the flowshop, the discrete processing machine processes one job at a time and the batch processing machine processes a batch of jobs simultaneously. The objective is to find the optimal schedule which minimizes the maximum completion time (makespan) of all jobs. In the situation where preemption is allowed on the discrete processing machine, it is shown that the optimal schedule can be found in polynomial time. However, in the situation where no preemption is allowed on the discrete processing machine, it is shown that the problem is NP-complete, for which an efficient heuristic solution algorithm is constructed and its tight worst-case error bound is derived.
본 논문에서는 뱃치와 개별 생산 설비들로 구성된 시스템에서의 생산일정계획 문제를 다루었다. 뱃치 생산 설비는 여러 개의 작업을 하나의 뱃치로 묶어서 동시에 가공하는 설비를 말한다. 이러한 뱃치 생산 설비는 공정 기술의 발달로 많은 산업(특히, 반도체 제조 산업 등)에서 이용되고 있다.
본 논문에서는 먼저, 여러 개의 뱃치 생산 설비가 직렬로 연결된 시스템에서의 생산일정문제를 다루었다. 임의의 정규 척도(Regular measure)에 대하여 성립하는 최적해 성질을 규명하고, 이를 기초로 문제의 크기를 줄일 수 있는 알고리즘을 개발하였다. 또한, 최대 작업 완료 시간(Makespan)과 총 작업 완료 시간(Sum of completion times)에 대하여 각각 발견적 기법을 제시하였다. 이 두가지 발견적 기법(Hueristic)의 성능평가를 위해 수치 자료 실험을 수행하였다.
다음으로, 두개의 뱃치 생산 설비가 직렬로 연결된 시스템에서의 생산일정계획 문제를 다루었다. 세가지 납기 관련 척도(Due date related measures), 즉, 최대 납기 지연 시간(Maximum tardiness), 납기 지연 작업의 수(Number of tardy jobs), 총 납기 지연 시간(Total tardiness) 각각에 대하여 최적해 성질을 규명하고, 이를 기초로 최적 알고리즘들을 제시하였다. 이 최적 알고리즘들은 다항(Polynomial) 시간 만에 최적 스케쥴을 제공한다.
끝으로, 개별 생산 설비와 뱃치 생산 설비가 직렬로 연결된 시스템에서 각 작업의 도착 시간이 서로 다른 경우에 최대 작업 완료 시간을 최소화하는 문제를 다루었다. 개별 생산 설비에서 작업의 선점(Preemption)을 허용하는 경우에 대해 최적해 성질을 규명하고, 이를 기초로 최적 알고리즘을 제시하였다. 개별 생산 설비에서 작업의 선점을 허용하지 않는 경우에 대해, 이 문제가 NP-난도문제(NP-hard problem)임을 증명하였다. 또한, 이 문제의 최적해 성질을 규명하였고, 이를 기초로 발견적 기법을 제시하였다. 이 발견적 기법의 성능평가를 위해 수치 자료 실험을 수행하였다.
