可回退抢占的设备驱动综合调度算法

摘要：

针对基于拟关键路径法的综合调度算法按路径长度确定工序的调度次序,形成工序组间的并行处理,使设备产生较多空闲时间的问题,提出可回退抢占的设备驱动综合调度算法.该算法以每次工序加工结束作为一次可调度工序的寻找事件,若此时新出现的可调度工序具备抢占能力,则产生回退事件进行重调度；若不产生回退事件,如果可调度工序唯一,则调度此工序；如果可调度工序不唯一,选择父结点路径长的工序；如果父结点最长路径相同,选择用时长的工序.由于该算法在调度工序时形成工序间的并行处理,缩小基于拟关键路径的综合调度算法形成的并行处理单位,进而减少加工过程中产生较多的设备空闲时间,提高设备利用率；同时,由于采用抢占式的回退调度策略,优先调度对调度结果有重要影响的长路径工序,达到对拟关键路径法的扬长避短,进一步提高设备利用率.

关键词：设备空闲事件、事件驱动、工序并行、综合调度、回退抢占、工序组

所属期刊栏目：37

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金60873019;61073043;中国博士后科学基金20090460880;黑龙江省自然科学基金F200901;黑龙江博士后科学基金LBH-Z09214;哈尔滨市优秀学科带头人项目2010RFXXG054;2011RFXXG015

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

页码：1332-1343