工业工程

工业工程 ›› 2012, Vol. 15 ›› Issue (5): 118-124.

• 专题论述 • 上一篇    下一篇

考虑急件到达的单机鲁棒调度方法

  

  1. 北京航空航天大学 经济管理学院，北京 100191
  • 出版日期:2012-10-31 发布日期:2012-11-15
  • 作者简介:男，安徽省人，博士研究生，主要研究方向为鲁棒生产调度、进化计算.
  • 基金资助:

    国家自然科学基金资助项目（71071008,70821061）

A Robust Single Machine Scheduling Algorithm with Rush Orders

  1. School of Economics and Management, Beihang University, Beijing 100191, China
  • Online:2012-10-31 Published:2012-11-15

摘要： 实际生产过程中经常会有急件到达。由于急件的优先级最高，其到达容易扰乱初始调度，使实际调度性能恶化，影响调度目标的实现。针对以总拖期为目标且带有释放时间的单机调度问题，研究了在有急件到达情况下的鲁棒调度方法，以降低急件对实际调度性能的影响。鉴于该调度问题是NPhard问题，根据工件释放时间和交货期的关系构造“金字塔”结构，获得该调度问题的占优性质。根据这些占优性质和急件到达特点，研究急件到达情景下的占优规则，据此求解急件到达情景下的占优调度集合，作为鲁棒调度的备选调度方案集合。提出了应对急件到达的鲁棒调度算法。给出仿真算例验证了算法的有效性，算例表明本文给出的鲁棒调度方法能有效避免急件到达造成实际调度性能的恶化。 

关键词: 鲁棒调度, 急件, 单机调度, 占优规则

Abstract: Rush orders are common in practical production. With high priority, rush orders disturb the schedule being executed and degrade scheduling performance. Aiming at reducing the degradation of scheduling performance and hedging against the rush orders, a robust scheduling algorithm is presented for single machine job release problem with total tardiness as objective. Due to the NPhard nature of the problem, a special structure called toppyramid is established in the light of relationship between the release time and due dates of different jobs. In this way, dominant properties can be obtained. Then, the dominant properties are analyzed when rush orders arrives by considering the characteristics of rush orders, and alternative robust schedules are found. With simulation, an example is given to verify the effectiveness of the proposed algorithm. It shows that the proposed robust scheduling algorithm can effectively reduce scheduling performance degradation caused by rush orders.

Key words: robust scheduling, rush orders, singlemachine scheduling, priority rules