Timed route approaches for large multi-product multi-step capacitated production planning problems

Abstract 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.