k-Shifts算法在一类批量计划编制中的应用

分析了冶金行业常见的一类批量计划编制问题,给出了这类组合优化问题的数学模型;分析并证明了传统k-Opt算法不适合这类非对称性组合优化问题,提出将1-Shift算法扩展为k-Shifts算法,为求得近优解提供保证;缩小了k-Shifts算法的搜索空间,大大降低了k-Shift算法时间复杂度;改进了优化目标评价函数,大幅度提高求解性能。改进后的算法成功地解决了这一类NP问题,实验证明了在多项式时间复杂度内可以求出近似于问题全局最优值的解。