上海交通大学学报

上海交通大学学报（自然版） ›› 2012, Vol. 46 ›› Issue (11): 1746-1752.

• 自动化技术、计算机技术 • 上一篇    下一篇

考虑后续工序且批处理工序数为2的批综合调度算法

谢志强1, 2, 刘长海1, 杨静2   

  1. (1. 哈尔滨理工大学 计算机科学与技术学院， 哈尔滨 150080；2. 哈尔滨工程大学 计算机科学与技术学院， 哈尔滨 150001)  
  • 收稿日期:2012-03-02 出版日期:2012-11-30 发布日期:2012-11-30
  • 基金资助:

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

Batch Integrated Scheduling Algorithm Considering Posterior Operations and with Constraint of 2 Operations Batches Processing

 XIE  Zhi-Qiang-1, 2 , LIU  Chang-Hai-1, YANG  Jing-2   

  1. (1. College of Computer Science and Technology, Harbin University of Science and Technology， Harbin 150080, China;2. College of Computer Science and Technology, Harbin Engineering University. Harbin 150001, China)
  • Received:2012-03-02 Online:2012-11-30 Published:2012-11-30

摘要： 提出了考虑后续工序且批处理工序数为2的批综合调度算法.该算法根据复杂产品具有树状工艺结构的特点，对非批处理设备上的工序采用已有的优先级、调度长路径和长用时策略调度；对批处理设备上的工序，综合考虑先行工序和后续工序的加工时间对批处理的影响，当被等待工序非批处理延迟时间大于批处理时批处理工序的后续工序加工时间之差时，等待工序与被等待工序一同批处理.通过采用批处理判断策略、提前最大化策略以及并行最大化策略使批处理调度结果更合理.理论分析和实例证明，该算法可使批处理工序数为2的批综合调度结果更优,而且复杂度不超过二次多项式.
 

关键词: 调度算法, 综合调度, 批综合调度,  , 批处理设备, 后续工序

Abstract: A batch integrated scheduling algorithm considering posterior operations and with constraint of 2 operations batches processing was proposed. On the base of tree structure features of complex products, this algorithm uses priority strategy, long-path strategy and long-time strategy to scheduling operations on nonbatch processing machines. For operations processed on batch processing machines, the influences on batch processing by the process time of predecessor operations and posterior operations are taken into full consideration. When the deferredtime in the case of nonbatchedprocessing is longer than the processing lag of posterior operations when operations are batch processed, the waiting operations and operationswaited are batch processed simultaneously. Otherwise, they are not batch processed. The through scheduling using batch judgment strategy, early processing maximization strategy and parallel maximization strategy, the scheduling result is more reasonable. The theoretical analysis and examples show that the proposed algorithm can make the process result of batch integrated scheduling with constraint of 2 operations much better, and the time complexity is no more than quadratic polynomial.  

Key words: scheduling algorithm, integrated scheduling, batching integrated scheduling, batch processing machine, posterior operation

中图分类号: