论文部分内容阅读
对单机环境下紧急工作的重调度问题进行了研究．初始调度中工作带有到达时间，目标为最小化初始工作的等待时间和；重调度目标是在初始调度锁定的情况下，将紧急工作插入初始调度，最小化紧急工作的最长等待时间．建立了RRLS（rescheduling rush jobs with loads locked on single machine）问题模型，然后证明了RRLS问题是NP难问题．根据问题性质和特点提出了有效的启发式算法，并给出了算法的时间复杂度．通过实例证明了算法的最优性条件．