摘要: 对单机环境下紧急工作的重调度问题进行了研究.初始调度中工作带有到达时间,目标为最小化初始工作的等待时间和;重调度目标是在初始调度锁定的情况下,将紧急工作插入初始调度,最小化紧急工作的最长等待时间.建立了RRLS(reschedulingrushjobswithloadslockedonsinglemachine)问题模型,然后证明了RRLS问题是NP难问题.根据问题性质和特点提出了有效的启发式算法,并给出了算法的时间复杂度.通过实例证明了算法的最优性条件.
中图分类号:
郭艳东,黄敏,王庆. 锁定初始调度的紧急工作单机重调度问题[J]. 东北大学学报(自然科学版), 2013, 34(5): 628-631.
GUO Yandong, HUANG Min, WANG Qing. Rescheduling for Rush Jobs on Single Machine with Loads Locked Original Scheduling[J]. Journal of Northeastern University, 2013, 34(5): 628-631.