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

›› 2011, Vol. 47 ›› Issue (22): 181-190.

• 论文 • 上一篇    下一篇

基于交货期紧迫度的综合调度算法

谢志强;常宁宁;杨静   

  1. 哈尔滨理工大学计算机学院;哈尔滨工程大学计算机学院
  • 发布日期:2011-11-20

Integrated Scheduling Algorithm Based on Delivery Dates Urgency Degree

XIE Zhiqiang;CHANG Ningning;YANG Jing   

  1. School of Computer Science and Technology, Harbin University of Science and Technology School of Computer Science and Technology, Harbin Engineering University
  • Published:2011-11-20

摘要: 为解决开始时间与交货期都不相同的多品种小批量复杂产品综合调度问题,提出基于交货期紧迫度的综合调度算法。该算法根据产品加工的开始时间由前到后排序调度;当存在多产品开始时间相同时,根据产品优先加工的紧迫度,确定它们的调度次序;如果存在紧迫度相同的产品,将按交货期由早到晚排序调度;若交货期也相同,则将它们虚拟成一个产品统一调度;对被调度产品采用长路径策略和短用时策略确定其各工序的调度次序,并结合设备工序紧凑法确定工序的开始时间。该算法结合产品紧迫度和设备工序紧凑法的优点,使开始时间不同的多产品在尽量减少设备空闲时间的情况下,按交货期完工。理论分析和实例表明,该算法可在二次复杂度内给出较合理的综合调度方案。

关键词: 不同开始时间, 交货期, 紧迫度, 设备工序紧凑法, 综合调度算法

Abstract: In order to solve the integrated scheduling problem that there is difference at starting time and delivery dates of complex products of many species of small batches, an integrated scheduling algorithm based on delivery dates urgency degree is put forward. This algorithm schedules from font to back according to the beginning time of products. When there exist multi-products with the same beginning time, the scheduling order of these products is determined by the urgency degree of priority processing; if there exist products with the same time degree of urgency, they will be scheduled according to delivery date and priority schedules the products with early delivery date; if these products have the same delivery date they will be virtually combined to one product and be scheduled. The order of the scheduling products’ processes is determined by long-path strategy and short-time strategy; the processes’ start-times are determined by equipment compact operations. The algorithm combines the urgency of products and the advantages of equipment compact operations. Under the condition of reducing idle time of equipments, it not only can make the multi-products with different starting time be finished in delivery dates. Theoretical analysis and examples show that the algorithm can solve integrated scheduling problem with reasonable schemes in second complexity.

Key words: Integrated scheduling algorithm, Delivery dates, Difference at staring time, Equipment compact operations, Urgency degree

中图分类号: