This thesis considers the scheduling problems for a two-machine flowshop of batch and discrete processors with earliness/tardiness measures. In the problems, it is assumed that each batch has the same processing time. Under this assumption, the thesis considers three different problem cases associated with three different flowshop systems including system 1 where a batch processor runs after a discrete processor, system 2 where a batch processor runs after another batch processor, and system 3 where a discrete processor runs after a batch processor.
The first problem case is investigated for a two-machine flowshop where the earliness/tardiness measure and a common due date are considered. In the case, it is assumed that each batch has the same processing time and the common due date is not set earlier than the total job processing time on the first machine. Under these assumptions, some solution properties are characterized for all the three different flowshop systems. Then, the solution properties are used to drive polynomial solution procedures for systems 1 and 2, while system3 is proved to be NP-complete and so a pseudo-polynomial procedure is derived for the system.
The second problem case deals with a scheduling problem of minimizing the weighted sum of earlinesses and tardinesses of jobs for two-machine flowshops of systems 1 and 2. In the problem, two different types related to due date are considered. One of them is called an unrestricted type where due date is not urgent to constrain the scheduling decision. The other one is called a restricted type where due date is urgent to constrain the scheduling decision. The optimality conditions for both the types are verified, based on which a polynomial time algorithm is derived.
The last problem case investigates a scheduling problem of minimizing maximum tardiness for two-machine flowshops composed of systems 1 and 3. Several solution properties are characterized for the case, base on which a dynamic programming procedure is derived.
본 논문은, 뱃치 공정이 있는 두 단계 플로우샵에서의 조기(Earliness) 또는 지연(Tardiness) 달성에 따른 작업에 대해 벌과를 부여하는 상황 아래에서 총 벌과의 합을 최소화하는 문제와 최대 지연되는 작업을 최소화 시키는 작업 일정 계획의 문제를 다루었다. 여기서 고려된 뱃치 공정은 뱃치 작업 시간이 동일한 경우와 작업되는 제품의 특성에 따라 뱃치 작업 시간이 다른 경우로 나뉘어 지는데, 전자를 중심으로 다루어 졌으며 세 가지 시스템 상황 - 개별작업 이후 뱃치 작업, 뱃치 작업 후 뱃치 작업, 뱃치작업 후 개별 작업 - 에서 문제를 고려하였다.
첫째, 세가지의 시스템 상황 각각에 대해 작업들이 공통의 납기를 갖는 경우에 조기벌과와 지연 벌과의합을 최소화 하는 일정 계획 문제를 고려하였다. 처음의 두가지 시스템 상황하에서는 최적의 해를 찾는 알고리즘을 개발하였고, 마지막 시스템 상황의 문제에서는 NP Complete임을 증명하였고, 이에 대한 현실적인 문제들에 대해서는 최적해를 제한된 시간에 찾을 수 있는 DP(Dynamic Program)알고리즘을 개발 하였다.
둘째, 처음 고려된 문제를 확장하여 공통 납기 하에서 각 각의 작업들에 대해 조기 벌과와 지연 벌과에 가중치를 부여한 벌과의 합을 최소화하는 일정 계획 문제를 분석하였다. 이에 대한 발견적 기법을 제시하였으며, 해법에 대한 계산 효율을 알기 위해 예시적인 문제와 알고리즘 실험 결과를 제시하였다.
세째, 개별 작업 설비와 뱃치 설비로 구성된 Flowshop에서 개별 작업의 납기가 서로 다른 경우에 최대로 지연되는 작업의 시간을 최소화 하는 문제를 다루었다. 이 경우에서는 작업의순서가 조기 납기를 갖는 작업 순서로 해야 됨을 보였고, 뱃칭 방법을 제시하는 DP 알고리즘을 개발하였다.
본 논문은 주로 단일 설비에서 다루던 문제를 다양한 시스템 환경의 Folwshop으로 확대하여 최적해의 성질을 규명하고, 이에 따른 해법들을 연구 제시 함으로써 보다 복잡한 환경과 현실적인 상황의 모형 연구의 시발점이 될 수 있다.
