A Robust Single Machine Scheduling Algorithm with Rush Orders

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.