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

• 作者: 冯大光 唐立新
• 来源期刊: 控制工程
• 学科: 工学
• 关键词: 罩式退火炉 批处理机 贪婪算法 动态规划 局域搜索
• 年，卷（期）: 2011,（3）
• 页码范围: 420-423
• 分类号: TP27
• 字数: 4014字
• 语种: 中文
• DOI: 10.3969/j.issn.1671-7848.2011.03.025

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	冯大光		1	4	1.0	1.0
5	唐立新		2	5	1.0	2.0