新工件到达锁定初始调度的单机重调度问题
郭艳东1
郭家喜2
伦淑娴3
1.渤海大学 数理学院,辽宁 锦州,1210132.北方华锦化学工业集团有限公司,辽宁 盘锦,1240003.渤海大学 新能源学院,辽宁 锦州,121013
摘要：研究了新工件到达锁定初始调度的单机重调度问题。即有一组带有不同释放时间的初始工件已经按照最小化完成时间和的优化目标调度完毕，形成初始调度且已锁定，此时有一组释放时间为零的新工件到达，且需要插入初始调度进行加工，其优化目标为最小化新工件的完工时间和。文中研究了新工件的加工过程可中断和新工件的加工过程不可中断，共2类新工件到达锁定初始调度的单机重调度问题。分析了重调度问题的复杂性，针对第一类重调度问题提出了多项式算法并证明了其最优性。证明了第二类重调度问题为NP完全问题，提出了一个多项式算法，并证明了该算法的有效性和最优解的特征，解决了企业实际问题并进一步丰富了重调度理论。
关键词：重调度单机新工件NP难
分类号：TP391.41(计算技术、计算机技术)
资助基金：辽宁省自然科学基金(No2014020143)辽宁省自然科学基金(No20131001)辽宁省自然科学基金(No201202003)新世纪优秀人才支持计划(NoNCET-11-1005)辽宁省第一批次科学计划项目(No2011402001)辽宁省教育厅项目(NoL2014444)辽宁省教育厅项目(NoL2012401)
论文发表日期：2015-01-01
在线出版日期：2025-08-15（本平台首次上网日期，不代表文献的发表时间）
页数：7( 168-174 )
英文信息