锁定初始调度的紧急工作单机重调度问题  

Rescheduling for Rush Jobs on Single Machine with Loads Locked Original Scheduling

作　　者：郭艳东[1] 黄敏[1] 王庆[1] 

机构地区：[1]东北大学流程工业综合自动化国家重点实验室,辽宁沈阳110819

出　　处：《东北大学学报（自然科学版）》2013年第5期628-631,共4页Journal of Northeastern University(Natural Science)

基　　金：国家自然科学基金资助项目(71071028;70931001;71021061;61070162;71171040);国家杰出青年科学基金资助项目(61225012);高等学校博士学科点专项科研基金优先发展领域课题(20120042130003);高等学校博士学科点专项科研基金资助项目(20110042110024;20100042110025);工信部物联网发展专项资助项目;中央高校基本科研业务费专项资金资助项目(N110204003)

摘　　要：对单机环境下紧急工作的重调度问题进行了研究.初始调度中工作带有到达时间,目标为最小化初始工作的等待时间和;重调度目标是在初始调度锁定的情况下,将紧急工作插入初始调度,最小化紧急工作的最长等待时间.建立了RRLS(rescheduling rush jobs with loads locked on single machine)问题模型,然后证明了RRLS问题是NP难问题.根据问题性质和特点提出了有效的启发式算法,并给出了算法的时间复杂度.通过实例证明了算法的最优性条件.Rescheduling problem for rush jobs on single machine was researched. Due to the reason that the original scheduled jobs have release time, a formulate RRLS （rescheduling rush jobs with loads locked on single machine） problem was proposed based on the following measures. That is, the total waiting time was minimized, and the rush jobs was inserted into original schedule, and the maximum waiting time was minimized with loads locked. Then the RRLS problem was proved as a NP-hard one. A heuristic algorithm was presented according to the property of the problem, and its time complexity was also given. At last, an examole oroved the ootimalitv conditions of algorithm.

关 键 词：重调度问题 NP难 紧急工作 启发式算法 等待时间 

分 类 号：TP273[自动化与计算机技术—检测技术与自动化装置]