Forming and scheduling jobs with capacitated containers in semiconductor manufacturing: Single machine problem |
| |
Authors: | Fehmi Tanrisever Erhan Kutanoglu |
| |
Institution: | (1) Red McCombs School of Business, The University of Texas at Austin, Austin, TX 78712, USA;(2) Operations Research and Industrial Engineering, The University of Texas at Austin, Austin, TX 78712, USA |
| |
Abstract: | 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. |
| |
Keywords: | Batching Scheduling Dynamic programming Job formation Multi-order jobs |
本文献已被 SpringerLink 等数据库收录! |
|