Data-driven branching and selection for lot-sizing and scheduling problems with sequence-dependent setups and setup carryover

摘要

The capacitated lot-sizing and machine scheduling problem with sequence-dependent setup time and setup carryover is a challenging problem with a wide application in industries. For the problem, two mixed integer programming models are proposed in order to explore their relative efficiencies in obtaining optimal solutions and linear programming relaxation lower bounds. Furthermore, due to the fact that the complicating constraints involve pairs of items (the sequence-dependent setups) and pairs of consecutive periods (the setup carryovers), making it difficult to decompose the problem per item or per period, we instead present a Dantzig-Wolfe decomposition reformulation per machine to improve lower bounds. We propose a branching and selection method to solve the problem, in which a collection of variables rather than individual variables are put into a data-driven process to generate useful information which is then adopted in the branching and selection process. Extensive numerical experiments show that the proposed algorithm can obtain numerically near-optimal solutions for small-scale problems and outperforms CPLEX and other heuristics in terms of both solution quality and runtime when the scale of instances increases. More experiments have been conducted to extract some insightful features related to the model and algorithm.