An approximate dynamic programming approach to wafer-lot scheduling for parallel multi-chamber equipment in semiconductor fabrication lines
研究了半导体制造中并行多腔室设备的晶圆批次调度问题，提出混合整数规划模型和近似动态规划算法，通过有效不等式和上下界方法提升求解效率，尤其适用于大规模实例。
In this paper, we address a wafer-lot scheduling problem (WLSP) for parallel multi-chamber equipment in semiconductor wafer fabrication lines. This equipment can process multiple wafers simultaneously, with each chamber handling one wafer at a time. To process a wafer, the corresponding lot must be loaded into a cassette module, which remains occupied until all wafers in the lot are processed, thereby limiting cassette module availability. Each wafer lot requires a specific process step, with target production quantities set for each step. The WLSP aims to maximise the fulfilment of these target quantities within the planning horizon while satisfying operational constraints. We show that the WLSP is strongly NP-hard and present a mixed integer programming (MIP) model based on a two-level tour structure. To enhance performance, we derive valid inequalities that strengthen the linear programming (LP) relaxation bounds of the model. In addition, we propose approximate dynamic programming (ADP) algorithms incorporating several bounding methods. Specifically, we devise three models to compute upper bounds and introduce a roll-out heuristic to obtain lower bounds. The proposed algorithms are particularly effective for larger instances. Among the upper bounding methods, the LP model with the proposed valid inequalities consistently provides the tightest bounds, demonstrating its effectiveness.