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

›› 2012, Vol. 48 ›› Issue (24): 164-173.

• 论文 • 上一篇    下一篇

2个加工时间不同工序组批的嵌套批综合调度算法

谢志强; 刘长海; 杨静   

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

Nested Batching Integrated Scheduling Algorithm of Different Processing Time with Constraint of 2 Operations Batches Processing

XIE Zhiqiang;LIU Changhai;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:2012-12-20

摘要: 针对已有的批加工工序数为2的批综合调度算法,没有考虑组批工序不同和后续工序中存在组批工序的情况,不能适用于更复杂的批综合调度问题,提出求解2个加工时间不同工序组批的嵌套批综合调度算法。该算法根据批处理工序加工时间不同的特点,定义串行衔接时间和并行衔接时间;提出判断组批的余差比较策略;当可与等待工序一同批处理的工序不唯一时,采用组批前移最大化策略确定组批处理工序;当准备组批处理工序的后续工序中存在组批工序时,在余差比较策略中加入嵌套优化策略确定该工序是否组批;由于组批工序的后续工序较多且对调度结果影响较大,采用前续工序优先策略使组批工序尽早加工。理论分析和实例表明,提出的算法可解决2个加工时间不同工序组批的嵌套批综合调度问题。

关键词: 调度算法, 批综合调度, 嵌套处理, 综合调度

Abstract: Aiming at the existing batching integrated scheduling algorithm with constraint of 2 operations batch processing, without considering the different time of the batch processing operation and among the subsequent operations existing groups of batch process, both of which can not apply to more complex batching integrated scheduling problem, nested batching integrated scheduling algorithm considering different processing time with constraint of 2 operations batches processing is proposed. According to the characteristic with different processing time of batch processing operations, the algorithm defines the serial connection time and parallel connection time; It puts forward the residual comparing strategy for judging group batch; When the batch operation which with waiting-operation is batch processed on the same time is not only, the group of batch maximizing forward strategy has been adopted to determine the batch operation; When the subsequent operations of batch process exist group of batch process, the nested optimization strategy has been added to determine whether the operation is group batch processed in the residual comparing strategy; Because of the more subsequent operations of batch process and the greater influence on scheduling results, the preceding operation priority strategy which can process the group of batch process as early as possible has been adopted. Theory analysis and examples show that the proposed algorithm can solve the nested batching integrated scheduling algorithm considering different processing time with constraint of 2 operations batches processing.

Key words: Batching integrated scheduling, Integrated scheduling, Nested processing, Scheduling algorithm

中图分类号: