A multi-chip package (MCP) is assembled by stacking homogeneous or heterogeneous chips into one final package. MCPs can easily increase the circuit density, capacity, and functionality of a package or device without significantly increasing the cost. Therefore, demand on MCPs is rapidly increasing for mobile or digital devices. However, MCP assembly process repeat similar assembly operations as many as the number of chips to be assembled. The assembly machines are shared by the assembly operations for chips of different layers. Furthermore, since some chips are commonly used for different MCP products or different chip layers of a MCP product, the stock of chips should be properly supplied for the assembly operations for each chip layer of each MCP product. The complexity due to reentrant job flows and chip allocation for the assembly operations is further amplified in an MCP assembly line by the large number of similar assembly machines at each assembly process step such as die attach and wire bonding. In this thesis, we consider a unique scheduling problem for an MCP assembly line. To address the complexity, we decompose the scheduling problem into two subproblems, chip stock allocation and machine capacity allocation problems.
The chip stock allocation problem should determine how much of the chips of each type in stock should be allocated for lots for different MCP products in different assembly stages so as to meet the daily production requirements of each MCP product. To define the problem, we first develop a mixed integer programming model. A major challenge for solving the problem is with the fact that each lot, even for the same product, has different number of packages. This means that each lot requires different number of chips and individual lots should be considered for scheduling decisions. However, since there are more than several thousands of lots in progress, the complexity of handling individual lots is intractable. We there propose two heuristic procedures to solve the problem efficiently. First, we redefine the problem based on the flow of chips rather than the flow of individual lots. This approximation simplifies the optimization model significantly but captures overall job flows. After solving the problem based on chip flows, we convert the optimal chip flows into flows of lots. The chip allocation decision is also accordingly accommodated. An alternative method is to decompose the problem by each time bucket. We solve the chip allocation problem for each time bucket. We report experimental results on the two proposed procedures by using realistic data from the industry.
Once the chip allocation decision is made, we should determine how the parallel machines at each stage should be allocated for assembly operations for the lots of different products in different assembly steps. While the daily production requirements imposed by the upper level production planning system is important, the number of setups should not exceed the capacity of the setup technical staffs. We propose three strategies of allocating the machine capacity to the assembly operations, one for expediting assembly operations for products behind the schedule, second for preventing excessive setups by using the notions of virtual lots, the last one that combines the two strategies. Once we determine the strategy for allocating the parallel machines to the assembly operations of different lots, simple dispatching rules are used for final scheduling. We experiment the proposed scheduling methods based on the machine capacity allocation strategies and compare the performances with those by conventional dispatching rules that do not have explicit machine capacity allocation strategies.
Finally, we examine the problem of converting the chip allocation decision based on the total number of chips in progress into the one based on lots. We formulate this problem as an optimization problem similar to a transportation problem and propose a Lagrangian relaxation-based solution procedure. We propose two Lagrangian heuristics. We experiment the performance of the proposed methods.
멀티칩 패키지(MCP, multi-chip package)는 동종 또는 이기종의 칩을 하나의 패키지에 쌓아서 조립하는 복합칩이다. 멀티칩 패키지는 적은 비용 증가로 패키지의 용량이나 성능을 증가시킬 수 있는 장점이 있다. 하지만 멀티칩 조립 공정은 유사한 조립 작업을 조립되는 칩의 수량만큼 반복한다. 조립 설비는 다른 제품의 조립 작업뿐만 아니라 같은 제품의 다른 층의 조립 작업과 공유된다. 더욱이 칩이 다른 멀티칩 제품 또는 같은 제품의 다른 층에 사용되는 경우가 빈번하기 때문에, 모든 멀티칩의 각 층의 조립 작업을 위해 적절하게 공급 되어야만 한다. 재방문 공정 흐름과 칩의 배분에 의한 문제의 복잡도와 함께 각 공정의 이기종 병렬 설비로 인해 복잡도가 크게 확대된다. 본 논문에서는 일정 계획에 관한 문제를 칩의 배분 문제와 설비 용량 할당 문제로 분할하여 접근한다.
칩 배분 문제는 창고 재고 칩을 일자별 생산 요구를 만족 시키기 위해 서로 다른 종류의 멀티칩에 어떻게 할당시킬 것인가를 결정하는 문제다. 이 문제를 정의하기 위해, 우선 정수 계획법에 기반한 수리 모형을 제시한다. 이 접근 방법의 가장 큰 어려움은 같은 제품의 로트라 하여도 로트에 따라 로트의 패키지 수량이 다르다는 것이다. 이것은 각 로트가 서로 다은 칩을 요구하기 때문에 개별 로트 단위로 일정 계획 문제를 접근해야 한다는 것이다. 하지만 현재 공정중인 로트가 수천개 이상으로 매우 많기 때문에, 개별 로트를 기준으로 문제를 접근하는 것은 불가능하다. 이에 따라 우리는 문제를 효과적으로 접근하기 위해 2 가지 방법을 제안한다. 첫 번째 방법은 로트 단위의 접근 방법 대신에 개별 패키지 별 흐름에 기반한 재정의 방법이다. 이 접근 방법은 최적화 모델을 단순화 시키지만 문제에 영향을 미치는 여러 요소들을 고려할 수 있다. 패키지 단위의 흐름을 해결한 이후, 실제 투입은 로트 단위로 일어나기 때문에 시간대별 칩 투입 요구를 로트 단위로 환산하는 최적화 문제를 해결해야 한다. 다른 접근 방법은 배분 문제를 각 시간 단위별로 나누는 것이다. 실제 칩의 배분은 로트 단위로 일어나기 때문에 로트 단위의 흐름을 이용하면서 문제의 크기를 줄이는 방법이 시간대별 접근 방법이다. 제안된 접근 방법에 대해 실제 데이터를 이용하여 실험하고 결과를 비교하였다.
칩의 배분 문제가 해결과 함께 설비의 사용 문제를 풀어야 한다. 설비의 사용은 멀티칩 생산 라인이 이기종 병렬 설비로 이루어져 있고, 각 제품별로 조립 공정을 위해 공정 재방문이 일어나기 때문이다. 각각의 공정 재방문에 따라 제품별 공정 설비의 공유와 제품 내의 조립 차수별 설비 공유가 발생한다. 따라서 효과적인 설비 공유 문제 해결 방법이 필요하다. 설비 공유 문제의 해결에서 상위 계획 시스템에서 제시하는 일자별 생산 계획을 준수하는 것뿐만 아니라, 과도한 설비 교체 횟수를 지양하는 설비 운영 방법이 필요하다. 왜냐하면 설비 교체 요원의 능력을 넘어서는 과도한 설비 교체는 불가능하기 때문이다. 이를 위해 본 연구에서는 3가지 설비 운영 방법을 제시하였다. 첫째는 일정 계획의 지연을 방지하고, 지연된 제품에 대해 생산 속도를 향상 시키는 방법이고, 둘째는 설비 교체 횟수의 절감을 위해 같은 조립 차수와 같은 공정 단계의 같은 제품을 하나의 가상 로트로 만드는 방법, 그리고 두 방법의 혼합 방법을 제시하였다. 병렬 설비에 대한 설비 운영 방법이 결정되면, 간단한 선입 선출 방법과 같은 간단한 설비 운영 방법을 통해 최종 스케줄을 제시할 수 있게 된다. 제시된 방법들을 비교하기 위해 기존의 알려진 10개의 디스페칭 방법과 비교하였다.
마지막으로 칩 단위의 수량을 로트 단위로 변환하는 문제를 수리 모형을 제시하고 이의 해결 방법을 제시하였다. 이 수리 모형은 수송 문제와 유사한 형태를 가지며, 이 문제의 해결을 위해 라그랑지안 릴렉세이션 기반의 2가지 휴리스틱 절차를 제시하였다. 독특한 문제 특성을 갖고 제시된 기존의 연구 방법이 없기 때문에 수리 모형 기반의 최적해와 제시된 두 방법을 비교 하였다.
