This dissertation focuses on scheduling problems in hybrid flowshops with the objective of minimizing total tardiness. A hybrid flowshop is a generalized form of flowshops in which each stage consists of multiple parallel machines. We consider three different problems for hybrid flowshop scheduling, and develop algorithms for the problems.
First, we consider a two-stage hybrid flowshop scheduling problem with the objective of minimizing total tardiness of jobs. In the hybrid flowshop, there is one machine at the first stage and there are multiple identical parallel machines at the second stage. We develop dominance properties 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 a hybrid flowshop in which there are multiple serial stages, each with identical parallel machines. The objective of the problem is to minimize total tardiness of a given set of jobs. We suggest a new type of heuristic method, called bottleneck-focused algorithm, for the problem. In the algorithm, a schedule for a bottleneck stage is constructed first and then schedules for other stages are constructed based on the schedule for the bottleneck. Since the bottleneck stage may not be the first stage in the hybrid flowshop, ready times of operations at the bottleneck stage depend on the schedule at its upstream stages. At each iteration of the algorithm, the ready times are iteratively updated using information of a schedule obtained at the previous iteration.
Finally, we consider a production scheduling problem in a printed circuit board (PCB) manufacturing system, which has the form of hybrid flowshop. The system produces multiple product types with different due dates and different manufacturing processes. Also, setup operations are required at certain stages or machines, and some product types have reentrant flows. In the production scheduling problem, one must determine not only sequences of jobs at the stages but also batch sizes of a batch size of each product at each machine. We present a dispatching rule-based production scheduling method for the system. New dispatching rules are developed for each stage considering special features of PCB manufacturing. With the dispatching rules, we determine both the start time of each lot at a machine and the batch size of each product at each machine.
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. The algorithms suggested in this research can be used for real-world problems if they are modified to cope with special characteristics of the problems. Especially, the production scheduling algorithm developed for a PCB manufacturing system can be directly applied to the system.
본 논문에서는 혼합 흐름 공정에서 납기를 고려하는 일정계획 문제를 다루고 있다. 혼합 흐름 공정이란 각 작업들이 동일한 공정순서를 거쳐 완성되는 형태의 전통적인 흐름 공정에서 작업장마다 복수의 병렬기계가 존재하는 생산 시스템을 말한다. 본 논문에서는 세가지 혼합 흐름 공정 일정계획 문제를 고려하였고, 주어진 작업들의 납기지연을 최소화하면서 고려한 각 혼합 흐름 공정마다 작업장에서의 작업들의 순서를 결정해 주는 알맞은 해법을 개발하였다.
먼저, 논문의 2장에서는 두개의 작업장을 갖는 혼합 흐름 공정에서의 총 납기지연을 최소화하는 일정계획 문제를 다루었다. 고려되는 혼합 흐름 공정의 첫번째와 두번째 작업장에는 각각 단일 기계와 동일 병렬 기계들이 존재한다. 최적해를 구하기 위하여 분지 한계 방법(branch and bound algorithm)을 개발하였다. 본 장에서는 해의 우월 성질(dominance property) 및 하한 계산 방법을 개발하여 제안된 분지 한계 방법에 이용하였다. 제안된 방법을 통하여 적당한 계산 시간안에 고려된 혼합 흐름 공정 일정계획 문제의 최적 스케쥴을 구할 수 있었다.
다음으로, 논문의 3장에서는 직렬의 작업장마다 동일 병렬 기계들이 존재하는 혼합 흐름 공정에서의 일정계획 문제를 다루었다. 논문의 2장에서 두개의 작업장을 갖는 공정을 고려한 것에 비해, 3장에서는 30개의 작업장을 갖는 공정까지 고려하였다. 마찬가지로, 일정계획 문제의 목적함수는 총 납기 지연을 최소화하는 것이다. 본 장에서는 고려하는 문제를 해결하기 위해서 병목 중심 방법(bottleneck-focused algorithm)이라는 새로운 휴리스틱 방법을 개발하였다. 제안된 방법에서는 우선 병목 작업장의 스케쥴이 결정된 후 나머지 작업장들의 스케쥴은 병목 작업장의 스케쥴에 기반해서 생성되어진다. 병목 작업장이 혼합 흐름 공정의 첫번째 작업장이 아닐 수 있기 때문에, 병목 작업장에서의 각 작업들의 준비 시간은 선행 작업장에서의 스케쥴에 의존하게 된다. 제안된 방법에서는 병목 작업장에서의 준비시간을 이전에 얻어진 스케쥴 정보를 이용하여 반복적으로 갱신해 가면서 스케쥴을 결정하였다.
마지막으로, 논문의 4장에서는 인쇄 회로 기반(printed circuit board, PCB) 제조 시스템에서의 생산 일정계획 문제를 다루었다. PCB 제조 시스템은 다양한 납기를 갖는 복수의 제품 종류를 다양한 제조 공정을 통해서 생산하는 시스템으로 혼합 흐름 공정의 일종으로 볼 수 있다. 매우 많은 직렬 작업장으로 이루어져 있으며, 직렬 작업장마다 복수의 병렬 기계가 존재한다. 또한 특정한 작업장에는 셋업 작업(setup operation)이 필요한 경우도 있으며, 몇몇 제품을 재투입 흐름(reentrant flow)의 성질을 갖고 있다. 이러한 특징들을 고려하는 스케쥴을 구하기 위하여 4장에서는 디스패칭 규칙에 기반한 일정계획 방법을 제안하였다. 제안된 방법을 통하여 각 작업장의 작업 순서 뿐만 아니라 셋업이 필요한 작업에 대해서는 배치(batch)의 크기도 결정하였다.
본 논문에서 개발된 최적화 방법 및 휴리스틱 방법들은 많은 계산 실험을 통하여 그 성능을 평가하였다. 특히, 3장과 4장에서 방법들에 대해서는 실제 현장의 문제 또는 실제 현장의 상황을 반영할 수 있도록 생성된 실험 문제들을 이용하여 평가되었다. 평가로부터 현실적인 시간 내에 논문에서 다루고 있는 혼합 흐름 공정에서의 스케쥴에 대한 우수한 해들을 찾을 수 있음을 확인하였다.
