工件具有不同尺寸单台批处理机的调度问题

冯大光^1,2，唐立新¹

1. 东北大学物流优化与控制研究所辽宁省制造系统与物流优化重点实验室2. 沈阳农业大学理学院

摘 要：n个工件要在一台有高度限制的批处理机上分批进行加工,工件j的加工时间和高度分别为pj和sj,批的加工时间为批中加工时间最大的工件的加工时间,每批加工时,机器的剩余量为批处理机的高度与批中工件的高度和之差,目标函数最小化机器空余总量和工件总完成时间,该NP-难问题源于钢铁企业的罩式退火炉调度问题。基于部分工件分批性质,提出贪婪算法;提出工件SPT顺序的最优分批-动态规划算法,并对两种算法进行了比较。为了进一步检验算法,把动态规划算法应用于总完成时间最小化问题,与已有算法进行了比较;根据相邻批的工件加工时间的取值,提出分批修改规则,并与动态规划结合实现局域搜索算法（DPLS）,通过仿真实验表明DPLS算法非常有效。

关键词：罩式退火炉;批处理机;贪婪算法;动态规划;局域搜索;