基于设备空闲事件驱动的综合调度算法

针对基于拟关键路径法(Allied critical path method,ACPM)的综合调度算法按路径长度确定工序的调度次序,形成工序组间的并行处理,使设备产生较多空闲时间的问题,提出基于设备空闲事件驱动的综合调度算法。该算法主要是根据空闲设备选择加工工序,思路是以每次工序加工结束作为一次设备空闲事件,驱动空闲设备进行一次可调度工序的寻找;如果可调度工序唯一,则调度此工序;如果可调度工序不唯一,选择父结点路径长的工序;如果父结点最长路径相同,选择用时短的工序。由于该算法在调度工序时不考虑工序序列且以设备空闲驱动,使得该算法按工序并行处理且能充分利用设备空闲时间,避免基于ACPM法产生较多设备空闲时间的问题。另外,由于该算法无需判断空闲时间段的大小、相同设备间的使用均衡和无需空闲设备频繁检测可调度工序,可节约大量的判断操作。实例表明所提出的算法不仅比系列ACPM法设备利用率都高,而且简便可行。

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

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