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

摘要：

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

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

所属期刊栏目：34

分类号：TP273(自动化技术及设备)

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

在线出版日期：2015-07-29（万方平台首次上网日期，不代表论文的发表时间）

页数：共4页

页码：628-631