International Journal of Computer Network and Information Security (IJCNIS)
IJCNIS Vol. 6, No. 7, 8 Jun. 2014
Cover page and Table of Contents: PDF (size: 469KB)
Task Assignment for Heterogeneous Computing Problems using Improved Iterated Greedy Algorithm
Full Text (PDF, 469KB), PP.50-55
Views: 0 Downloads: 0
Author(s)
R.Mohan
1,*
N.P.Gopalan
2
Index Terms
Load Balancing, Task Assignment, Task Interaction Graph (TIG), Iterated Greedy Heuristic, Parallel Processing, Heterogeneous Computing, Message Passing Interface
Abstract
The problem of task assignment is one of the most fundamental among combinatorial optimization problems. Solving the Task Assignment Problem is very important for many real time and computational scenarios where a lot of small tasks need to be solved by multiple processors simultaneously. A classic problem that confronts computer scientists across the globe pertaining to the effective assignment of tasks to the various processors of the system due to the intractability of the task assignment problem for more than 3 processors. Several Algorithms and methodologies have been proposed to solve the Task Assignment Problem, most of which use Graph Partitioning and Graph Matching Techniques. Significant research has also been carried out in solving the Task Assignment Problem in a parallel environment. Here we propose a modified version of iterated greedy algorithm that capitalizes on the efficacy of the Parallel Processing paradigm, minimizing the various costs along with the duration of convergence. The central notion of the algorithm is to enhance the quality of assignment in every iteration, utilizing the values from the preceding iterations and at the same time assigning these smaller computations to internal processors (i.e. parallel processing) to hasten the computation. On implementation, the algorithm was tested using Message Passing Interface (MPI) and the results show the effectiveness of the said algorithm.
Cite This Paper
R.Mohan, N.P.Gopalan, "Task Assignment for Heterogeneous Computing Problems using Improved Iterated Greedy Algorithm", International Journal of Computer Network and Information Security(IJCNIS), vol.6, no.7, pp.50-55, 2014. DOI:10.5815/ijcnis.2014.07.07
Reference
[1]Casavant, T., Kuhl, J.G., (1998) A taxonomy of scheduling in general-purpose distributed computing systems, IEEE Transaction on Software Engineering 14(2). Pp 141-154.
[2]Chockalingam, T., Arunkumar, S., (1995) Genetic algorithm based heuristics for the mapping problem. Computer and Operations Research. v22. Pp. 55-64.
[3]Hamam, Y., Hindi, K.S., 2000) Assignment of program modules to processors; a simulated annealing approach. European Journal of Operational Research 122. Pp 509-513 European Journal of Operational Research. v177 i3. pp. 2033-2049.
[4]Yin, P.Y., Yu, S.S., Wang, P.P., Wang, Y.T., (2006). A hybrid particle swarm optimization algorithm for optimal task assignment in distributed systems. Computer Standard and Interface 28. Pp 441-450.
[5]Kang, Q., He, H., (2013) Honeybee mating optimization algorithm for task assignment in heterogeneous computing systems. Intelligent Automation and Soft Computing 2013 Vol. 19. Pp 69-84.
[6]Qinma Kang, Hong He and Huimin Song (2011) Task assignment in heterogeneous computing systems using an effective iterated greedy algorithm. Journal of Systems and Software, pp. 985-992.
[7]Shatz, S.M., Wang J.P., Goto, M., (1992) Task allocation for maximizing reliability of distributed computer systems. IEEE Transactions on Computers. v41. Pp. 1156-1168.
[8]Pan, Q, K., Wang, L., Zhao, B.H., (2008) An improved iterated greedy algorithm for the no-wait flow shop scheduling problem with makespan criterion. International Journal of Advanced Manufacturing Technology. v38. Pp. 778-786.
[9]Ruiz, R., Stutzle, T., (2007) A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem.
[10]Ruiz, R., Stutzle, T., (2008) An iterated greedy heuristic for the sequence dependent setup times flowshop problem with makespan and weighted tardiness objectives. European Journal of Operational Research. v 187 i3.Pp.1143-1159.
[11]Ying, K.C., Lin, S.W., Huang, C.Y., (2009) Sequencing single-machine tardiness problems with sequence dependent setup times using an iterated greedy heuristic. Expert Systems with Applications. v36. Pp. 7087-7092.
[12]Chern, M.S., Chen, G.H., Liu P., (1989). An LC branch-and-bound algorithm for module assignment problem. Information Processing Letters 32. Pp 61-71.