We examine a batch machine scheduling problem for multi-chip semiconductor packaging. Since the batch machines are located between two bottleneck processes, it is vital to minimize the maximum lateness under the restriction on the job release dates. The problem has incompatible job families and agreeable release dates and due dates. We first show that a specific class of job sequences within each batch is optimal. Based on the property, we propose heuristics for the single- and parallel- machine cases. We present computational performance of the proposed heuristics.
본 논문은 멀티칩 반도체 패키징 중 뱃치공정의 스케쥴링에 관한 문제를 연구한다. 멀티칩 반도체의 특성상 고려가 되는 뱃치공정은 두 병목공정 사이에 존재하게 되어, 병목공정에서 요구하는 납기를 준수하는 것, 그 중에서도 납기 위반 최대치를 최소화 하는 것이 중요하다. 특히 뱃치공정이 서로 합치적인 작업가용시점과 납기를 가지며, 서로 다른 작업군끼리는 동일한 뱃치를 구성할 수 없는 특성을 이용하여 각 뱃치내의 작업들의 순서에 관한 최적조건을 제시하였다. 실제 현장의 문제가 뱃치공정이 두 개의 연속된 공정으로 존재하게 된 상황이기 때문에, 우선 하나의 뱃치공정에서 단일 장비일 경우와 복수 동일 장비일 경우의 문제를 위한 휴리스틱 알고리즘을 제안하고, 그 결과를 바탕으로 작업종료시점 제약이 있는 상황에서의 두 개의 연속된 뱃치공정 문제를 위한 휴리스틱 알고리즘을 제안하였다. 제안된 휴리스틱 알고리즘은 실험을 통하여 기존의 휴리스틱 알고리즘과 성능을 비교한 후, 제안된 알고리즘이 기존의 알고리즘보다 항상 좋은 결과를 준다는 것을 보였다.
