新工件到达锁定初始调度的单机重调度问题

• 作者: 伦淑娴 郭家喜 郭艳东
• 来源期刊: 渤海大学学报（自然科学版）
• 学科: 工学
• 关键词: 重调度 单机 新工件 NP难
• 年，卷（期）: 2015,（2）
• 所属期刊栏目: 信息科学与工程
• 页码范围: 168-174
• 页数: 7页
• 分类号: TP391.41
• 字数: 5469字
• 语种: 中文

摘要

研究了新工件到达锁定初始调度的单机重调度问题。即有一组带有不同释放时间的初始工件已经按照最小化完成时间和的优化目标调度完毕，形成初始调度且已锁定，此时有一组释放时间为零的新工件到达，且需要插入初始调度进行加工，其优化目标为最小化新工件的完工时间和。文中研究了新工件的加工过程可中断和新工件的加工过程不可中断，共2类新工件到达锁定初始调度的单机重调度问题。分析了重调度问题的复杂性，针对第一类重调度问题提出了多项式算法并证明了其最优性。证明了第二类重调度问题为NP完全问题，提出了一个多项式算法，并证明了该算法的有效性和最优解的特征，解决了企业实际问题并进一步丰富了重调度理论。

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	伦淑娴	渤海大学新能源学院	60	328	9.0	15.0
2	郭艳东	渤海大学数理学院	10	23	3.0	4.0
3	郭家喜		2	1	1.0	1.0