考虑学习效应的最小化延误总时间的单机批次排序问题

来源期刊：控制与决策2019年第12期

论文作者：胡金昌 吴耀华 吴颖颖 杨栋

文章页码：2708 - 2712

关键词：批次排序问题;单机;学习效应;动态规划;模拟退火算法;最小化延误总时间;

摘    要：一些生产场景中,工件以批次作业的形式被安排生产,工件批量大、加工工序基本相同,所以标准工时相同,而且实际加工时间会受到学习效应的影响.为此,讨论学习效应的最小化延误总时间的单机批次排序问题,对该问题建立数学模型.该问题属于NP-hard问题,采用动态规划算法（DP）和模拟退火算法（SA）求解该问题,通过实验分析不同规模时DP的执行时间与SA的执行时间和求解误差的变化趋势,比较SA与其他实践中常用的经典规则的求解效果.最后得出DP适合批次数小于13的小规模问题,可以得到精确解;与经典规则相比, SA至少可以使目标函数降低20%,表明SA算法具有有效性. SA解决大规模问题时效果较优,并得出SA的执行时间和误差随着控制参数改变的变化趋势.