Two-stage assembly flowshop scheduling problems are investigated in this thesis. In a general two-stage assembly flowshop, to complete each job, multiple components are fabricated by in-house machines or procured from outside suppliers at the first stage. After all components of each job are prepared at the first stage, the components are assembled at the second stage. When the available times of outsourced-components can be completely adjusted in favorable to assembly schedule, it is not necessary to consider the outsourcing components any more. However, if not, then the fabrications of in-house components and the subsequent final-assembly should be scheduled after due consideration of the arrival times of outsourced-components.
Two types of two-stage assembly scheduling problems are considered in this thesis. The first type of problem has an outsourced-component whose available time should be considered as constraint for whole scheduling. In the problem, each job is assembled with two types of components for which makespan is the objective measure. An in-house dedicated-machine fabricates one type of component and the other type of component is outsourced subject to its own arrival time, which should be considered as constraint for whole scheduling. It is proved that the problem is NP-hard in the strong sense and some solution properties are characterized. Based on the solution properties, three heuristic algorithms and a branch-and-bound algorithm are derived. Through numerical experiments, it is shown that the performances of the derived algorithms are quite good. For the same problem, four ρ-approximation algorithms and their tight worst-case error bounds are derived. Moreover, one of them is modified to give an improved worst-case performance ratio of 3/2. It is also proved that the worst-case performance ratio is best possible.
The other type of problem is related with the case in which there is not any component available time constraint. The problem is a two-stage assembly scheduling where dedicated machines fabricate all the multiple components in the shop and the objective measure is the total completion time. Since a reference work in the literature has already proved the NP-hardness of the problem and provided some simple heuristics and a branch-and-bound algorithm, this thesis focuses on derivation of comparatively better algorithms. In this thesis, several solution properties and lower bounds are derived. Four heuristics and a branch-and-bound algorithm are constructed based on the solution properties and lower bounds. The performances of the algorithms are compared with the reference one by numerical experiments. From the comparison, it is concluded that the effectiveness of the heuristics of this thesis is much better than that of previous research.
본 논문은 2 단계 조립 일정계획 문제를 주제로 고려하고 있다. 일반적인 2 단계 조립 일정계획 문제에서는 제1단계에서 다수개의 부품을 준비한 후, 제2단계에서 이 부품들을 조립함으로써, 여러 개의 작업들 중에서 하나의 작업이 완결된다. 제1단계에서 이루어지는 부품준비는 조립업체 내부에서 자체적으로 생산하거나, 외주(Outsourcing)로 조달하거나 혹은 내부생산과 외주조달을 적절히 혼합하여 사용할 수 있다. 조립업체가 부품을 외주로 조달하는 경우에 조립업체의 일정계획에 적합하도록 외주부품의 조달시점을 조절할 수 있는가 혹은 그렇지 못한가에 따라서 문제 상황이 확연히 구별된다. 즉, 조립업체가 외주부품의 조달시점을 조절할 수 있다면, 조립업체의 입장에서 자사의 조립일정계획에 적합하도록 외주조달시점을 외주업체에게 통보하면 되므로, 조립일정계획 수립에 외주부품 조달시점이 제약으로 작용하지 않는다. 그러나, 외부 부품업체가 외주조달 부품의 조달시점을 일방적으로 결정하고, 조립업체는 이를 수용해야 한다면 조립업체는 외주부품 조달시점을 조립업체 일정계획 수립에 제약조건으로 고려해야 한다. 일반적으로, 이와 같은 외주부품의 조달시점 결정은 조립업체와 외주 부품업체 중에서 보다 큰 협상력을 보유한 업체에 의해 이루어지고, 업체간 협상력의 크기는 해당업체가 보유한 핵심기술이나 업체의 규모 등에 좌우되는 것으로 보고되고 있다.
본 논문에서는 부품 조립 일정계획을 수립할 때, 외주부품의 조달시점을 제약으로 고려해야 하는 경우와 그렇지 않아도 되는 경우로 대별하여, 두 가지 유형의 2 단계 조립 일정계획 문제를 고려하였다. 첫 번째 유형의 문제에서는 두 개의 부품을 조립하여 하나의 작업을 완결하면서, 최대작업완료시간 (Makespan)을 최소화하는 상황에서, 하나의 부품은 내부에서 자체적으로 생산하고, 나머지 하나의 부품은 외주조달 시간제약을 갖는 형태로 외부에서 조달하는 상황을 고려하고 있다. 일차적으로, 문제의 난이도가 비다항(NP-hard)임을 증명하였고, 최적해가 될 수 있는 특성(Solution Property)들을 규명하였다. 이러한 최적해 특성들을 토대로 발견적 해법(Heuristic)들과 분지한계 해법(Branch-and-bound Algorithm)을 제시하고, 수치실험을 통해 해법들의 성능이 양호함을 확인하였다. 또, 동일한 문제에 대해 최악오차한계분석(Worst-case Analysis)을 수행하여, 최악오차한계(Worst-case- Error Ratio)가 2인 발견적 해법들과, 이를 3/2으로 개선한 발견적 해법을 제시하고, 이 발견적 해법들의 오차한계가 각각 최선한계(Best Possible)임을 규명하였다.
두 번째 유형의 문제에서는 외주부품이 없는 경우, 다수개의 부품을 부품별로 특화된 기계(Dedicated Machine)에서 자체적으로 생산해서 조립하는 2단계 조립 일정계획 상황에서 총작업완료시간(Total Completion Time)을 최소화하는 것을 목적으로 하고 있다. 동일한 문제 상황에 대해 보다 일반적인 목적식인 총가중작업완료시간(Total Weighted Completion Time)을 최소화하는 연구가 이미 이루어져 있기 때문에, 본 논문에서는 상대적으로 효과적인 해법 개발을 목적으로 하였다. 최적해가 갖는 특성들을 규명하였고, 이들에 기반하여 발견적 해법들과 분지한계 해법을 제시하였다. 수치실험을 통해 해법들의 성능을 기존 연구와 비교함으로써 두 가지 결론에 도달하였다. 첫째로, 최적해를 제공하는 분지한계 해법은 본 연구의 결과가 전체적으로 근소하게 우세하지만 충분한 개선이라고는 할 수 없으므로 추가적인 성능개선 연구가 필요하다는 것이다. 반면, 근사해를 도출하는 발견적 해법의 경우에는 기존 연구와 대비하여 본 연구의 결과의 개선 정도가 통계적으로 유의미함을 확인하였다.
