A large-scale distributed decision-making procedure for a single-machine scheduling problem

作者：Hong Soondo; Banerjee Amarnath^*

来源：International Journal of Production Research, 2012, 50(20): 5795-5808.

DOI：10.1080/00207543.2011.628708

• scheduling
• decision support systems
• distributed decision-making
• large-scale scheduling problem

This paper presents a distributed scheduling procedure for a large-scale single-machine problem with precedence constraints, and identifies phenomena using large-scale distributed decision-making for a decomposable and distributed situation. The approach proposed exhibits efficient computational performance over a large-sized work load (23,000 jobs and 2,209,536 precedence constraints) in a distributed computing environment. We highlight three findings: (1) the communication burden originating from the large-scale problem can lead to performance loss while distributed agents collaborate to solve the problem, but after a threshold the computational gain by distribution offsets the loss; (2) when the problem size is sufficiently large, the real computation gain outperforms the expected gain by the number of agents (super-linear effect); and (3) when the number of precedence constraints of each agent differs, the slowest agent processing the largest number of precedence constraints restrains the computational performance (load imbalance). We believe that our research is the first distributed decision-making model that meets the requirements of distributed information, distributed decision authority, and distributed computation in a large-scale single-machine scheduling situation with precedence constraints.

• 出版日期2012