This dissertation focuses on scheduling problems in re-entrant flowshops, flowshops with reentrant flows of jobs. In a typical flowshop composed of m machines, jobs are composed of m operations at most and each job visits each machine at most once. On the other hand, in re-entrant flowshops, jobs should visit the machines multiple times. In other words, jobs should go through multiple passes of serial manufacturing processes, that is, routes of all jobs are identical as in ordinary flowshop, but the jobs must be processed multiple times on the machines. We consider three different problems for re-entrant flowshop scheduling, and develop algorithms for the problems.
First, we consider a two-machine re-entrant flowshop scheduling problem with the objective of minimizing makespan. In the re-entrant flowshop, all jobs must be processed twice on each machine, that is, each job should be processed on machine 1, machine 2 and then machine 1 and machine 2. We develop dominance properties, lower bounds and upper bounds on the makespan for the problem, and suggest a branch and bound algorithm that is developed using these properties and bounds. Secondly, we focus on a two-machine re-entrant flowshop scheduling problem with the objective of minimizing total tardiness. We develop dominance properties, lower bounds and upper bounds on the total tardiness of a given set of jobs for the problem, and suggest a branch and bound algorithm that is developed using these properties and bounds.
Finally, we consider an m-machine re-entrant flowshop scheduling problems with the objective of minimizing makespan and total tardiness, respectively. In the m-machine (m≥2) re-entrant flowshop considered here, all jobs should be processed L (≥2) times on each machine, and hence all jobs are composed of Lm operations with zero or positive processing times. We suggest heuristic algorithms, which are modified from well-known existing algorithms for the general m-machine flowshop problem or newly developed.
Performance of the suggested algorithms are evaluated through series of computational tests on test problems which are obtained from data of real manufacturing systems that have forms of re-entrant flowshops 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.
본 논문에서는 재 투입이 있는 흐름공정에서 생산성과 납기를 고려하는 생산 일정계획 문제를 다루고 있다. 재 투입이 있는 흐름공정이란 일반적인 흐름공정의 확장된 형태이다. 일반적인 흐름공정에서는 제품이 순차적으로 위치하고 있는 각 기계들에서의 해당 공정을 통하여 이루어지며 마지막 기계에서의 해당 공정이 완료 될 때 그 제품의 작업이 완료 된다. 하지만, 재 투입이 있는 흐름공정에서는 제품이 마지막 기계에서의 해당공정을 완료한 후 흐름공정의 첫 번째 기계에 재 투입되어 처음에 수행했던 공정과 유사한 혹은 동일한 공정들을 다시 수행하게 된다. 재 투입이 있는 흐름공정은 반도체 웨이퍼와 PCB (printed circuit board) 등의 high-tech 제품 및 섬유와 거울을 생산하는 제조 시스템에서 빈번히 사용되는 공정이며 일반적으로 병목공정으로 분류된다. 본 논문에서는 실제 재 투입이 있는 흐름공정에서 발생하는 세 가지의 일정계획 문제를 고려하였고, 주어진 작업들의 최대종료시간 및 납기지연을 최소화하는 재 투입이 있는 흐름공정의 일정계획 문제에서 작업들의 순서를 결정해 주는 알맞은 해법을 개발하였다.
먼저, 논문의 2장에서는 두 대의 기계들로 이루어지고 한번의 재 투입이 있는 흐름공정에서 작업들의 최대종료시간을 최소화하는 일정계획 문제를 다루었다. 본 장에서는 최적해(optimal solution)를 구하기 위하여 분지 한계 방법(branch and bound algorithm)을 개발하였다. 먼저 본 장에서는 최적해의 우월 성질(dominance property), 하한(lower bound) 및 휴리스틱 방법을 이용한 상한 (upper bound) 계산 방법들을 개발하여 제안된 분지 한계 방법에 이용하여 적당한 시간 내에 일정계획 문제의 최적 스케쥴을 구할 수 있었다.
다음으로, 논문의 3장에서는 논문의 2 장에서 다루었던 공정과 동일한 두 대의 기계들로 이루어지고 한 번의 재투입이 있는 흐름공정의 일정계획 문제를 다루었다. 다만, 일정계획 문제의 목적함수는 작업들의 최대 종료시간이 아닌 작업들의 총 납기 지연을 최소화 하는 것이다. 본 장에서는 최적해를 구하기 위하여 분지 한계 방법을 개발하였다. 논문의 2 장에서와 마찬가지로, 본 장에서는 최적해의 우월 성질, 하한 및 휴리스틱 방법을 이용한 상한 계산 방법들을 개발하여 제안된 분지 한계 방법에 이용하여 적당한 시간 내에 일정계획 문제의 최적 스케쥴을 구할 수 있었다.
마지막으로, 논문의 4장에서는 두 대 이상의 기계들로 이루어지고 한번 이상의 재투입이 있는 흐름공정의 일정계획 문제를 다루었다. 논문의 2 장과 3장에서는 한 번의 재투입과 두 대의 기계들만을 고려한 것에 비해, 4장에서는 한번 이상의 재투입과 두 대 이상의 기계들까지 고려하였다. 마찬가지로, 일정계획 문제의 목적함수는 작업들의 최대 종료시간 및 총 납기 지연을 최소화하는 것이다. 본 장에서는 고려하는 문제를 해결하기 위해서 일반적인 흐름공정 문제를 위해 기존에 개발된 휴리스틱(heuristic) 방법들을 본 문제에 적용할 수 있도록 보정하였으며 새로운 휴리스틱 방법들을 개발하였다.
본 논문에서 개발된 최적화 방법들과 휴리스틱 방법들은 많은 계산 실험을 통하여 그 성능을 평가되었다. 특히, 실제 현장의 문제 또는 실제 현장의 상황을 반영할 수 있도록 생성된 실험 문제들을 이용하여 평가되었다. 평가로부터 현실적인 시간 내에 논문에서 다루고 있는 병렬 기계 공정에서의 스케쥴에 대한 우수한 해들을 찾을 수 있음을 확인하였다.
