Whenever tasks of an application are scheduled in Heterogeneous Distributed Computing environment, idle slots on processors are efficiently utilized to minimize the overall running time. Since task assignment problem has been proved to be NP-complete problem, many heuristics have been given in the literature caring empty slots on processors as well as dependencies among tasks. This paper presents an efficient and effective way to allocate tasks of an application in the Heterogeneous Distributed Computing environment. Generally in list based static scheduling where computation time and communication time are known a-priori. First tasks are prioritized and then the processors that minimize the cost function are assigned to the appropriate tasks. Duplication based scheduling is another category of static scheduling. In this category communication costs among the processors are avoided by duplicating the tasks on same processor. This paper presents a duplication based list scheduling that overwhelms the existing scheduling algorithms in both the categories.

1. Garey, M. R. and Johnson D. S. 1979 Computers and Intrctability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co. , New York, NY, USA
2. Yang, T. and Gerasoulis, A. 1994 DSC: Scheduling parallel tasks on an unbounded number of processors. IEEE Trans. Parallel Distrib. Syst. , 5(9):951–967.
3. Ilavarasan, E. and Thambidurai, P. 2007 Low Complexity Performance Effective Task Scheduling Algorithm for Heterogeneous Computing Environments. Journal of Computer Sciences 3 (2): 94-103
4. Topcuoglu, H. , Hariri, S. , and Wu, M. Y. 2002 Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Trans. Parallel Distrib. Syst. , 13(3):260–274.
5. Adam, T. L. , Chandy K. M. , and Dickson J. R. 1974 A comparison of list schedules for parallel processing systems. Commun. ACM, 17(12):685–690.
6. Kwok, Y. K. and Ahmad, I. 1999 Benchmarking and comparison of the task graph scheduling algorithms. J. Parallel Distrib. Comput. , 59(3):381–422.
7. Liu, G. Q. , Poh, K. L. and Xie. , M. 2005 Iterative list scheduling for heterogeneous computing. J. Parallel Distrib. Comput. , 65(5):654–665.
8. Liou, J. and Falls, M. A. 1996 An efficient clustering heuristic for scheduling dags on multiprocessors. In Proc. Symp. Parallel and Distributed Processing.
9. Bittencourt,L. F. , Madeira, E. R. M. , Cicerre, F. R. L. , and Buzato, L. E. 2005 A Path Clustering Heuristic for Scheduling Taks Graphs onto a Grid. 3rd ACM International Workshop on Middleware for Grid Computing, Grenoble, France. Nov.
10. Ahmad, I. and Kwok, Y. K. 1994 A new approach to scheduling parallel programs using task duplication. In Proc. Int'l Conf Parallel Processing, volume 2, pages 47–51.
11. Ahmad, I. and Kwok,Y. K. 1998 On exploiting task duplication in parallel program scheduling. IEEE Trans. Parallel Distrib. Syst, 9(9):872–892.
12. Park, G. L. , Shirazi, B. and Marquis, J. 1997 DFRN: A new approach for duplication based scheduling for distributed memory multiprocessor systems. In IPPS '97: Proceedings of the 11th International Symposium on Parallel Processing, pages157–166, Washington, DC, USA, IEEE Computer Society.
13. Kwok, Y. K. and Ahmad, I. 1994 Exploiting duplication to minimize the execution times of parallel programs on message-passing systems. In Proceedings of the 6th Symposium on Parallel and Distributed Processing, pages 426–433, Los Alamitos, CA, USA, October, IEEE Computer Society Press.
14. Ranaweera , S. and Agrawal, D. P. 2000 A task duplication based scheduling algorithm for heterogeneous systems. In 14th International Parallel and Distributed Processing Symposium (SPDP'2000), pages 445–450, Washington - Brussels - Tokyo, May.
15. Darbha, S. and Agrawal, D. P. 1997 A task duplication based scalable scheduling algorithm for distributed memory systems. J. Parallel Distrib. Comput, 46(1):15–27.
16. Bansal, S. , Kumar, P. and Singh, K. 2003 An Improved Duplication Stratgy for Scheduling Precedence Constrained Graphs in Multiprocessors. IEEE Trans. Parallel and Distributed Systems,Vol. 31, No. 4,pp. 533-544,june.
17. Goldberg, D. E. 1989 Genetic algorithms in search, optimization, and machine learning. Addison-Wesley, Reading, Massachusetts.
18. Wang, L. , Siegel, H. J. , Roychowdhury, V. P. , and Maciejewski, A. A. 1997 Task matching and scheduling in heterogeneous computing environments using a genetic-algorithm-based approach. Journal of Parallel and Distributed Computing,47(1):8–22, November.
19. Ali, S. , Sait, S. M. , and Benten, M. S. T. 1994 GSA: Scheduling and allocation using genetic algorithm. In Proceedings of the 1994 European Design Automation Conference, pages 84–89, Toronto, Canada, September.

Distributed Computing Critical Path Heterogeneous System Static Scheduling