This dissertation focuses on scheduling problems in parallel-machine shops with the objective of minimizing total tardiness. A parallel-machine shop consists of multiple machines that can process the same set of jobs independently. Generally, processors/machines at parallel-machine shops can be classified into three types according to the processing time of a job: identical processors, uniform processors and unrelated processors. We consider three different problems for parallel-machine scheduling, and develop algorithms for the problems.
First, we consider an identical parallel-machine scheduling problem with the objective of minimizing total tardiness of jobs. Identical parallel machines can process the same set of jobs and the processing times of a job are the same on all the machines. We develop dominance properties, upper bounds and lower bounds on the total tardiness of a given set of jobs, and suggest a branch and bound algorithm that is developed using these properties and bounds.
Secondly, we consider a scheduling problem in unrelated parallel-machine shops, which processing times of a job on different machines are arbitrarily different. The objective of the problem is to minimize total tardiness of a given set of jobs. In the problem considered here, we identify several optimal solution properties and develop dominance properties, lower bounds and upper bounds. To obtain an optimal solution, we devise a branch and bound algorithm using those properties and bounds with a new branching scheme developed in this research.
Finally, we focus on the problem of scheduling jobs on identical parallel machines considering a job splitting property. In this problem, it is assumed that a job can be split into a discrete number of sub-jobs and they are processed on parallel machines independently. Here, a sub-job is a set or a batch of (identical) unit-jobs of a job that are processed on a machine consecutively. For the problem with the objective of minimizing total tardiness, we suggest a branch and bound algorithm after devising some dominance properties and lower bounds.
Performance of the suggested algorithms are evaluated through series of computational tests on test problems which are obtained from real data or generated in such a way that resulting problems reflect the real situations relatively well. Results of the computational tests show that the algorithms suggested in this research give very good solutions in a reasonable amount of computation time. Also, the algorithms suggested in this research can be used for operations scheduling problem in real manufacturing systems if they are modified slightly to cope with special characteristics of the problems.
본 논문에서는 병렬 기계 공정에서 납기를 고려하는 생산 일정계획 문제를 다루고 있다. 병렬 기계 공정이란 동일한 작업을 수행할 수 있는 기계들이 다수 존재하는 생산 시스템을 말한다. 소량 다품종 생산 방식이 늘어나면서 병렬 기계 공정은 다수의 산업 현장에서 빈번히 사용되는 공정일 뿐만 아니라 원천적으로 다수의 작업을 동시에 해야 하는 공정이기 때문에 대다수의 시스템에서는 병목공정으로 알려져 있다. 본 논문에서는 실제 병렬 기계 공정에서 발생하는 세가지의 일정계획 문제를 고려하였고, 주어진 작업들의 납기지연을 최소화하는 병렬 기계 공정에서의 작업들의 순서를 결정해 주는 알맞은 해법을 개발하였다.
먼저, 논문의 2장에서는 동종 병렬 기계(identical parallel machines)가 존재하는 공정에서의 작업들의 총 납기지연을 최소화하는 일정계획 문제를 다루었다. 동종 병렬 기계라 함은 동일한 작업을 서로 다른 기계에서 수행하더라도, 동종의 기계이기 때문에 같은 작업수행시간을 소요되는 것을 의미한다. 본 장에서는 최적해(optimal solution)를 구하기 위하여 분지 한계 방법(branch and bound algorithm)을 개발하였다. 먼저 본 장에서는 최적해의 우월 성질(dominance property) 및 하한(lower bound) 계산 방법을 개발하여 제안된 분지 한계 방법에 이용하였다. 뿐만 아니라 동종 병렬 기계에서의 일정 계획 문제하에서 분지 한계 방법에서 쓰일 수 있는 가지치기 방법(branching scheme)과 새로운 상한 (upper bound) 계산 방법을 통하여 적당한 시간내에 일정계획 문제의 최적 스케쥴을 구할 수 있었다. 뿐만 아니라 실험을 통해 기존에 알려져 있는 방법들과 비교하였을 때 훨씬 우월한 결과를 보여주었다.
다음으로, 논문의 3장에서는 이종 병렬 기계(unrelated parallel machines)가 존재하는 공정에서의 작업들의 총 납기지연을 최소화하는 일정계획 문제를 다루었다. 이종 병렬 기계라 함은 동일한 작업을 수행할 수 있는 병렬 기계라 하더라고 서로간의 모델 번호나 제작 시기가 달라 같은 작업을 수행하더라고 서로 다른 기계에서는 상이한 작업 시간을 갖는 것을 의미한다. 논문의 2장에서 다룬 동종 병렬 기계에서의 일정 계획 문제는 이종 병렬 기계 문제의 특이한 경우라고 볼 수 있다. 본 장에서는 논문의 2장과 마찬가지로 최적해를 구하기 위하여 분지 한계 방법을 개발하였다. 본 장에서는 최적해가 갖는 특별한 성질을 먼저 밝히고, 하한 및 상한계산 방법을 개발하였다. 또한 분지 한계 방법에서 쓰일 수 있는 가지치기 방법을 개발하여 제안된 분지 한계 방법에 사용하였다. 실험 결과를 통하여 기존에 제안된 방법보도 훨씬 많은 문제를 빠른 시간 안에 풀 수 있다는 것을 보여주었다.
마지막으로, 논문의 4장에서는 특정한 성질을 갖는 병렬 공정에서의 생산 일정계획 문제를 다루었다. PCB(Printed Circuit Board) 제조 시스템에서 드릴(Drill)공정은 대기하고 있는 패널(panel)에 구멍(hole)을 뚫는 공정으로서 하나의 작업(job)이 여러대의 드릴 기계에 나누어져 가공된 후에 작업이 완료되면 다시 합쳐져 다음 공정에 전달되게 된다. 이렇게 작업이 분할되어 공정이 수행되는 것을 작업 분할 성질 (job splitting property)이라고 한다. 본 장에서는 이러한 작업 분할 성질이 있을 때 작업의 납기를 최소화 하는 일정계획 문제를 다루고 있다. 2장과 3장에서와 마찬가지로 해의 최적해가 갖는 성질을 먼저 밝히고, 하한 및 상한계산 방법을 개발하였다. 그리고 분지 한계 방법에서 쓰일 수 있는 가지치기 방법을 개발하여 제안된 분지 한계 방법에 사용하였다. 이러한 분지 한계 방법을 사용하면 분할되는 작업의 최적의 일정계획이 구해지게 된다.
본 논문에서 개발된 최적화 방법들은 많은 계산 실험을 통하여 기존에 알려진 방법들과 비교하여 그 성능을 평가하였다. 특히, 실제 현장의 문제 또는 실제 현장의 상황을 반영할 수 있도록 생성된 실험 문제들을 이용하여 평가되었다. 평가로부터 현실적인 시간 내에 논문에서 다루고 있는 병렬 기계 공정에서의 스케쥴에 대한 우수한 해들을 찾을 수 있음을 확인하였다.
