摘要
针对基于拟关键路径法(Allied critical path method,ACPM)的综合调度算法按路径长度确定工序的调度次序,形成工序组间的并行处理,使设备产生较多空闲时间的问题,提出基于设备空闲事件驱动的综合调度算法。该算法主要是根据空闲设备选择加工工序,思路是以每次工序加工结束作为一次设备空闲事件,驱动空闲设备进行一次可调度工序的寻找;如果可调度工序唯一,则调度此工序;如果可调度工序不唯一,选择父结点路径长的工序;如果父结点最长路径相同,选择用时短的工序。由于该算法在调度工序时不考虑工序序列且以设备空闲驱动,使得该算法按工序并行处理且能充分利用设备空闲时间,避免基于ACPM法产生较多设备空闲时间的问题。另外,由于该算法无需判断空闲时间段的大小、相同设备间的使用均衡和无需空闲设备频繁检测可调度工序,可节约大量的判断操作。实例表明所提出的算法不仅比系列ACPM法设备利用率都高,而且简便可行。
Aiming at the problem that parallel processing among the groups of operations and machines with plenty of idle time will be caused by allied critical path method（ACPM） based on the length of path by the integrated scheduling algorithm,an integrated scheduling algorithm based on event-driven by machines＇ idle is presented.Selecting operations which need be processed according to the idle machines is the main method in this algorithm.Process of this method is to regard the end of each operation processed as an event with machines＇ idle,and this event drives idle machine to search schedulable operations.If schedulable operation is sole,this operation is scheduled.If schedulable operations are not sole,the operation whose father node has longest path length is selected.If the operations with longest path of father node are not sole,operation whose processing time is shortest is selected.As this algorithm doesn＇t consider the operation sequence in scheduling operations and it is driven by machines＇ idle,the algorithm can cause among schedulable,take full advantage of idle time of machine and avoid problem that there will be more machine idle time by using the integrated scheduling algorithm based on ACPM.In addition,the algorithm needn＇t to compare the length of machine idle time and judge whether using identical machines is balanced,and also not need idle machine to detect schedulable operations frequently,so plenty of judgment operations can be saved.Examples show the algorithm which is proposed not only has the highest efficiency than other algorithms based on ACPM,but also can be realized easily.
出处
《机械工程学报》
EI
CAS
CSCD
北大核心
2011年第11期139-147,共9页
Journal of Mechanical Engineering
基金
国家自然科学基金(60873019
61073043)
黑龙江省自然科学基金(F200901)
中国博士后科学基金(20090460880)
黑龙江省博士后科学基金(LBH-Z09214)
哈尔滨市优秀学科带头人基金(2010RFXXG054
2011RFXXG015)资助项目
关键词
设备空闲事件
事件驱动
工序并行
综合调度
调度算法
Machines＇ idle event Event-driven Operations parallel processing Integrated scheduling Scheduling algorithm
