Task scheduling problem can be defined as a method to schedule tasks for execution . Task scheduling in multiprocessor system is also called as multiprocessor scheduling , and is long studied and difficult problems that continues to be a topic of considerable research. Task scheduling in multiprocessor is a term that can defined as finding a schedule for a general task graph to be executed on a multiprocessor system so that execution time can be minimized. Efficient multiprocessor task scheduling is essentially the problem of allocating a set of computational jobs to a set of processors to minimize the overall execution time. This is NP- complete problem that can be solved only by search techniques and heuristic. Genetic algorithm is the best search technique for solving this problem because they are known to provide robust, stochastic solutions for numerous optimization problems .

Task Scheduling, Genetic Algorithms, Scheduling, Multiprocessor System, Mutation, Crossover

[1] G. Syswerda and J. Palmucci, �The application of genetic algorithms to resource scheduling�, Proceedings of the Fourth International Conference on Genetic Algorithms and Their Applications, pages 502-508, San Mateo, CA, July 1991.
[2] G. A. Cleveland and S. F. Smith, �Using genetic algorithms to schedule flow shop releases�, Proceedings of the Third International Conference on Genetic Algorithms and Their Applications, pages 160-169, San Mateo, CA, June 1989.
[3] J. H. Holland, �Adaptation in Natural and Artificial Systems�, The University of Michigan Press, Ann Arbor, MI, 1975.
[4] Cottet, F., Delacroix, J, Kaiser, C., Mammeri, Z., �Scheduling in Real-time Systems�, John Wiley & Sons Ltd, England, 2002.
[5] Goldberg, David E, �Genetic Algorithms in Search, Optimization and Machine Learning�, Kluwer Academic Publishers, Boston, 1989.
[6] Mitchell, Melanie, �An Introduction to Genetic Algorithms�, MIT Press, Cambridge, MA. 1996.
[7] L.M.Schmitt, �Fundamental Study Theory of Genetic Algorithms�, International Journal of Modelling and Simulation Theoretical Computer Science. 2001.
[8] C. V. Ramamoorthy, "Optimal scheduling strategies in a multiprocessor system", IEEE Trans. Computers, vol. C-2I.,Feb. 1972.
[9] I. H. Kasahara and S. Narita, "Practical multiprocessing scheduling algorithms for efficient parallel processing", IEEE Transactions on Computers, 1998.
[10] E. S. H. Hou, R. Hong, and N. Ansari, �Efficient multiprocessor scheduling based on genetic algorithms�, IEEE 1990.
[11] Muhhamad K. Dhodhi, Imtiaz Ahmad, Ishfaq ahmad, �A multiprocessor scheduling scheme using Problem-space genetic algorithms�, IEEE 1995.
[12] Michael Bohler, Frank Moore, Yi Pan, �Multiprocessor Scheduling Using Genetic Algorithms�, Twelfth International FLAIRS Conference, 1999.
[13] Yi-Wen Zhongiz, Jian-Gang Yang, �A Genetic algorithm for tasks scheduling in parallel multiprocessor systems�, Proceedings of the Second International Conference on Machine Learning and Cybernetics, Xi`an, 2-5 November 2003
[14] Michael Rinehart, Vida Kianzad, and Shuvra S. Bhattacharyya, �A Modular Genetic Algorithm for Scheduling Task Graphs�, 2003.
[15] Andrew J. Page and Thomas J. Naughton, �Framework for task scheduling in heterogeneous distributed computing using genetic algorithms�, pp. 1-14, 2005.
[16] Andrew J. Page and Thomas J. Naughton, �Dynamic task scheduling using genetic algorithms for heterogeneous distributed computing�, 2005.
[17] Faezeh Montazeri, Mehdi Salmani-Jelodar, S. Najmeh Fakhraie and S. Mehdi Fakhraie, �Evolutionary Multiprocessor Task Scheduling�, Proceedings of the International Symposium on Parallel Computing in Electrical Engineering (PARELEC`06), IEEE 2006.
[18] M. Salmani Jelodar, S. N. Fakhraie, F. Montazeri, S. M. Fakhraie, M. Nili Ahmadabadi, �A Representation for Genetic-Algorithm-Based Multiprocessor Task Scheduling�, Congress on Evolutionary Computation, Vancouver, BC, Canada, IEEE July 16-21, 2006.
[19] M. Nikravan and M. H. Kashani, �A Genetic algorithm for process scheduling in distributed operating system considering load balancing �, Proceedings 21st European Conference on Modelling and Simulation, 2007.
[20] Keshav Dahal, Alamgir Hossain, Benzy Varghese, �Scheduling in Multiprocessor System Using Genetic Algorithms�, 7th Computer Information Systems and Industrial Management Applications, IEEE 2008.
[21] Amir Masoud Rahamani, Mohamad Ali Vahedi �A novel Task Scheduling in Multiprocessor Systems with Genetic Algorithm by using Elitism stepping method�, 2008.
[22] Yajun Li, Yuhang Yang, Maode Ma, Rongbo Zhu, �A Problem-Specific Genetic Algorithm for Multiprocessor Real-time Task Scheduling�, The 3rd Intetnational Conference on Innovative Computing Information and Control (ICICIC`08), IEEE 2008.
[23] Peyman Almasi Nejad, Ahmad Farahi, Davood Karim Zadegan Moghadam, Reza Asgary Moghadam, �An Intelligent Method for Multi Processor Scheduling using Genetic Algorithms�, International Conference on MultiMedia and Information Technology, IEEE 2008.
[24] Ali Pedram, �A method for scheduling multi processing systems with genetic algorithm�, International Journal of Engineering and Technology Vol. 1, No. 2, June, 2009.
[25] Intisar A.Majied Al-Said, Nedhal Al-Saiyd, Firas Turki Attia, �Multiprocessor scheduling based on genetic algorithms�, 2009.
[26] Sachi Gupta, Gaurav Agarwal, �Task Scheduling in Multiprocessor System Using Genetic Algorithm�, Second International Conference on Machine Learning and Computing, IEEE 2010.
[27] Adel Manaa and Chengbin Chu, �Scheduling multiprocessor tasks to minimize the makespan on two dedicated processors�, European Journal of Industrial Engineering, pp. 265 � 279, Volume 4, Number 3 / 2010.
[28] Amir Masoud Rahmani and Mojtaba Rezvani, �A Novel Genetic Algorithm for Static Task Scheduling in Distributed Systems�, 2009.
[29] Carnegie-Mellon, �Genetic Algorithms and Their Applications�, Proc. of the First Int. Conference, July 24-26, 1985.
[30] Dr. Franz Rathlauf, �Representations for Genetic and Evolutionary Algorithms�, 2nd edition, @ Springer. 2006.
[31] S. Beaty, �Genetic algorithms and instruction scheduling�, Proceedings of the 24th Microprogramming Workshop (MICRO-24), Albuquerque, NM, November 1991.
[32] John J. Grefenstette, �Genetic Algorithms and Their Applications�, Proc. 2nd Int. Conf, July 28-31, 1987, MIT, Cambridge,1987.
[33] Davis, �Handbook of Genetic Algorithms�, Van Nostrand Reinhold, 1991.
[34] E. Hou, R. Hong, and N. Ansari, "Multiprocessor scheduling based on genetic algorithms", Dept of ECE, New Jersey Institute of Technology, Technical Report, Aug. 1990.
[35] Michalewicz, �Genetic Algorithms + Data Structures = Evolution Programs�, Springer, 1996.
[36] Goldberg D., �Genetic Algorithms in Search, Optimization, and Machine Learning�, Addison-Wessley publishing company Inc., 1989.
[37] Allen, F. & Karjalainen, �Using Genetic Algorithms to Find Technical Trading Rules�, Journal of Financial Economics, 1999.
[38] Forrest, Stephanie. "Genetic algorithms: principles of natural selection applied to computation", Science, vol.261, 1993.
[39] Kirkpatrick, S., C.D. Gelatt and M.P. Vecchi, "Optimization by simulated annealing", Science, vol.220, p.671-678, 1983.
[40] Tang, K.S., K.F. Man, S. Kwong and Q. He. "Genetic algorithms and their applications", IEEE Signal Processing Magazine, vol.13, 2004.
[41] Michael Bohler, Frank Moore, Yi Pan. �Improved Multiprocessor Task Scheduling Using Genetic Algorithms�, Twelfth International FLAIRS Conference, 1999.
[42] S.N.Sivanandam, S.N.Deepa, �Introduction to Genetic Algorithms�, Springer-Verlag Berlin Heidelberg, 2008.
[43] Forrest, Stephanie. "Genetic algorithms: principles of natural selection applied to computation" Science, vol.261. 1993.
[44] G. Syswerda, �Uniform crossover in genetic algorithms�, Proceedings of the Third International Conference on Genetic Algorithms and Their Applications, pages 2-9, San Mateo, CA, June 1989.
[45] G. G. Robertson, �Population size in classifier systems�, Proceedings of the Fifth International Workshop on Machine Learning, pages 142-152, San Mateo, CA, June 1988.
[46] M. F. Bramlette, �Initialization, mutation and selection methods in genetic algorithms for function optimization�, Proceedings of the Fourth International Conference on Genetic Algorithms and Their Applications, pages 100-107, San Mateo, CA, July 1991.
[47] Whitley, D., �A genetic algorithm tutorial�, Statistics and Computing�, 1994.
[48] Vose, Michael D, �The Simple Genetic Algorithm: Foundations and Theory�, MIT Press, Cambridge, MA, 1999.
[49] J. J. Grefenstette and J. E. Baker, �How genetic algorithms work: A critical look at implicit parallelism�, Proceedings of the Third International Conference on Genetic Algorithms and Their Applications, pages 20-27, San Mateo, CA, June 1989.
[50] K. A. De Jong, �An Analysis of the Behavior of a Class of Genetic Adaptive Systems�, Ph.D. dissertation, University of Michigan, 1975.