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

摘要

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