Efficient Algorithms for Scheduling Semiconductor Burn-In Operations

TLDR

A batch processing machine can process up to B jobs simultaneously, with batch processing time equal to the longest job time in the batch. The study focuses on scheduling semiconductor burn‑in operations and introduces efficient dynamic‑programming algorithms to minimize various performance metrics on a single batch processing machine. Dynamic‑programming techniques are used to design algorithms for minimizing performance measures on a single batch processing machine, and heuristics with worst‑case error bounds are proposed for parallel identical machines. The heuristics for parallel identical machines achieve provable worst‑case error bounds.

Abstract

In this paper, we study the problem of scheduling semiconductor burn-in operations, where burn-in ovens are modeled as batch processing machines. A batch processing machine is one that can process up to B jobs simultaneously. The processing time of a batch is equal to the largest processing time among all jobs in the batch. We present efficient dynamic programming-based algorithms for minimizing a number of different performance measures on a single batch processing machine. We also present heuristics for a number of problems concerning parallel identical batch processing machines and we provide worst case error bounds.