修改D-W分解求具有需求时间窗和投机性成本的批量问题

Using modified D-W decomposition to solve lot sizing problem with demand time windows and speculative cost

研究多产品具有能力约束、需求时间窗、允许延期交货和投机性成本的批量问题.分析无能力约束凸包极点的特征,采用修正的Dantzig-Wolfe分解对原问题进行等价变换.使用列生成获得下界,同时采用启发式分支定界寻找近优解.对随机算例进行了测试与比较,计算结果表明上界与下界之间的间隙非常小;另外分析了当能力参数和订单规模变化时解的质量和计算时间.

This research concerns a deterministic multi-item lot-sizing problem with capacity constraints, demand time windows, backlogging and speculative cost. The extreme points of the uncapacitated lot size polytope are analyzed, and an equivalent mixed-integer programming formulation is developed by applying modified Dantzig-Wolfe decomposition to the original problem. The lower bound is obtained by column generation processing. Furthermore, a heuristic branch and bound algorithm is developed to find near optimal solution. Numerical experiments generated randomly are tested and compared. The result shows that the gaps between the lower and upper bounds are very small. Moreover, the solution＇s quality and algorithm＇s run-time are analyzed when varying the capacitated parameter and number of orders.