Distributed Task Scheduling through a Swarm Intelligence Approach
Resumo
This paper addresses distributed task scheduling problems as a distributed version of the Resource-Constrained Project Scheduling Problem (RCPSP). We propose and evaluate a novel approach for the distributed RCPSP based on theoretical models of division of labor in social insect colonies. Our approach uses a probabilistic decision-making model based on the social insect tendency to perform certain tasks, and was implemented as an algorithm called Swarm-RCPSP. We show that the results of the Swarm-RCPSP algorithm are better than those obtained with a distributed greedy algorithm, are not very far from the best-known solutions, and have the advantage of being computed in a distributed manner, which is an important issue when dealing with multiagent systems.
Referências
Brucker, P. and Knust, S. (2000). A linear programming and constraint propagation-based lower bound for the rcpsp. European Journal of Operational Research, 127(2):355–362.
Davin, J. and Modi, P. J. (2005). Impact of problem centralization in distributed constraint optimization algorithms. In Proceedings of the Fourth International Joint Conference on Autonomous Agents and MultiAgent Systems, pages 1057–1066, New York, NY, USA. ACM Press.
Ferreira, Jr., P. R., Boffo, F., and Bazzan, A. L. C. (2008). Using Swarm-GAP for distributed task allocation in complex scenarios. In Jamali, N., Scerri, P., and Sugawara, T., editors, Massively Multiagent Systems, number 5043 in Lecture Notes in Artificial Intelligence, pages 107–121. Springer, Berlin.
Kolisch, R. and Sprecher, A. (1997). Psplib – a project scheduling problem library. European Journal of Operational Research, 96(1):205–216.
Kube, R. and Bonabeau, E. (2000). Cooperative transport by ants and robots. Robotics and Autonomous Systems, 30(1/2):85–101.
Luo, X., Wang, D., Tang, J., and Tu, Y. (2006). An improved pso algorithm for resource-constrained project scheduling problem. Intelligent Control and Automation, 1(1):3514–3518.
Maheswaran, R. T., Tambe, M., Bowring, E., Pearce, J. P., and Varakantham, P. (2004). Taking DCOP to the real world: Efficient complete solutions for distributed multi-event scheduling. In Proceedings of the 3rd International Joint Conference on Autonomous Agents and Multiagent Systems, AAMAS, volume 1, pages 310–317, New York. Washington, DC: IEEE Computer Society.
Merkle, D., Middendorf, M., and Schmeck, H. (2002). Ant colony optimization for resource-constrained project scheduling. IEEE Transactions on Evolutionary Computation, 6(4):333–146.
Robinson, G. E. (1992). Regulation of division of labor in insect societies. Annual Review of Entomology, 37:637–665.
