IJBTT

Optimization of Online Job Shop Partitioning and Scheduling for Heterogeneous Systems using Genetic Algorithm

	International Journal of Computer Trends and Technology (IJCTT)
	© 2016 by IJCTT Journal
	Volume-34 Number-3
	Year of Publication : 2016
	Authors : Sunny Sharma, Gurjit Singh Randhawa
	DOI :  10.14445/22312803/IJCTT-V34P126

Sunny Sharma, Gurjit Singh Randhawa "Optimization of Online Job Shop Partitioning and Scheduling for Heterogeneous Systems using Genetic Algorithm". International Journal of Computer Trends and Technology (IJCTT) V34(3):144-149, April 2016. ISSN:2231-2803. www.ijcttjournal.org. Published by Seventh Sense Research Group.

Abstract -
Job Shop Scheduling problem becomes more complex if heterogeneous systems are considered and algorithm is to be implemented for online schedulers. In real time, number of heterogeneous systems connected to online scheduler may vary from time to time. Also, number of different sized jobs may differ at any instant. This problem deals with optimization of job partitioning when maximum partition size is given; and to find out scheduling criteria when new jobs arrive keeping old jobs status in mind. So, partitioning size for any particular job and make span time for given jobs are optimized at any given instant for given set of jobs. This is known to be NP complete problem therefore many techniques based on different heuristics have been proposed to solve partitioning and scheduling problem efficiently and in reasonable amount of time. This paper proposes the solution to this problem using Genetic algorithm. Variation in number of jobs and systems require very flexible algorithm which can adjust its parameters accordingly; the proposed algorithm is capable and very efficient to handle such issues. This paper covers introduction to problem and various terms used, proposed solution using Genetic Algorithm (GA) with newly designed fitness function and performance comparison of proposed GA under various constraints.

References
[1] A. M. Dell, M. Trubian, ?Applying tabu-search to job shop scheduling problem, Annals of Operations Research, vol. 41, no. 3, pp. 231-252, 1993.
[2] Albert Y.Zomaya, Chris Ward and Ben Macey, ?Genetic Scheduling for Parallel Processor Systems: Comparative Studies and Performance Issues, IEEE Transactions on Parallel and Distributed systems, Vol. 10, No.8, pp.795- 812,August 1999.
[3] Amir Masoud Rahmani and Mojtaba Rezvani, ?A Novel Genetic Algorithm for Static Task Scheduling in Distributed Systems, International Journal of Computer Theory and Engineering, Vol. 1, No. 1, 1793-8201, April 2009
[4] David. E. Goldberg, ?Genetic algorithms in Search, Optimization & Machine learning, Addison Wesley, Publishing Co. Inc. ,Boston, MA, pp- 1-25, 1990.
[5] E. Nowicki, C. Smutnicki, ?A fast taboo search algorithm for the job shop scheduling problem, Management Science, vol. 41, no. 6, pp. 113-125, 1996.
[6] Edwin.S.H Hou, N.Ansari, H.Ren , ?A Genetic Algorithm for Multiprocessor Scheduling, IEEE Transaction on Parallel and Distributed Systems, vol. 5,no. 2, pp.113-120,Feb. 1994.
[7] Erick Cantú-Paz, ?A Survey of Parallel Genetic Algorithms, Department of Computer Science and Illinois Genetic Algorithms Laboratory, University of Illinois at Urbana- Champaign,1998.
[8] Gerasoulis and Yang, ?DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors., IEEE Transactions on Parallel and Distributed Systems, vol. 5, no. 9, pp. 951-967, Sep. 1994.
[9] Imad Fakhri Al Shaikhli and Ismail Khalil , ?An Improved Genetic Algorithm for Solving The Multiprocessor Scheduling Problem, Australian Journal of Basic and Applied Sciences, ISSN 1991-8178, Vol.5, No.12, pp : 947- 951, 2011.
[10] Liang Sun, Xiaochun Cheng, Yanchun Liang, ?Solving Job Shop Scheduling problem Using Genetic Algorithm with Penalty Function, International Journal of Intelligent Information Processing, Volume 1, Number 2, December 2010.
[11] Melanie Mitchell, ?An Introduction to Genetic algorithms, The MIT press, Cambridge, Massachusetts, England, 5th printing, pp 2-20, 1999.
[12] Pratibha Bajpai et al., ?Genetic Algorithm- an Approach to Solve Global Optimization Problems, Indian Journal of Computer Science and Engineering, 2010.
[13] Yi-Hsuan Lee and Cheng Chen, ?A Modified Genetic Algorithm for Task Scheduling in Multiprocessor Systems, Proceedings of 6th International Conference Systems and Applications, IEEE Computer Society, Washington DC,USA, pp. 382-387, 1999.
[14] Wei Wu, Junhu Wei and Xiaohong Guan, ?Hybrid Nested Partitions Algorithm for scheduling in job shop problem, ?Proceedings of the 2009 IEEE International Conference on Robotics and Biomimetics, December 19-23, 2009, Guilin, China.
[15] Sharma MS, Virk RS. A Review towards Evolutionary Multiobjective optimization Algorithms, http://ijoes.vidyapublications.com/paper /Vol13/37- Vol13.pdf.

Keywords
Genetic Algorithm, Optimization, Scheduling.