A method for assigning tasks or resources, based on a model of division of labor in social insects, is introduced and applied to a dynamic flow shop scheduling problem. The problem consists of assigning trucks to paint booths in a truck facility to minimize total makespan and the number of paint flushes. Similarities between the ant-based approach and a market-based approach are high-lighted. Both systems are able to adapt well to changing conditions.
Get full access to this article
View all access options for this article.
References
1.
Bonabeau, E., G. Théraulaz, and J.-L. Deneubourg .Quantitative Study of the Fixed Threshold Model for the Regulation of Division of Labour in Insect Societies." Proc. Roy. Soc. London B 263 (1996): 1565-1569.
2.
Bonabeau, E., A. Sobkowski, G. Théraulaz, and J.-L. Deneubourg . "Adaptive Task Allocation Inspired by a Model of Division of Labor in Social Insects." In Bio-Computation and Emergent Computing, edited by D. Lundh , B. Olsson, and A. Narayanan, 36—45. Singapore: World Scientific, 1997.
3.
Bonabeau, E., G. Théraulaz, and J.-L. Deneubourg . "Fixed Response Thresholds and the Regulation of Division of Labor in Insect Societies." Bull. Math. Biol.60 (1998): 753-807.
4.
Bonabeau, E., M. Dorigo, and G. Théraulaz.Swarm Intelligence: From Natural to Artificial Systems . Oxford, UK: Oxford University Press, 1999.
5.
Clearwater, S.H., and B.A. Huberman. "Thermal Markets for Controlling Building Environments ." Energy Eng.91 ( 1994): 26-56.
6.
Clearwater, S.H.Market-Based Control: A Paradigm for Distributed Resource Allocation. Singapore: World Scientific, 1995 .
7.
Dorigo, M., V. Maniezzo, and A. Colorni. "The ant system: optimization by a colony of cooperating agents." IEEE Trans. Syst. Man Cybern. B 26 (1996): 29-41.
8.
Dorigo, M., and L. Gambardella. "Ant colony system : a cooperative learning approach to the traveling salesman problem." IEEE Trans. Evol. Comp. 1 (1997): 53-66.
9.
Goldberg, D.E.Genetic Algorithms in Search, Optimization and Machine Learning. Reading, MA: Addison-Wesley, 1989 .
10.
Huberman, B.A., and T. Hogg. "Distributed Computation as an Economic System." J. Econom. Perspect.9 (1995): 141-152.
11.
Kurose, J.F., and R. Simha. "A Microeconomic Approach to Optimal Resource Allocation in Distributed Computer Systems." IEEE Trans. Computers38 (1989): 705-717.
12.
Morley, R. "Painting Trucks at General Motors: The Effectiveness of a Complexity-Based Approach." In Embracing Complexity: Exploring the Application of Complex Adaptive Systems to Business, 53-58. Cambridge, MA : The Ernst & Young Center for Business Innovation , 1996.
13.
Morley, R., and G. Ekberg. "Cases in Chaos: Complexity-Based Approaches to Manufacturing ." In Embracing Complexity: A Colloquium on the Application of Complex Adaptive Systems to Business, 97-702. Cambridge, MA : The Ernst & Young Center for Business Innovation , 1998.
14.
Oster, G., and E.O. Wilson.Caste and Ecology in the Social Insects. Princeton, NJ: Princeton University Press, 1978.
15.
Riolo, R.L. "Survival of the Fittest Bits." Sci. Am.267 (1992): 114-116.
16.
Robinson, G.E. "Regulation of Vision of Labor in Insect Societies." Annu. Rev. Entomol.37 (1992): 637-665.
17.
Schoonderwoerd, R., O. Holland, and J. Bruten "Ant-based load balacing in telecommunications networks." Adaptive Behav.5 (1996): 169-207.
18.
Théraulaz G., S. Goss, J. Gervet, and J.-L. Deneubourg . "Task Differentiation in Polistes Wasp Colonies: A Model for Self-Organizing Groups of Robots." In Proceedings First International Conference on Simulation of Adaptive Behavior: From Animals to Animats, edited by J.-A. Meyer and S. W. Wilson, 346—355. Cambridge, MA: MIT Press, 1991.
19.
Théraulaz, G., E. Bonabeau, and J.-L. Deneubourg . "Threshold Reinforcement and the Regulation of Division of Labour in Insect Societies." Proc. Roy. Soc. London B 265 (1998): 327-335.
20.
Tofts, C., and N.R. Franks. "Doing the Right Thing:\enskip Ants, Honey Bees and Naked Mole-Rats." Trends EcoL Evol.7 (1992): 346-349.
21.
Waldspurger, C.A., T. Hogg, B.A. Huberman, and J.O. Kephart. "Spawn: A Distributed Computational Economy." IEEE Trans. Softw. Engineer.18 ( 1992): 103-117.
22.
Walsh, W.E., M.P. Wellman, P.R. Wurman, and J.K. MacKie-Mason . "Some economics of market-based distributed scheduling." In Eighteenth Int. Conf. on Distributed Computing Systems, 325-332.
23.
Wellman, M.P. "A market-oriented programming environment and its application to distributed multicommodity flow problems." J. Artif. Intel. Res.1 (1993): 1-23.
24.
Wellman, M.P. "The economic approach to artificial intelligence." ACM Computing Surveys (1995): 360-362.
25.
Wilson, E.O.The Insect Societies. Cambridge, MA: Harvard University Press, 1971.
26.
Wilson, E.O. "The Relation Between Caste Ratios and Division of Labour in the Ant Genus Pheidole (Hymenoptera: Formicidae)." Behav. Ecol. Sociobiol.16 (1984): 89-98.
27.
Ygge, E., and J.M. Akkermans. "Making a case for multi-agent systems." In Multi-Agent Rationality (Boman, M., and W. Van de Velde, eds), 156-176. Springer Verlag, Berlin.
28.
Ygge, F.Market-Oriented Programming and its Application to Power-Load Management. PhD Dissertation, Lund University, Sweden, 1998 .
