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

2012年03月15日16:56:32 本网站我要评论(2)字号：T | T | T

关键字：应用

冯大光，唐立新
东北大学物流优化与控制研究所，辽宁省制造系统与物流优化重点实验室，辽宁沈阳

沈阳农业大学理学院，辽宁沈阳

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

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

１　引　言

钢铁企业生产的板卷具有一定的高度，为改变其物理结构满足市场的需求，需要利用罩式退火炉进行退火。板卷根据的用途不同，退火时间也不同，一般需要４５天时间。罩式退火炉具有一定的高度，只要放入炉内的板卷高度之和不超过炉子的高度，多个板卷就可以叠放，同时进行退火，同时结束退火。多个板卷同时进行退火时，以其中退火时间较长板卷的退火时间作为共同的退火时间，同时退火的板卷称为批。需要退火处理的板卷往往很多，而罩式退火炉的数量又有限，所以如何对板卷进行分批，使得进行炉子充分利用是一个迫切需要解决的问题。在进行组批时，应尽量使炉子空余总量较小，并且不能把退火时间相差较多的板卷放在一起，避免加热燃料的浪费和待退火板卷库存的增加，对于国家提倡的创建“节约型社会” 具有十分重要的意义。

登录网站后可下载文件

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

相关阅读: