Timed route approaches for large multi-product multi-step capacitated production planning problems
针对半导体制造中多产品多步骤的产能受限生产规划问题，提出定时路径概念和列生成算法，在工业数据上平均减少92%计算时间，部分案例提速超千倍。
In complex systems that can be found in semiconductor manufacturing, linear programming production planning models must consider many products with hundreds of production steps to be performed on hundreds of machines. To deal with this complexity and solve problems with flexible lead times in a reasonable CPU time, the new concept of timed route is introduced. In a timed route, each production step of a product is associated with a specific time period. A new formulation relying on timed routes is then proposed. Because the number of feasible timed routes can grow exponentially, a column generation approach is presented. Algorithms to generate relevant timed routes are given, and their complexity analyzed. Computational experiments on industrial data with different lead time profiles, fixed lead times and flexible lead times, show that computational times are very significantly reduced when using our approaches, by 92% on average and even divided by more than 1,000 in some cases. The advantages of timed routes are also discussed.