فهرست:
1- مقدمه .................................................................................................................. 1
1-1 مقدمه ............................................................................................................................ 1
1-2 هدف از اجرای پایاننامه ........................................................................................... 2
1-3 مراحل انجام پایاننامه ............................................................................................... 2
1-4 ساختار پایاننامه ......................................................................................................... 3
2- ادبیات موضوعی .................................................................................................... 4
2-1 مقدمه ............................................................................................................................ 4
2-2 ساختار الگوریتم ژنتیک ............................................................................................. 6
2-3 عملگرهای ژنتیکی ....................................................................................................... 7
2-4 روند کلی الگوریتم ژنتیک .......................................................................................... 8
2-5 شرط پایان الگوریتم .................................................................................................... 10
2-6 برخی از کاربردهای الگوریتم ژنتیک ........................................................................ 10
2-7 تعاریف .............................................................................................................................. 11
2-8 مزایای اجرای موازی ..................................................................................................... 12
2-9 مراحل زمانبندی در گرید ......................................................................................... 16
2-10 انواع زمانبند ................................................................................................................. 17
2-11 انواع زمانبندی ............................................................................................................ 18
2-12 نحوهی زمانبندی (ایستا و پویا) .............................................................................. 19
2-13 ساختار زمانبند ........................................................................................................... 19
2-14 انواع صفبندی کارها ................................................................................................. 21
2-15 پیچیدگی محاسباتی زمانبندی ...............................................................................22
2-16 جمع بندی ............................................................................................................... 22
3- پیشینه پژوهشی .................................................................................................. 23
3-1 مقدمه ............................................................................................................................ 23
3-2 الگوریتمهای حریصانه ............................................................................................... 23
3-3 الگوریتمهای تکاملی .................................................................................................. 26
3-3-1 راهکارهای مبتنی بر جستجوی محلی ................................................ 26
3-3-2 راهکارهای جمعیت محور ...................................................................... 28
3-4 جمعبندی .................................................................................................................. 31
4- الگوریتمهای پیشنهادی ...................................................................................... 33
4-1 مقدمه ............................................................................................................................ 33
4-2 فرضیات وتعاریف ......................................................................................................... 34
4-3 الگوریتم Asuffrage .................................................................................................. 35
4-4 الگوریتم MaxSuffrage ............................................................................................ 36
4-5 الگوریتم توازن نسخه یک ......................................................................................... 38
4-6 الگوریتم توازن نسخه دو ........................................................................................... 40
4-7 الگوریتم ژنتیک و توازن بار ...................................................................................... 41
4-8 جمعبندی ..................................................................................................................... 46
5- نتایج حاصل از ارزیابی........................................................................................... 47
5-1 مقدمه ............................................................................................................................ 47
5-2 محک ارزیابی براون ................................................................................................... 47
5-3 ارزیابی الگوریتم Asuffrage .................................................................................... 49
5-4 ارزیابی الگوریتم MaxSuffrage .............................................................................. 51
5-5 ارزیابی الگوریتم توازن نسخه یک ............................................................................ 53
5-6 ازریابی الگوریتم توازن نسخه دو .............................................................................. 54
5-7 ارزیابی الگوریتم ژنتیک به همراه توازن بار............................................................. 55
5-8 پیشنهادات برای آینده .............................................................................................. 57
6- منابع ..................................................................................................................... 58
منبع:
[1] Lorpunmanee S., Sap M. N., Abdullah A. H.and Chompoo-inwai C. (2007), “An Ant Colony Optimization For Dynamic Job Scheduling In Grid Environment”, International Journal of Computer and Information Science and Engineering, Vol. 3, No. 1, PP. 207-214.
[2] Jacob, B., Brown, M., Fukui, K., and Trivedi, N. (2005), “Introduction to Grid Com-putting”, International Business Machines Corporation.
[3] Tseng, L.Y. and Yang, S.(1997), “Genetic algorithms for clustering , feature selection and classification” ,IEEE Int. Conference on Neural Networks, pp.1612-1616.
[4] Bala, J., Huary, J.,Vafaie, H., De jong, K. and Wechslev,H. (1995), “Hybrid learning using genetic algorithms and decision trees for pattern classification” , IJCAI conference , Montreal , August 19-25.
[5] Siedlecki,W. and Sklansky,J. (1989), “A note on genetic algorithms for large scale pattern selection” , Pattern Recognition Letters , vol.10, pp. 335-347.
[6] Vafaie, H. and De Jong, K. (1993), “Robust feature selection algorithms” , Proc. of the fifth conference on tools for artificial intelligence, Boston, MA: IEEE Computer Society Press., pp. 356-363.
[7] Vafaie, H., and De Jong, K. (1992), “Genetic algorithms as a tool for feature selection in machine learning”, Proc. of the 4th Int. conference on tools with artificial intelligence,pp.200-204 Arlington,VA.
[8] Vafaie,H. and Imam,I. (1994), “Feature selection methods: genetic algorithms vs. greedy-like search”. Proc. of the Int. conference on fuzzy and intelligent control systems.
[9] J. H. Holland, (1975), “Adaptation in natural and artificial systems: An introductory analysis with applications to biology, control, and artificial intelligence”, University of Michigan Press.
[10] K. A. De Jong, (1975), “An analysis of the behavior of a class of genetic adaptive systems”, [PhD Thesis] University of Michigan Ann Arbor, MI, USA.
[11] M. Mitchell, (1996), “An Introduction to Genetic Algorithms”, MIT Press, Cambridge, MA.
[12] D. Beasley, D. Bull and R. Martin, (1993), “An Overview of Genetic Algorithms: Part 1 Fundamentals”, University of Cardiff, Cardiff.
[13] D. Beasley, D. Bull and R. Martin, (1993), “An Overview of Genetic Algorithms: Part 2 Research Topics”, University of Cardiff, Cardiff.
[14] D. E. Goldberg, (1989), “Genetic Algorithms in Search, Optimization and Machine Learning”, Addison Wesley, Reading, MA.
[15] Fogel, D.B, (2000), “ What is Evolutionary Computation?” IEEE Spectrum, pp. 26-32.
[16] Back,T, (1996), “ Evolutionary Algorithms in Theory & Practice “, Oxford University Press.
[17] I. Foster, C. Kesselman, and S. Tuecke, (2001), “The anatomy of the grid: Enabling scalable virtual organizations”, International journal of high performance computing applications, vol. 15, no. 3, pp. 200-222.
[18] F. Xhafa, and A. Abraham, (2010), “Computational models and heuristic methods for Grid scheduling problems”, Future generation computer systems, vol. 26, no. 4, pp. 608-621.
[19] I. Rodero, F. Guim, J. Corbalan et al., (2010), “Grid broker selection strategies using aggregated resource information,” Future Generation Computer Systems, vol. 26, no. 1, pp. 72-86.
[20] B. Plale, P. Dinda, and G. von Laszewski, (2002), “Key concepts and services of a grid information service”, in Proceedings of the 15th International Conference on Parallel and Distributed Computing Systems (PDCS), pp. 437-442.
[21] J. Yu, and R. Buyya, (2005), “A taxonomy of workflow management systems for grid computing,” Journal of Grid Computing, vol. 3, no. 3-4, pp. 171-200.
[22] J. Cao, S. A. Jarvis, S. Saini et al., (2003), “Gridflow: Workflow management for grid computing,” in 3rd IEEE/ACM International Symposium on Cluster Computing and the Grid, Tokyo, Japan, pp. 198-205.
[23] H.-b. ZHANG, L.-s. TANG, and L.-x. LIU, (2009), “Survey of grid scheduling,” Computer Engineering and Design, vol. 9, pp. 026.
[24] V. Subramani, R. Kettimuthu, S. Srinivasan et al., (2002), “Distributed job scheduling on computational grids using multiple simultaneous requests,” in 11th IEEE International Symposium on High Performance Distributed Computing, Edinburgh, Scotland, pp. 359-366.
[25] D. G. Feitelson, and L. Rudolph, (1998), “Metrics and benchmarking for parallel job scheduling,” in Job Scheduling Strategies for Parallel Processing, New York, NY, pp. 1-24.
[26] Fernandef D., (1989), ”Allocating Mudules To Processor In A Distributed System”, IEEE Transactions on Software Engineering, Vol. 15, No. 11,PP. 1427-1436.
[27] Braun T.D., Siegel H.J., Beck N., Boloni L.L., Maheswaran M., Reuther A.L., Robertson J.P. and Theys M.D., Yao B., (2001), “A comparison of eleven static heuristics for mapping a class of independent tasks onto heterogeneous distributed computing systems”, Journal of Parallel and Distributed Computing, Vol. 61, No. 6,PP. 810-837.
[28] Ritchie G. andLevine J. (2003),“A Fast, Effective Local Search For Scheduling Independent JobsIn Heterogeneous Computing Environments”, Proceedings of the 22nd Workshop of the UK Planning and Scheduling Special Interest Group,Mar 15 -20,Glasgow Scotland, PP. 59-65.
[29] YarKhan A. and Dongarra J. (2002), “Experiments With Scheduling Using Simulated Annealing In A Grid Environment”, In Proceedings of the 3rd International Workshop on Grid Computing, July 12-15, Baltimore USA, PP. 232-242.
[30] Ritchie G. (2003),“Static Multi-Processor Scheduling With Ant Colony Optimisation& Local Search”, Master of Science thesis, University of Edinburgh.
[31] Zomaya A. Y. and Teh Y. H. (2001), “Observations On Using Genetic Algorithms For Dynamic Load-Balancing”, IEEE Transactions on Parallel and distributed systems,Vol. 12, No. 2, PP. 899-911.
[32] Xhafa F., Alba E., Dorronsoro B., Duran B. and Abraham, A. (2008), “Efficient Batch Job Scheduling In Grids Using Cellular Memetic Algorithms”, Metaheuristics for Scheduling in Distributed Computing Environments, Vol. 146, No. 2, PP. 273-299.
[33] S. Nesmachnow, H. Cancela, and E. Alba. (2011), “Heterogeneous computing with volutionary algorithms.” Soft Computing, Vol. 15, Issue. 4, pp. 685–701.
[34] S. Nesmachnow, H. Cancela, and E. Alba. (2012), “A parallel micro evolutionary algorithm for heterogeneous computing and grid scheduling.” Applied Soft Computing, Vol. 12, Issue. 2, pp. 626–639.
[35] A. K. Chaturvedi, R. Sahu, (2011), “New Heuristic for Scheduling of Independent Tasks in Computational Grid”, International Journal of Grid and Distributed Computing, Vol. 4 25-36.
[36] F. Xhafa, J. Carretero, E. Alba, and B. Dorronsoro, (2008), “Design and evaluation of tabu search method for job scheduling in distributed environments.” In Proceedings of the 21th International Parallel and Distributed Processing Symposium, pages 1-8.