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

Rescheduling for new jobs on single machine with locked initial jobs

作　　者：郭艳东[1] 郭家喜 伦淑娴[3] 

机构地区：[1]渤海大学数理学院,辽宁锦州121013 [2]北方华锦化学工业集团有限公司,辽宁盘锦124000 [3]渤海大学新能源学院,辽宁锦州121013

出　　处：《渤海大学学报（自然科学版）》2015年第2期168-174,共7页Journal of Bohai University:Natural Science Edition

基　　金：辽宁省自然科学基金项目(No:2014020143;No:20131001;No:201202003);教育部新世纪优秀人才支持计划项目(No:NCET-11-1005);辽宁省第一批次科学计划项目(No:2011402001);辽宁省教育厅项目(No:L2014444;No:L2012401)

摘　　要：研究了新工件到达锁定初始调度的单机重调度问题.即有一组带有不同释放时间的初始工件已经按照最小化完成时间和的优化目标调度完毕,形成初始调度且已锁定,此时有一组释放时间为零的新工件到达,且需要插入初始调度进行加工,其优化目标为最小化新工件的完工时间和.文中研究了新工件的加工过程可中断和新工件的加工过程不可中断,共2类新工件到达锁定初始调度的单机重调度问题.分析了重调度问题的复杂性,针对第一类重调度问题提出了多项式算法并证明了其最优性.证明了第二类重调度问题为NP完全问题,提出了一个多项式算法,并证明了该算法的有效性和最优解的特征,解决了企业实际问题并进一步丰富了重调度理论.This paper studies that some new jobs come from some new orders need to be rescheduled by in-serting into initial schedule.Where, some initial jobs with release times in the initial schedule, and then the ini-tial schedule is locked.We consider two cases of this rescheduling problem, one is the new jobs with preemptive to be processed, another is the new jobs with non-preemptive.For the first case, a polynomial time algorithm is developed, and its optimality is proofed.For the second case, NP-hardness is proofed firstly, a heuristic is de-signed following, and then a special case is solved optimal by this heuristic , at last a characteristic of optimal so-lution is showed, The theoretical results of this research can solve practical problems of enterprise and enrich re-scheduling theory.

关 键 词：重调度 单机 新工件 NP难 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]