Santhi VENKATRAMAN, Dharshikha SELVAGOPAL

An optimized multiobjective CPU job scheduling using evolutionary algorithms

Scheduling in a multiprocessor parallel computing environment is an NP-hard optimization problem. The main objective of this work is to obtain a schedule in a distributed computing system (DCS) environment that minimizes the makespan and maximizes the throughput. We study the use of two of the evolutionary swarm optimization techniques, the re y algorithm and the arti cial bee colony (ABC) algorithm, to optimize the scheduling in a DCS. We also enhance the traditional ABC algorithm by merging the genetic algorithm techniques of crossover and mutation with the employed bee phase and the onlooker phase, respectively. The resulting enhanced ABC algorithm is used as the scheduling algorithm and is evaluated against the re y and ABC algorithms. The results obtained show that in a distributed environment with a large number of jobs and resources, multiobjective scheduling using evolutionary algorithms can perform well in terms of minimizing makespan and maximizing throughput.

PDF

___

[1] Drozdowski M. Selected Problems of Scheduling Tasks in Multiprocessor Computer Systems. Poznan, Poland: Politechnika Poznanska, Monogra e, 1997.
[2] Xia W, Wu Z. An effective hybrid optimization approach for multiobjective exible job-shop scheduling problems. Comput Ind Eng 2005; 48: 409-425.
[3] Deb K. Multi-Objective Optimization Using Evolutionary Algorithms. New York, NY, USA: John Wiley & Sons, 2011.
[4] Zitzler E, Thiele L. Multiobjective optimization using evolutionary algorithms | a comparative case study. In: Eiben AE, Back T, Schoenauer M, Schwefel H, editors. Parallel Problem Solving from Nature. Berlin, Germany: Springer, 1998. pp. 292-301.
[5] Koulamas C, Kyparisis GJ. An improved delayed-start LPT algorithm for a partition problem on two identical parallel machines. Eur J Oper Res 2008; 187: 660-666.
[6] Muthiah A, Rajkumar R. A comparison of arti cial bee colony algorithm and genetic algorithm to minimize the makespan for job shop scheduling. In: 12th Global Congress on Manufacturing and Management; 8{10 December 2014; Vellore, India. Amsterdam, the Netherlands: Elsevier. pp. 1745-1754.
[7] Zalzala AMS, Fleming PJ. Genetic Algorithms in Engineering Systems. London, UK: Institution of Electrical Engineers, 1997.
[8] Singh MR, Mahapatra SS. A swarm optimization approach for exible ow shop scheduling with multiprocessor tasks. Int J Adv Manuf Tech 2012; 62: 267-277.
[9] Li JQ, Xie S, Pan Q, Wang S. A hybrid arti cial bee colony algorithm for exible job shop scheduling problems. Int J Comput Commun 2011; 6: 286-296.
[10] Zhang R, Wu C. An arti cial bee colony algorithm for the job shop scheduling problem with random processing times. Entropy 2011; 13: 1708-1729.
[11] Khadwilard A, Chansombat S. Thepphakorn T, Thapatsuwan P, Chainate W, Pongcharoen P. Application of re y algorithm and its parameter setting for job shop scheduling. J Ind Tech 2012; 8: 1-10.
[12] Udaiyakumar KC,Chandrasekaran C. Application of re y algorithm in job shop scheduling problem for minimiza- tion of makespan. In: 12th Global Congress on Manufacturing and Management; 8{10 December 2014; Vellore, India. Amsterdam, the Netherlands: Elsevier. pp. 1798-1807.
[13] Yousif A, Abdulah AH, Nor SM, Bashir MB. Optimizing job scheduling for computational grid based on re y algorithm. In: IEEE Conference on Sustainable Utilization and Development in Engineering and Technology; 6{9 October 2012; Kuala Lumpur, Malaysia. New York, NY, USA: IEEE. pp. 97-101.
[14] Varadharajan TK, Rajendran C. A multi-objective simulated-annealing algorithm for scheduling in owshops to minimize the makespan and total owtime of jobs. Eur J Oper Res 2005; 167: 772-795.
[15] Zhang G, Shao X, Li P, Gao L. An effective hybrid particle swarm optimization algorithm for multi-objective exible job-shop scheduling problem. Comput Ind Eng 2009; 46: 1309-1318.
[16] Karthikeyan S, Asokan P, Nickolas S, Page T. A hybrid discrete re y algorithm for solving multi-objective exible job shop scheduling problems. Int J Bioisp Comp 2015; 7: 386-401.
[17] Marichelvam MK, Prabaharan T, Yang XS. A discrete re y algorithm for the multi-objective hybrid ow shop scheduling problems. IEEE T Evolut Comput 2014; 18: 301-305.
[18] Tavakkoli-Moghaddam R, Jolai F, Vaziri F, Ahmed PK, Azaron A. A hybrid method for solving stochastic job shop scheduling problems. App Math Comput 2005; 170: 185-206.
[19] Yang XS. Fire y algorithms for multimodal optimization. In: Watanabe O, Zeugmann T, editors. Stochastic Algorithms: Foundations and Applications. Berlin, Germany: Springer, 2009. pp. 169-178.
[20] Tasgetiren F, Chen A, Gencyilmaz G, Gattou S. Smallest position value approach. In: Godfrey C Onwubolu, Dav- endra D, editors. Differential Evolution: A Handbook for Global Permutation-Based Combinatorial Optimization. Berlin, Germany: Springer, 2009. pp. 121-138.
[21] Karaboga D, Gorkemli B, Ozturk C, Karaboga N. A comprehensive survey: arti cial bee colony (ABC) algorithm and applications. Artif Intell Rev 2014; 42: 21-57.
[22] Kumar S, Sharma VK, Kumari R. A novel hybrid crossover based arti cial bee colony algorithm for optimization problem. Int J Comput Applic 2013; 82: 18-25.
[23] Singh A, Gupta N, Sinhal A. Arti cial bee colony algorithm with uniform mutation. In: Proceedings of the International Conference on Soft Computing for Problem Solving; 20{22 December 2011; Roorkee, India. Berlin, Germany: Springer. pp. 503-511.
[24] Nachar N. The Mann-Whitney U: a test for assessing whether two independent samples come from the same distribution. Tutorials in Quantitative Methods for Psychology 2008; 4: 13-20.