DAG Scheduling in Heterogeneous Computing and Grid Environments Using Variable Neighborhood Search Algorithm

References

• Abraham, A., H. Liu, and M. Zhao. 2008. Particle swarm scheduling for work-flow applications in distributed computing environments. Studies in Computational Intelligence 128:327–42.
   Google Scholar
• Ahmad, I., and Y. Kwok. 1994. A new approach to scheduling parallel programs using task duplication. Proceedings Int’l Conference Parallel Processing 2:47–51.
   Google Scholar
• Alba, E., and G. Luque. 2007. A new local search algorithm for the DNA fragment assembly problem. Proceedings of 7th European Conference on Evolutionary Computation in Combinatorial Optimization, vol. 4446 of Lecture Notes in Computer Science, Berlin, Heidelberg, Springer, 1–12.
   Google Scholar
• Amini, A., T. Y. Wah, M. Saybani, and S. Yazdi. 2011. A study of density-grid based clustering algorithms on data streams. Proceedings of 8th International Conference on Fuzzy Systems and Knowledge Discovery, FSKD, Shanghai, China, 3, 1652–56.
   Google Scholar
• Audet, C., J. Brimberg, P. Hansen, and N. Mladenovi´C. 2004. Pooling problem: Alternate formulation and solution methods. Management Science 50:761–76. doi:10.1287/mnsc.1030.0207.
   Web of Science ®Google Scholar
• Bajaj, R., and D. Agrawal. 2004. Improving scheduling of tasks in a heterogeneous environment. IEEE Transactions on Parallel and Distributed Systems 15 (2):107–18. doi:10.1109/TPDS.2004.1264795.
   Web of Science ®Google Scholar
• Bansal, S., P. Kumar, and K. Singh. 2003. An improved duplication strategy for scheduling precedence constrained graphs in multiprocessor systems. IEEE Transactions on Parallel and Distributed Systems 14 (6):533–44. doi:10.1109/TPDS.2003.1206502.
   Web of Science ®Google Scholar
• Behnamian, J., and M. Zandieh. 2013. Earliness and tardiness minimizing on a realistic hybrid flowshop scheduling with learning effect by advanced metaheuristic. Arabian Journal for Science and Engineering 38:1229–42. doi:10.1007/s13369-012-0347-6.
   Web of Science ®Google Scholar
• Boyer, W. F., and H. Gs. 2005. Non-evolutionary algorithm for scheduling dependent tasks in distributed heterogeneous computing environments. Journal of Parallel and Distributed Computing 65 (9):1035–46. doi:10.1016/j.jpdc.2005.04.017.
   Web of Science ®Google Scholar
• Brimberg, J., P. Hansen, K.-W. Lih, N. Mladenovi´C, and M. Breton. 2003. An oil pipeline design problem. Operations Research 51:228–39. doi:10.1287/opre.51.2.228.12786.
   Web of Science ®Google Scholar
• Chen, T., B. Zhang, X. Hao, and Y. Dai. 2006. Task scheduling in grid based on particle swarm optimization. Proceedings of the 5th International Symposium on Parallel and Distributed Computing (ISPDC’06), Timisoara, Romania, 238–45.
   Google Scholar
• Chitra, P., R. Rajaram, and P. Venkatesh. 2011. Application and comparison of hybrid evolutionary multiobjective optimization algorithms for solving task scheduling problem on heterogeneous systems. Applied Soft Computing 11:2725–34. doi:10.1016/j.asoc.2010.11.003.
   Web of Science ®Google Scholar
• Chung, Y., and S. Ranka. 1992. Applications and Performance analysis of a compile-time optimization approach for list scheduling algorithms on distributed memory multiprocessors. Proceedings of the Super Computing, Minneapolis, 512–21, November.
   Google Scholar
• Coffman, E. G. 1976. Computer and jop-shop scheduling theory. New York, NY: John Wiley & Sons Inc.
   Google Scholar
• Cormen, T. H., C. E. Leiserson, and R. L. Rivest. 1990. Introduction to algorithms. MIT Press, Cambridge.
   Google Scholar
• Correa, T. C., A. Ferreria, and P. Rebreyend. 1996. Integrating list heuristics into Genetic Algorithms for Multiprocessor Scheduling. Proceedings of the 8th IEEE Symposium on Parallel and Distributed processing (SPDP’96), New Orleans, Louisiana, October.
   Google Scholar
• Costa, M. C., F. R. Monclar, and M. Zrikem. 2005. Variable neighborhood decomposition search for the optimization of power plant cable layout. Journal of Intelligent Manufacturing 13:353–65. doi:10.1023/A:1019980525722.
   Web of Science ®Google Scholar
• Darling, A. E., L. Carey, and W. Feng. 2003. The design, implementation and evaluation of mpi BLAST. Proceedings of the 4th LCI International Conference on Linux Clusters: The HPC Revolution 2003, San Jose, California, June.
   Google Scholar
• El-Rewin, H., and T. Lewis. 1990. Scheduling parallel program tasks onto arbitrary target machines. Journal of Parallel and Distributed Computing 9:138–53. doi:10.1016/0743-7315(90)90042-N.
   Web of Science ®Google Scholar
• El-Rewini, H., T. G. Lewis, and H. H. Ali. 1994. Task scheduling in parallel and distributed systems. New Jersey, NJ: Prentice Hall.
   Google Scholar
• Ferrandi, F., P. Lanzi, C. Pilato, D. Sciuto, and A. Tumeon. 2010. Ant colony heuristic for mapping and scheduling tasks and commucnication on heterogeneous embedded systems. IEEE Transactions on Computer- Aided Design of Integrated Circuits and Systems 29 (6):911–24. doi:10.1109/TCAD.2010.2048354.
   Web of Science ®Google Scholar
• Foster, I., and C. Kesselman. 2004. The Grid 2: Blueprint for a new computing infrastructure, 2nd ed. San Francisco, California, USA: Elsevier and Morgan Kaufmann.
   Google Scholar
• Freund, R. F., and H. J. Siegel. 1993. Heterogeneous processing. IEEE Computer 26 (6):13–17.
   Google Scholar
• Garey, M. R., and D. S. Johnson. 1979. Computers and intractability: A guide to the theory of NP-completeness. New York, NY: W.H. Freeman and Co.
   Google Scholar
• Hamidzadeh, B., L. Y. Kit, and D. J. Lija. 2000. Dynamic task scheduling using online optimization. IEEE Transactions Parallel Distributed Systems 11 (11):1151–63. doi:10.1109/71.888636.
   Web of Science ®Google Scholar
• Hansen, P., and N. Mladenovic´. 2003. An introduction to variable neighborhood search. In Handbook of MetaHeuristics, Eds. F. Glover and G. A. Kochenberger, 145–84. Amsterdam, Netherlands: Kluwer [Chapter 6].
   Google Scholar
• Hansen, P., N. Mladenovi´C, and J. A. Moreno Pérez. 2008. Variable neighborhood search: Methods and applications. 4OR A Quarterly Journal of Operations Research 6:319–60. doi:10.1007/s10288-008-0089-1.
   Web of Science ®Google Scholar
• Hansen, P., N. Mladenovic´, and J. Moreno Pérez. 2010. Developments of variable neighborhoodsearch. Annals of Operations Research 175 (1):367–407. doi:10.1007/s10479-009-0657-6.
   Web of Science ®Google Scholar
• Hansen, P., N. Mladenovic, and D. Urosevic. 2006. Variable neighborhood search and local branching. Computers and Operations Research 33 (10):3034–45. doi:10.1016/j.cor.2005.02.033.
   Web of Science ®Google Scholar
• He, L., S. A. Jarvis, D. P. Spooner, H. Jiang, D. N. Dillenberger, and G. R. Nudd. 2006. Allocating non-real-time and soft real-time jobs in multiclusters. IEEE Transactions on Parallel and Distributed Systems 17 (2):99–112. doi:10.1109/TPDS.2006.18.
   Web of Science ®Google Scholar
• Hou, E., N. Ansari, and H. Ren. 1994. A genetic algorithm for multiprocessor scheduling. IEEE Transactions on Parallel and Distributed Systems 5 (2):113–20. doi:10.1109/71.265940.
   Web of Science ®Google Scholar
• Hwang, J., Y. Chow, F. Anger, and C. Lee. 1989. Scheduling precedence graphs in systems with interprocessor communication times. SIAM Journal on Computing 18 (2):244–57. doi:10.1137/0218016.
   Web of Science ®Google Scholar
• Ilavarasan, E., P. Thambidurai, and R. Mahilmannan. 2005. Performance effective task scheduling algorithm for heterogeneous computing system. Proceedings of the 4th International Symposium on Parallel and Distributed Computing, France, 28–38.
   Google Scholar
• Iosup, A., C. Dumitrescu, D. Epema, H. Li, and L. Wolters. 2006. How are real grids used? The analysis of four grid traces and its implications. Proceedings of the 7th IEEE/ACM International Conference on Grid Computing, Spain, 262–69.
   Google Scholar
• Kashani, M., and M. Jahanshahi. 2009. Using simulated annealing for task scheduling in distributed systems. Proceedings of the International Conference on Computational Intelligence, Modelling and Simulation (CSSim’09), Brno, Czech Republic 265–69.
   Google Scholar
• Kim, S. J., and J. C. Browne. 1988. A general approach to mapping of parallel computation upon multiprocessor architectures. Proceedings of International Conference on Parallel Processing, 2, 1–8.
   Google Scholar
• Kim, J., J. Rho, J. O. Lee, and M. C. Ko. 2005. CPOC: Effective static task scheduling for grid computing. Proceedings of the International Conference on High Performance Computing and Communications, Italy, 477–86.
   Google Scholar
• Kruatachue, B., and T. G. Lewis. 1988. Grain size determination for parallel processing. IEEE Software 5:23–32. doi:10.1109/52.1991.
   Web of Science ®Google Scholar
• Kwok, Y. K., and I. Ahmad. 1996. Dynamic critical-path scheduling: An effective technique for allocating task graphs to multiprocessors. IEEE Transactions on Parallel and Distributed Systems 7:506–21. doi:10.1109/71.503776.
   Web of Science ®Google Scholar
• Kwok, Y. K., and I. Ahmad. 1999. Static scheduling algorithms for allocating directed task graphs to multiprocessors. ACM Computation Survey 31:406–71. doi:10.1145/344588.344618.
   Web of Science ®Google Scholar
• Liou, J., and M. A. Palis. 1996. An efficient clustering heuristic for: Scheduling DAGs on Multiprocessors. Proceedings of the Symposium on Parallel and Distributed Processing, Dallas, Texas, U.S.A., 152–156.
   Google Scholar
• Liu, H., L. Wang, and J. Liu. 2010. Task scheduling of computational grid based on particle swarm algorithm. Proceedings of the 3rd International Joint Conference on Computational Science and Optimization (CSO), Anhui Province, China, 2, 332–36.
   Google Scholar
• Loudni, S., P. Boizumault, and P. David. 2006. On-line resources allocation for ATM networks with rerouting. Computers and Operations Research 33:2891–917. doi:10.1016/j.cor.2005.01.016.
   Web of Science ®Google Scholar
• Lusa, A., and C. N. Potts. 2008. A variable neighbourhood search algorithm for the constrained task allocation problem. Journal of the Operational Research Society 59:812–22. doi:10.1057/palgrave.jors.2602413.
   Web of Science ®Google Scholar
• Marquis, J., G. Park, and B. Shirazi. 1997. DFRN: A new approach for duplication based scheduling for distributed memory multiprocessor systems. Proceedings of the International Conference on Parallel Processing, Geneva, Switzerland, 157–66.
   Google Scholar
• Meric, L., G. Pesant, and S. Pierre. 2004. Variable neighborhood search for optical routing in networks using latin routers. Annales Des Télécommunications/Annals of Telecommunications 59:261–86.
   Web of Science ®Google Scholar
• Mladenovic´, N., and P. Hansen. 1997. Variable neighborhood search. Computers and Operations Research 24:1097–100. doi:10.1016/S0305-0548(97)00031-2.
   Web of Science ®Google Scholar
• Mladenovic´, N., and P. Hansen. 1999. An introduction to variable neighborhood search. In MetaHeuristics: Advances and trends in local search paradigms for optimization, Eds., S. Voss, I. H. Osman, and C. Roucairol, 449–67. Boston, MA, USA: Kluwer Academic [Chapter 30].
   Google Scholar
• Mladenovic´, N., and P. Hansen. 2001. Variable neighborhood search: Principles and applications. European Journal of Operational Research 130:449–67. doi:10.1016/S0377-2217(00)00100-4.
   Web of Science ®Google Scholar
• Moghaddam, K., F. Khodadadi, and R. Entezari –Maleki. 2012. A hybrid genetic algorithm and variable neighborhood search for task scheduling problem in grid environment. International Workshop on Information and Electronics Engineering Procedia Engineering 29: 3808–14
   Google Scholar
• Mohammad, I. D., and N. Kharma. 2008. A high performance algorithm for static task scheduling in heterogeneous distributed computing systems. Journal of Parallel and Distributed Computing 68:399–409. doi:10.1016/j.jpdc.2007.05.015.
   Web of Science ®Google Scholar
• Mohammad, I. D., and N. Kharma. 2011. A hybrid heuristic–genetic algorithm for task scheduling in heterogeneous processor networks. Journal of Parallel and Distributed Computing 71:1518–31. doi:10.1016/j.jpdc.2011.05.005.
   Web of Science ®Google Scholar
• Nesmachnow, S., E. Alba, and H. Cancela. 2012. Scheduling in heterogeneous computing and grid Environments using a parallel CHC evolutionary Algorithm. Computational Intelligence 28:131–55. doi:10.1111/coin.2012.28.issue-2.
   Web of Science ®Google Scholar
• Nesmachnow, S., H. Cancela, and E. Alba. 2012. A parallel micro evolutionary algorithm for heterogeneous computing and grid scheduling. Applied Soft Computing 12:626–39. doi:10.1016/j.asoc.2011.09.022.
   Web of Science ®Google Scholar
• Radulescu, A., and A. J. C. Van Gemund. 1999. On the complexity of list scheduling algorithms for distributed memory systems. Proceedings of the 13th International Conference on Supercomputing, Portland, Oregon, USA, 68–75, November.
   Google Scholar
• Shanmugapriya, R., S. Padmavathi, and S. Shalinie. 2009. Contention awareness in task scheduling using Tabu search. Proceedings of the IEEE International Advance Computing Conference (IACC), Andhra Pradesh, India 272–77.
   Google Scholar
• Shroff, P., D. W. Watson, N. S. Flann, and R. Freund. 1996. Genetic simulated annealing for scheduling data-dependent tasks in heterogeneous environments. Proceedings of the Heterogeneous Computing Workshop, Honolulu, HI, 98–104.
   Google Scholar
• Sih, G. C., and E. A. Lee. 1993. A compile-time scheduling heuristic for interconnection constrained heterogeneous processor architectures. IEEE Transactions Parallel Distributed Systems 4 (2):175–87. doi:10.1109/71.207593.
   Web of Science ®Google Scholar
• Singh, H., and A. Youssef. 1996. Mapping and scheduling heterogeneous tasks graphs using genetic algorithms. Proceedings of the Heterogeneous Computing Workshop, Honolulu, HI, 86–97.
   Google Scholar
• Song, S., K. Hwang, and Y. K. Kwok. 2006. Risk resilent heuristics and genetic algorithms for security- assured grid job scheduling. IEEE Transactions on Computers 55 (6):703–19. doi:10.1109/TC.2006.89.
   Web of Science ®Google Scholar
• Talukder Khaled Ahsan, A. K. M., M. Kirley, and R. Buyya. 2009. Multiobjective differential evolution for scheduling workflow applications on global Grids. Concurrency and Computation: Practice and Experience 21 (13):1742–56. doi:10.1002/cpe.v21:13.
   Web of Science ®Google Scholar
• Topcuoglu, H., S. Hariri, and M. Y. Wu. 2002. Performance-effective and low-complexity task scheduling for heterogeneous computing. IEEE Transactions Parallel and Distributed Systems 13 (3):260–74. doi:10.1109/71.993206.
   Web of Science ®Google Scholar
• Tsuchiya, T., T. Osada, and T. Kikuno. 1997. A new heuristic algorithm based on gas for multiprocessor scheduling with task duplication. Proceedings of the 3rd International Conference on Algorithms and Architectures for Parallel Processing, Melbourne, Australia, 295–308.
   Google Scholar
• Tumeo, A., C. Pilato, F. Ferrandi, D. Sciuto, and P. Lanzi. 2008. Ant colony optimization for mapping and scheduling in heterogeneous multiprocessor systems. Proceedings of the International Conference on Embedded Computer Systems: Architectures, Modeling, and Simulation (SAMOS), Greece, 142–49.
   Google Scholar
• Ullman, J. D. 1975. NP-complete scheduling problems. Journal of Computer and System Sciences 10 (3):384–93. doi:10.1016/S0022-0000(75)80008-0.
   Web of Science ®Google Scholar
• Viswanathan, S., B. Veeravalli, and T. G. Robertazzi. 2007. Resource-aware distributed scheduling strategies for large-scale computational cluster/grid systems. IEEE Transactions on Parallel and Distributed Systems 18 (10):1450–61. doi:10.1109/TPDS.2007.1073.
   Web of Science ®Google Scholar
• Wang, L. 1997. A genetic-algorithm-based approach for task matching and scheduling in heterogeneous computing environments. Journal of Parallel and Distributed Computing 47 (1):8–22. doi:10.1006/jpdc.1997.1392.
   Web of Science ®Google Scholar
• Wang, C., J. Gu, Y. Wang, and T. Zhao. 2012. A Hybrid heuristic-genetic algorithm for task scheduling in Heterogeneous Multi-core system. Algorithms and Architectures for Parallel Processing, Lecture Notes in Computer Science 7439:153–70.
   Google Scholar
• Wen, Y., H. Xu, and J. Yang. 2011. A heuristic-based hybrid genetic-variable neighborhood search algorithm for task scheduling in heterogeneous multiprocessor system. Informatics Sciences 181:567–81. doi:10.1016/j.ins.2010.10.001.
   Web of Science ®Google Scholar
• Wong, Y. W., R. Goh, S. H. Kuo, and M. Low. 2009 A Tabu search for the heterogeneous dag scheduling problem. Proceedings of the 15th International Conference on Parallel and Distributed Systems, ICPADS, Guangdong, China, 663–70.
   Google Scholar
• Wong, H. M., D. Yu, B. Veeravalli, and T. G. Robertazzi. 2003. Data-Intensive Grid Scheduling: Multiple Sources with Capacity Constraints. Proceedings of the 16th International Conference on Parallel and Distributed Computing and Systems (PDCS ’03) Marina del Rey, USA, 7–11.
   Google Scholar
• Wu, M., and D. Dajski. 1990. Hypertool: A programming aid for message passing systems. IEEE Transactions Parallel Distributed Systems 1 (3):330–43. doi:10.1109/71.80160.
   Google Scholar
• Xhafa, F. 2007. A hybrid evolutionary heuristic for job scheduling on computational grids. Studies in Computational Intelligence 75:269–311.
   Google Scholar
• Xhafa, F., and B. Duran. 2008. Parallel memetic algorithms for independent job scheduling in computational grids. Eds. C. Cotta, and J. van Hemert Recent Advances in Evolutionary Computation for Combinatorial Optimization, vol. 153 of Studies in Computational Intelligence, Springer-Verlag Berlin Heidelberg, 219–39.
   Google Scholar
• Xu, Y., K. Li, L. He, and T. K. Truong. 2013. A DAG scheduling scheme on heterogeneous computing systems using double molecular structure-based chemical reaction optimization. Journal of Parallel and Distributed Computing 73:1306–22. doi:10.1016/j.jpdc.2013.05.005.
   Web of Science ®Google Scholar
• Yang, T., and A. Gerasoulis. 1994. DSC: Scheduling parallel tasks on an unbounded number of processors. IEEE Transactions Parallel and Distributed Systems 5 (9):951–67. doi:10.1109/71.308533.
   Web of Science ®Google Scholar
• Zomaya, A., C. Ward, and B. Macey. 1999. Genetic scheduling for parallel processor systems: Comparative studies and performance issues. IEEE Transactions on Parallel and Distributed Systems 10:795–812. doi:10.1109/71.790598.
   Web of Science ®Google Scholar