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

A Robust Single Machine Scheduling Algorithm with Rush Orders

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

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 re- lease 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 scheduling performance degradation that the proposed robust scheduling algorithm can effectively reduce caused by rush orders.