This dissertation focuses on design and scheduling problems in a parallel-line assembly system producing multiple product types. Each line in this system can be regarded as an assembly system, in which a series of operations is processed while the products are moved on a conveyor system. These problems can be found in an air conditioner manufacturing system composed of parallel assembly lines that produce multiple product types. In this dissertation, we develop algorithms for a design problem in an assembly system and then, we develop scheduling algorithms for parallel assembly manufacturing systems with multiple product types.
First, we focus on a design problem in an assembly system composed of parallel assembly lines that produce multiple product types. In the assembly system, different types of products can be assigned to the same line and each product type can be assigned to multiple lines. In the design problem, therefore, we consider decisions on the assignment of product types to the assembly lines including production quantities of each product type on each line. The cycle time of each line or the speed of the transport system of each line can be determined by the assignment. We formulate the problem to a non-liner mixed integer model and develop an algorithm based on Benders’ decomposition approach as well as heuristic algorithms for the problem with the objective of minimizing the weighed sum of workload imbalance of the lines. Here, the workload imbalance of a line is measured by the time differences between the cycle time and processing times of the operations of the product types on the line. Note that this weighted sum represents the sum of idle times of the assembly lines, or the time loss (loss of capacity) of the lines, which are caused by assigning product types requiring different processing time to the same line.
Secondly, we focus on a scheduling problem in an air conditioner manufacturing system composed of multiple parallel assembly lines. There are multiple orders to be processed in this system, and each order is specified by the product type, the number of products to be processed and the due date. Each product is composed of two types of sub-assemblies, one unit of an external sub-assembly and one or more units of an internal sub-assembly. In the system, the parallel assembly lines are not identical and certain lines are designated for certain product types. We consider the scheduling problem with the objective of minimizing total tardiness of orders. We suggest four heuristic algorithms, two two-phase algorithms and two bottleneck-focused algorithms with several variations.
Performance of the suggested algorithms are evaluated through series of computational tests on test problems which are obtained from data of real manufacturing systems 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 dissertation give very good solutions in a reasonable amount of computation time. In addition, the design and scheduling algorithms suggested in this dissertation can be easily implemented in real manufacturing system if they are modified slightly to cope with the practical situations.
본 논문에서는 병렬 조립 시스템에서의 설계 문제 및 작업 스케쥴링 문제를 다르고 있다. 병렬 조립 시스템이란 일반적인 다수의 조립 라인으로 구성된 시스템이다. 각각의 조립 라인에서는 컨베이어 시스템에서 제품이 순차적으로 조립되어 완제품을 생산한다. 제품이 순차적으로 위치하고 있는 각 기계들에서의 해당 공정을 통하여 이루어지며 마지막 기계에서의 해당 공정이 완료 될 때 그 제품의 작업이 완료 된다. 또한, 고려한 병렬 조립 시스템에서는 다수의 제품들이 생산되고 있다. 대표적인 병렬 조립 시스템으로는 PCB (printed circuit board), TV, 냉장고, 세탁기 및 에어컨디션(air conditioner) 생산 시스템들이 있다. 본 논문에서는 에어컨디션을 생산하는 병렬 조립 시스템을 대상으로 실제 생산 시스템에서 발생하는 시스템 설계 문제 및 작업 일정계획 문제를 고려하였다. 우선, 생산할 제품들을 생산라인에 할당하는 문제, 라인에 할당된 제품들의 생산량 결정 및 조립 라인의 속도를 결정하는 조립 라인 설계문제에서 이러한 의사결정으로 발생하는 라인별 작업물량의 불균형(workload imbalance)을 최소화 하기 위한 해법을 개발하였고 다음으로 주어진 작업들의 납기지연을 최소화하는 병렬 조립 시스템 일정계획 문제에서 작업들의 순서를 결정해 주는 알맞은 해법을 개발하였다.
먼저, 논문의 2장에서는 병렬 조립 시스템 설계에 관한 문제를 다루었다. 본 장에서는 생산할 제품들을 생산라인에 할당하는 문제, 할당된 제품들의 생산량 결정 및 조립 라인의 속도를 결정한다. 이러한 결정으로 인해 발생되는 라인별 작업물량의 불균형(workload imbalance)을 최소화하는 조립 라인의 설계문제를 다루었다. 본 장에서는 최적해(optimal solution)를 구하기 위하여 벤더즈 분해 방법(Benders Decomposition algorithm)을 개발하였다. 먼저 본 장에서는 원 문제를 한 개의 주문제(master problem)와 한개의 서브문제(sub-problem)로 나누고 각각의 문제에서 하한(lower bound) 및 상한(upper bound) 계산 방법들을 개발하여 적당한 시간 내에 병렬 조립 시스템에서의 설계문제에 대한 최적해를 구할 수 있었다. 큰 사이즈의 문제의 경우 휴어리스틱(heuristic) 방법론을 제안하여 해를 구할 수 있었다.
다음으로, 논문의 3장에서는 대표적인 병렬 조립 생산 시스템인 에어컨 생산 시스템(air conditioner manufacturing system)에서의 일정계획 문제를 다루었다. 다만, 일정계획 문제의 목적함수는 작업들의 최대 종료시간이 아닌 작업들의 총 납기 지연을 최소화 하는 것이다. 본 장에서는 4개의 휴어리스틱(heuristic) 방법을 제안하였다. 2개의 두단계 방법(two-phase algorithms) 과2개의 병목중심 방법(bottleneck-focused algorithms) 들을 이용하여 적당한 시간 내에 일정계획 문제의 스케쥴을 구할 수 있었다.
본 논문에서 개발된 최적화 방법들과 휴리스틱 방법들은 많은 계산 실험을 통하여 그 성능을 평가되었다. 특히, 실제 현장의 문제 또는 실제 현장의 상황을 반영할 수 있도록 생성된 실험 문제들을 이용하여 평가되었다. 평가로부터 현실적인 시간 내에 논문에서 다루고 있는 병렬 조립 시스템의 시스템 설계 및 작업 스케쥴링에 대한 우수한 해들을 찾을 수 있음을 확인하였다.
