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

Raunak Sengupta, Rakesh Nagi, William Robert, Norris R.S. Sreenivas, Dustin Nottage, Ahmet Soylemezoglu

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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.

Original languageEnglish (US)
Title of host publicationProceedings of the 2020 IISE Annual Conference
EditorsL. Cromarty, R. Shirwaiker, P. Wang
PublisherInstitute of Industrial and Systems Engineers, IISE
Pages1246-1251
Number of pages6
ISBN (Electronic)9781713827818
StatePublished - 2020
Event2020 Institute of Industrial and Systems Engineers Annual Conference and Expo, IISE 2020 - Virtual, Online, United States
Duration: Nov 1 2020Nov 3 2020

Publication series

NameProceedings of the 2020 IISE Annual Conference

Conference

Conference2020 Institute of Industrial and Systems Engineers Annual Conference and Expo, IISE 2020
CountryUnited States
CityVirtual, Online
Period11/1/2011/3/20

Keywords

  • Decentralized Algorithm
  • Parallel Machines
  • Reactive Scheduling
  • Robust Scheduling
  • Scheduling

ASJC Scopus subject areas

  • Control and Systems Engineering
  • Industrial and Manufacturing Engineering

Fingerprint Dive into the research topics of 'A balancing algorithm for robust decentralized parallel machine scheduling to minimize makespan'. Together they form a unique fingerprint.

Cite this