A balancing algorithm for robust decentralized parallel machine scheduling to minimize makespan

In some situations, a scheduling problem may be characterized by unpredictable processing times, sudden pop-up jobs, machine failures as well as communication failures. Centralized scheduling might not be possible because of autonomous agents and where a centralized scheduling entity does not exist. One such example is ‘Automated Construction by Multiple Robotic Agents’. Autonomous construction is a critical enabling technology for the military and remote planetary exploration, and requires a decentralized, robust and reactive scheduling algorithm for assigning tasks to its component agents. Centralized scheduling is not an option for such systems. The processing times for various tasks such as digging of earth, drying of concrete, road paving, etc., are plagued with high variance. This is compounded by the fact that the robots performing the tasks might experience failures – due to agents and implements getting stuck in mud, breaking down, inadvertent leakage of fuel, etc. The abstract mathematical characterization of this paradigm is best represented as a scheduling problem involving unpredictable processing times, sudden pop-up jobs, machine- and communication-failures. In this paper, we propose a reactive scheduling algorithm that can be easily implemented in a decentralized manner for this paradigm. We consider the cases of identical parallel machine scheduling and non-identical parallel machine scheduling problems without precedence constraints. Our empirical results show that the proposed algorithm reaches near optimal solution almost all the time, thus showing its effectiveness.