EXACT ALGORITHMS FOR A TASK ASSIGNMENT PROBLEM
Abstract
We consider the following task assignment problem. Communicating tasks are to be assigned to heterogeneous processors interconnected with a heterogeneous network. The objective is to minimize the total sum of the execution and communication costs. The problem is NP-hard. We present an exact algorithm based on the well-known A* search. We report simulation results over a wide range of parameters where the largest solved instance contains about three hundred tasks to be assigned to eight processors.
References
S. Ali , Task execution time modeling for heterogeneous computing systems, Proceedings of the 9th Heterogeneous Computing Workshop (HCW 2000), ed.Cauligi Raghavendra (IEEE, 2000) pp. 185–199. Google Scholar- J. Syst. Architect. 54, 530 (2008), DOI: 10.1016/j.sysarc.2007.10.001. Crossref, ISI, Google Scholar
- IEEE T. Parall. Distr. 5(4), 445 (1994), DOI: 10.1109/71.273051. Crossref, ISI, Google Scholar
- IEEE T. Software Eng. 7, 583 (1981). ISI, Google Scholar
H. Casanova , Heuristics for parameter sweep applications in Grid environments, Proc. Ninth Heterogeneous Computing Workshop (IEEE Computer Society Press, 2000) pp. 349–363. Google Scholar-
T. H. Cormen , C. E. Leiserson and R. L. Rivest , Introduction to Algorithms , 1st edn. ( MIT Press , 1990 ) . Google Scholar -
M. R. Garey and D. S. Johnson , Computers and Intractability, A Guide to the Theory of NP-Completeness ( W.H. Freeman and Company , New York , 1979 ) . Google Scholar - Future Gener. Comp Sy. 12, 97 (1996). Google Scholar
- IEEE Concurr. 6, 42 (1998), DOI: 10.1109/4434.708255. Crossref, ISI, Google Scholar
- J. Parallel Distr. Com. 65, 1515 (2005). Crossref, ISI, Google Scholar
- IEEE T. Knowl. Data En. 16, 1497 (2004), DOI: 10.1109/TKDE.2004.91. Crossref, ISI, Google Scholar
-
S. Russell and P. Norvig , Artificial Intelligence: A Modern Approach , 2nd edn. ( Pearson Education Inc , New Jersey, USA , 2003 ) . Google Scholar - IEEE T. Software Eng. SE-3, 85 (1977), DOI: 10.1109/TSE.1977.233840. Crossref, ISI, Google Scholar
- J. Parallel Distr. Com. 42, 82 (1997), DOI: 10.1006/jpdc.1997.1302. Crossref, ISI, Google Scholar
- J Syst. Software 46, 59 (1999), DOI: 10.1016/S0164-1212(98)10088-2. Crossref, ISI, Google Scholar
- J. Parallel Distr. Com. 66, 32 (2006). Crossref, ISI, Google Scholar
J. B. Weissman and X. Zhao , Run-time support for scheduling parallel applications in heterogeneous nows, HPDC '97: Proc. of the 6th International Symposium on High Performance Distributed Computing (IEEE, Portland, USA, 1997) pp. 347–355. Google Scholar


