The week's pick
Reseach Article
Hybridization of Evolutionary Computation Techniques for Job Scheduling Problem
| International Journal of Computer Applications |
| Foundation of Computer Science (FCS), NY, USA |
| Volume 62 - Number 5 |
| Year of Publication: 2013 |
| Authors: V. Selvi, R. Umarani |
10.5120/10077-4691
|
V. Selvi, R. Umarani . Hybridization of Evolutionary Computation Techniques for Job Scheduling Problem. International Journal of Computer Applications. 62, 5 ( January 2013), 24-29. DOI=10.5120/10077-4691
Abstract
In the field of computer science and operation's research, PSO is an optimization algorithm which is inspired by social behaviour of bird flocking and fish schooling. The original PSO was used to solve continuous optimization problems. Crossover and mutation of the particle are modified due to the discrete solution's spaces of scheduling optimization problems. Artificial Bee Colony (ABC) is an optimization algorithm relatively new swarm intelligence technique based on behaviour of honey bee swarm and Meta heuristic. It is successfully applied to various paths mostly continuous optimization problems. Swarm intelligence systems are typically made up of a population of simple agents or boids interacting locally with one another and with their environment. The job scheduling problem is the problem of assigning the jobs in the system in a manner that will optimize the overall performance of the application, while assuring the correctness of the result. PSO and ABC algorithm is proposed in this paper, for solving the job scheduling problem with the criterion to decrease the maximum completion time. In this paper, modifications to the PSO and ABC algorithm is based on Genetic Algorithm (GA) of crossover and mutation operators. Such modifications applied to the creation of new candidate solutions improved performance of the algorithm.
References
- Dror G. Feitelson, Larry Rudolph and Uwe Schwiegelshohn, "Parallel Job Scheduling -A Status Report", In Proeedings of the Conference on JSSPP, pp. 1-16, 2004.
- Ivan Rodero, Francesc Guim and Julita Corbalan, "Evaluation of Coordinated Grid Scheduling Strategies", In Proceedings of 11th IEEE International Conference on High Performance Computing and Communications, Seoul, pp. 1-10, 2009.
- Oliner, Sahoo, Moreira, Gupta and Sivasubramaniam, "Fault-aware Job Scheduling for BlueGene/L Systems", In Proceedings of 18th International Parallel and Distributed Processing Symposium, 2004.
- Grudenic and Bogunovi, "Computer Cluster Scheduling Algorithm Based on Time Bounded Dynamic Programming", In Proceedings of the 34th International Convention on MIPRO, 2011, Opatija, pp. 722-726, 2011
- Abdelrahman Elleithy, Syed S. Rizvi and Khaled M. Elleithy, "Optimization and Job Scheduling in Heterogeneous Networks ", International Joint Conferences on Computer, Information, and Systems Sciences, and Engineering, 2008
- Zhang, Franke, Moreira and Sivasubramaniam, "A Comparative Analysis of Space- and Time-Sharing Techniques for Parallel Job Scheduling in Large Scale Parallel Systems", pp. 1-33, 2008.
- Surekha and Sumathi, "Solution to the Job Shop Scheduling Problem using Hybrid Genetic Swarm Optimization Based on (?, 1)-Interval Fuzzy Processing Time", European Journal of Scientific Research, Vol. 64, No. 2, pp. 168-188, 2011.
- . Bin Cai, Shilong Wang and Haibo Hu, "Hybrid Artificial Immune System for Job Shop Scheduling Problem", World Academy of Science, Engineering and Technology, Vol. 59, No. 18, pp. 81-86, 2011.
- Mohammad Akhshabi, Mostafa Akhshabi and Javad Khalatbari, "Parallel Genetic Algorithm to Solving Job Shop Scheduling Problem", Journal of Applied Sciences Research, Vol. 1, No. 10, pp. 1484-1489, 2011.
- Manish Gupta, Govind sharma, "An Efficient Modified Artificial Bee Colony Algorithm for Job Scheduling Problem", International Journal of Soft Computing and Engineering (IJSCE), Vol. 1, No. 6, pp. 291-296, January 2012.
- Hadi Mokhtari, "Adapting a Heuristic Oriented Methodology for Achieving Minimum Number of Late Jobs with Identical Processing Machines", Research Journal of Applied Sciences, Engineering and Technology, Vol. 4, No. 3, pp. 245-248, 2012.
- Elnaz ZM, Amir MR, Mohammad R, Feizi D (2008). Job Scheduling in Multiprocessor Architecture Using Genetic Algorithm. Proc. IEEE, pp. 248-250.
- Thanushkodi K, Deeba K (2009). An Evolutionary Approach for Job Scheduling in a Multiprocessor Architecture. CiiT Int. J. Artif. Intell. Syst. Mach. Learn. , 1(4).
- Tung-Kuan L, Jinn- Tsong T, Jyh-Hong C (2005). Improved genetic algorithm for the job-shop scheduling problem. International Journal Advanced Manufacture Technology (Spiringer), pp. 1021-1029.
- D. Y. Sha and Hsing-Hung Lin A multi-objective PSO for job-shop scheduling problems Expert Systems with Applications, Volume 37, Issue 2, March 2010, Pages 1065–1070.
- K. Thanushkodi, K. Deeba, On Performance Analysis of Hybrid Algorithm (Improved PSO with Simulated Annealing) with GA, PSO for Multiprocessor Job Scheduling, ISSN: 1109-2750 287 Issue 9, Volume 10, September 2011.
- Kao, Ming-Hsien Chen, and Yi-Ting Huang, Research Article A Hybrid Algorithm Based on ACO and PSO for Capacitated Vehicle Routing Problems, Mathematical Problems in Engineering,Volume 2012.
- Deepak Singh, Ankit Sirmorya, Solving Real Optimization Problem using Genetic Algorithm with Employed Bee (GAEB),International Journal of Computer Applications (0975 – 8887) Volume 42– No. 11, March 2012
- www. wikipedia. org.
Index Terms
Keywords