An Agent Based Heuristics for Large Synchronized Task Allocation
Abstract
This paper studies a heuristics method for huge synchronized task allocation problem. In many huge task processing, it is easy to consider that their huge tasks are divided into many subtasks processed by many distributed computers. It is known that the distributed computing is fast approach when their machines process independently. However, it is necessary to communicate between each machine to solve the problem in appreciation level. We treat a snowplow problem as an example of the huge synchronized task allocation problem. We employ an agent simulation for solving the snowblower problem.
References
N. Katoh, and T. Ibaraki, Resource Allocation Problems. Handbook of Combinatorial Optimization (Vol. 2), D. Z. Du, and P. M. Pardalos (Eds), pp. 159–260, 1998.
E. M. Arkin and M. A. Bender and J. S. B. Mitchell The snowblower problem. Proc. of 7th International Workshop on the Algorithmic Foundations of Robotics, 2006.
S. Iwata, A Fully Combinatorial Algorithm for Submodular Function Minimization. Journal of Combinatorial Theory, Series B, Vol. 84, pp. 203–212, 2002.
S. Iwata, and J. B. Orlin, A Simple Combinatorial Algorithm for Submodular Function Minimization. Proc. of the twentieth annual ACM-SIAM symposium on Discrete Mathematics, pp. 1230–1237, 2009.
S. Fujishige, Submodular Functions and Optimization, Second Edition. Annals of Discrete Mathematics, Vol. 58, Elsevier, 2005.
A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency (Algorithms and Combinatorics) . Springer varlag , 2003.
B. Lehmann, and D. Lehmann, and N. Nisan, Combinatorial auctions with decreasing marginal utilities. Games and Economic Behavior, Vol. 55, pp. 270-296, 2005.
R. K. Afuja, and T. L. Magnanti, and J. B. Orlin, Network Flows : Theory, Algorithms, and Applications. Prentice Hall; United States ed, 1993.
S. Masuyama and S. Nakayama, What Structural Features Make Graph Problems to Have Efficient Parallel Algorithms? Using Outerplanar Graphs, Trapezoid Graphs and In-Tournament Graphs as Examples. EICE Transactions on Information and Systems, Vol. E83-D, No. 3, pp. 541–549, 2000.
A. Billionnet, and M. C. Costa, and A. Sutter. An efficient algorithm for a task allocation problem. Journal of ACM, Vol. 39, pp. 502–518, 1992.
Billionnet, A. and Costa, M. C. and Sutter, A. The task allocation problem with constant communication. Discrete Applied Mathematics, Vol. 131, pp. 169–177, 2003.
