Batch scheduling for incompatible job families with agreeable release dates and due dates

Abstract

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.