An on-line seru scheduling algorithm with proactive waiting considering resource conflicts

Seru production systems (SPSs) with quick responsiveness and high flexibility have been applied in many Asian electronic enterprises. An SPS can quickly respond to market demands with changing varieties and fluctuated volumes. Resource conflicts are used to indicate the requirements for a same worker by more than one seru. This paper studies the on-line seru scheduling problem with resource conflicts in limited work space, which decides serus’ built-up sequence over time and aims at minimizing the makespan. To keep a balance between quick responsiveness and production efficiency in an SPS, a proactive waiting strategy is proposed and a nested algorithm is structured with an external framework and an internal sequencing policy. The external framework handles resource conflicts among serus and divides serus into groups in which resource conflicts do not exist. The internal sequencing policy acts on each group and decides the built-up sequence for serus. The nested algorithm is proved to be 2ρ-competitive with two seru families. Performance of the nested algorithm can be enhanced by improving the internal sequencing policy without changing the external framework, which is conformed by computational experiments. With more seru families, experimental results show that the nested-LPT algorithm can adapt to frequent arrivals of orders, complicated resource conflicts, and fluctuating market demands.