• CN:11-2187/TH
  • ISSN:0577-6686

›› 2011, Vol. 47 ›› Issue (11): 139-147.

• 论文 • 上一篇    下一篇

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

谢志强;辛宇;杨静   

  1. 哈尔滨理工大学计算机科学与技术学院;哈尔滨工程大学计算机科学与技术学院
  • 发布日期:2011-06-05

Integrated Scheduling Algorithm Based on Event-driven by Machines’ Idle

XIE Zhiqiang;XIN Yu;YANG Jing   

  1. College of Computer Science and Technology, Harbin University of Science and Technology College of Computer Science and Technology, Harbin Engineering University
  • Published:2011-06-05

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

关键词: 调度算法, 工序并行, 设备空闲事件, 事件驱动, 综合调度

Abstract: 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.

Key words: Event-driven, Integrated scheduling, Machines’ idle event, Operations parallel processing, Scheduling algorithm

中图分类号: