Column generation-based algorithm for preemptive relaxation formulation of coordinated seru scheduling and distribution problems

This article addresses scheduling problems to minimize the total cost for coordinated seru scheduling and distribution problems, in which seru is a creative production mode originating from Japan and brings inspiring benefits in practice. The problem is formulated as a general 0–1 integer programming model G-(0,1), which is reformulated into a mixed integer linear programming model by the preemptive relaxation formulation PF-(MILP). After analysing mathematical properties, the proof that PF-(MILP) is an exact formulation of G-(0,1) is provided. Subsequently, a column generation-based algorithm is designed, in which the master problem assigns jobs to serus, and independent pricing subproblems determine the corresponding coordinated optimal schedule. Dual variables from the master problem are employed to compute reduced costs to generate new columns. Leveraging the Monge property of the coefficient matrix, each pricing subproblem is solved efficiently by dynamic programming. Computational experiments indicate that the performance of PF-(MILP) is better than G-(0,1), and column generation-based algorithm is efficient and scalable.