This dissertation focuses on scheduling problems in two-stage flowshops with a limited waiting time constraint and sequence-dependent setup times with objective of minimizing makespan, i.e., the maximum completion time of a given set of jobs. In these problems, the second operation of each job should be started within a certain period of time after the first operation of the job is completed, and the sequence-dependent setup times are incurred between jobs on the second stage. In this dissertation, we consider two different problems for flowshop scheduling, and develop algorithms for the problems.
First, we consider a two-machine flowshop scheduling problem with limited waiting times and sequence-dependent setup times. In the two-machine flowshop, all jobs must be processed first on machine 1 and then 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 consider a two-stage flowshop scheduling problem with limited waiting times and sequence-dependent setup times. In the two-stage flowshop, each stage consists of multiple identical parallel machines that can process the same set of jobs independently, and all jobs must be processed first on one of machines in stage 1 and then one of machines in stage 2. We develop heuristic algorithms, which are modified from well-known existing algorithms for other flowshop problems or newly developed.
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 suggest in this dissertation give very good solutions in a reasonable amount of computational time. Also, the algorithms suggested in this dissertation can be used for operations scheduling problems in real manufacturing systems if they are modified slightly to cope with the practical situations.
본 논문에서는 대기시간 제약과 순서의존 준비시간이 있는 두 단계로 이루어진 흐름공정(two-stage flowshop)에서 생산성을 고려한 생산 일정계획 문제를 다루고 있다. 대기시간 제약이란 어떤 작업의 첫 번째 공정이 종료된 후 일정한 대기시간 내에 반드시 해당 작업의 두 번째 공정이 시작되어야만 하는 제약을 뜻한다. 또한, 순서의존 준비시간이란 어떤 공정에서의 준비시간(setup time)이 작업들의 선후관계에 따라서 결정된다는 것으로, 본 연구에서는 두 번째 공정에서 순서의존 준비시간이 존재하는 공정을 다룬다. 본 논문에서는 위와 같은 제약이 존재하는 흐름공정에서 발생하는 두 가지의 일정계획 문제를 고려하였고, 주어진 작업들의 최대종료시간을 최소화하는 것을 목적으로 하여 작업들의 순서를 결정해 주는 생산 일정계획 방법론을 개발하고자 한다.
첫 번째로, 대기시간 제약과 순서의존 준비시간이 있는 두 대의 설비로 구성된 흐름공정(two-machine flowshop)에서 작업들의 최대종료시간을 최소화하는 생산 일정계획 문제를 다루었다. 두 대의 설비로 구성된 흐름공정이란 각각의 공정이 한 대의 설비로만 이루어진 경우로서, 모든 작업들은 첫 번째 설비에서 처리가 된 후에 두 번째 설비에서 처리된다. 본 소주제에서는 최적해(optimal solution)을 구하기 위하여 분지한계법(branch-and-bound algorithm)을 개발하였다. 분지한계법에서는 최적해의 우월 성질(dominance property), 하한(lower bound) 계산방법과 발견적 기법을 이용한 상한(upper bound)을 구하는 방법을 제시하였다.
다음으로, 대기시간 제약과 순서의존 준비시간이 있는 두 단계로 구성된 흐름공정에서 작업들의 최대종료시간을 최소화하는 생산 일정계획 문제를 다루었다. 두 단계로 구성된 흐름공정이란 각각의 공정이 여러 대의 동종 병렬 설비(identical parallel machine)로 이루어진 경우로서, 동종 병렬 설비라 함은 동일한 작업을 서로 다른 기계에서 수행하더라도, 동종의 기계이기 때문에 같은 작업수행시간이 소요되는 것을 의미한다. 따라서 모든 작업은 첫 번째 공정에서 존재하는 설비 중 하나에서 처리된 후에 두 번째 공정에서 존재하는 설비 중 하나에서 처리된다. 본 소주제에서는 근사해를 찾기 위하여 기존에 개발된 발견적 기법(heuristic algorithm)들을 본 문제에 적용할 수 있도록 보정하였으며 새로운 발견적 기법들을 개발하였다.
본 논문에서 개발된 생산 일정계획 방법론의 성능은 많은 실험을 통해 기존에 개발된 방법들과 함께 비교 및 평가되었다. 특히, 실제 현장의 문제 또는 실제 현장의 상황을 반영할 수 있도록 생성된 실험 문제들을 이용하여 평가되었다. 실험 결과를 분석한 결과, 개발된 생산 일정계획 방법론은 본 논문에서 다루고 있는 문제에 대해 현실적인 시간 내에 우수한 해를 찾아낼 수 있음을 확인하였다.
