The flow shop batch scheduling problem in a prefabricated component manufacturing system with two-dimensional bin packing constraints

This study focuses on a flow shop batch scheduling problem in a prefabricated component manufacturing system with two-dimensional bin packing constraints. In this problem, job to batch assignment, job layout and batch sequence have to be determined simultaneously to minimise the total weighted sum of the makespan and the number of active pallets. Two mixed integer linear programming models are formulated at first. Subsequently, because of the complexity of the problem, to obtain optimal or near-optimal solutions with quantifiable quality in a computationally efficient manner, two hybrid Benders decomposition frameworks (HBD_LSDR_V and HCBD_LSDR_V) are proposed by integrating the strength of decomposition scheme, local search (LS), destruction and reconstruction (DR) mechanism, and valid inequalities (VIs). The only different between the two frameworks is the decomposition schemes they employ. The first one utilises a pure Benders decomposition scheme while the second one employs a combinatorial Bender decomposition scheme. Both the two frameworks solve their master problem and subproblem alternatively until a stop criterion is met. Finally, computational results show that, HCBD_LSDR_V achieves the best overall performance among all the methods. In addition, the efficiency of LS and DR, decomposition schemes, and VIs in the two frameworks are verified.