Multi-level lot-sizing and job shop scheduling with lot-streaming: Reformulation and solution approaches

This paper addresses a multi-level lot-sizing and job shop scheduling problem with lot-streaming. In the multi-level production system, workstations receive materials from the lower level, and after some operation, materials are shipped to the next level. Hence, establishing a material balance between the different levels is the most challenging part of multi-level production planning and scheduling. The material balance can be performed with or without lot-streaming. Lot-streaming effectively enables consecutive operations to overlap by splitting a processing lot into several sub-lots. In small-bucket time models, this capability is taken into account by establishing the material balance in each small unit of time (micro-period), which makes the models computationally expensive. In the present work, a novel and much less complicated big-bucket time formulation has been developed, which incorporates lot-streaming considering sequence-dependent setup times and capacitated machines. Computational experiments affirm the promising results of the proposed model compared to the well-known models in the literature. Moreover, two efficient heuristics have been developed for solving larger-size problems. First, the fix-and-relax algorithm as a constructive heuristic is combined with the fix-and-optimize algorithm as an improvement heuristic. Next, a decomposition heuristic is proposed using mixed-integer programming (MIP) and constraint programming (CP) in the master and sub-problem, respectively. The computational results show that the proposed heuristics are very efficient, even in solving large-sized problems.