Forming and scheduling jobs with capacitated constraints in semiconductor manufacturing: single machine problem

We study a scheduling problem motivated by the challenges observed in the newest semiconductor manufacturing wafer fabrication facilities. As wafers are larger and heavier in these wafer fabs, it is becoming more common to use specialized material handling containers that carry multiple orders coming from different customers and to schedule the containers as jobs in the fab. The system performance is a function of the completion times of orders, which ultimately depend on both (1) how the orders are assigned to such containers ("job formation"), and (2) how the containers are scheduled in the fab ("job scheduling"). The overall problem is to find the best way to form and schedule the jobs subject to complicating constraints, including the restrictions on the number of containers that can be used at one time and on the number of wafers the containers can carry. We focus on the single machine job formation and scheduling problem with the total completion time objective. We show that this problem is quite different from conventional parallel and serial batching scenarios and prove that the uncapacitated special case is polynomially solvable and the capacitated case is strongly NP-hard. We use a dynamic programming algorithm to solve the uncapacitated problem, which not only provides tight lower bounds for the capacitated problem, but also becomes a basis for a heuristic approach for the capacitated problem. The computational results show that this approach is very effective, leading to small optimality gaps that get even smaller as the problems become larger.