International Journal of Intelligent Systems and Applications (IJISA)
IJISA Vol. 8, No. 4, 8 Apr. 2016
Cover page and Table of Contents: PDF (size: 1825KB)
Hybrid Black Hole Algorithm for Bi-Criteria Job Scheduling on Parallel Machines
Full Text (PDF, 1825KB), PP.1-17
Views: 0 Downloads: 0
Author(s)
Kawal Jeet
1,*
Renu Dhir
2
Paramvir Singh
2
Index Terms
Auxiliary archive, Black Hole algorithm, Genetic algorithm, Job scheduling, Nature-inspired algorithm, Tardiness, Weighted flow time
Abstract
Nature-inspired algorithms are recently being appreciated for solving complex optimization and engineering problems. Black hole algorithm is one of the recent nature-inspired algorithms that have obtained inspiration from black hole theory of universe. In this paper, four formulations of multi-objective black hole algorithm have been developed by using combination of weighted objectives, use of secondary storage for managing possible solutions and use of Genetic Algorithm (GA). These formulations are further applied for scheduling jobs on parallel machines while optimizing bi-criteria namely maximum tardiness and weighted flow time. It has been empirically verified that GA based multi-objective Black Hole algorithms leads to better results as compared to their counterparts. Also the use of combination of secondary storage and GA further improves the resulting job sequence. The proposed algorithms are further compared to some of the existing algorithms, and empirically found to be better. The results have been validated by numerical illustrations and statistical tests.
Cite This Paper
Kawal Jeet, Renu Dhir, Paramvir Singh, "Hybrid Black Hole Algorithm for Bi-Criteria Job Scheduling on Parallel Machines", International Journal of Intelligent Systems and Applications(IJISA), Vol.8, No.4, pp.1-17, 2016. DOI:10.5815/ijisa.2016.04.01
Reference
[1]X. S. Yang, Z. Cui, R. Xiao, A. H. Gandomi, and M. Karamanoglu, Swarm intelligence and bio-inspired computation: theory and applications, 1st ed., Oxford:Elsevier, 2013.
[2]F. Dressler and O. B. Akan, "A survey on bio-inspired networking," Computer Networks, vol. 54, pp. 881-900, 2010.
[3]M. Farahmandian and A. Hatamlou, "Solving optimization problems using black hole algorithm," Journal of Advanced Computer Science & Technology, vol. 4, pp. 68-74, 2015.
[4]K. Jeet and R. Dhir, "Software Architecture Recovery using Genetic Black Hole Algorithm," ACM SIGSOFT Software Engineering Notes, vol. 40, pp. 1-5, 2015.
[5]D. Karaboga, B. Gorkemli, C. Ozturk, and N. Karaboga, "A comprehensive survey: artificial bee colony (ABC) algorithm and applications," Artificial Intelligence Review, vol. 42, pp. 21-57, 2014.
[6]A. Khadwilard, et al., "Application of firefly algorithm and its parameter setting for job shop scheduling," in First Symposium on Hands-On Research and Development, 2011.
[7]R. Raju, J. Amudhavel, N. Kannan, and M. Monisha, "A bio inspired Energy-Aware Multi objective Chiropteran Algorithm (EAMOCA) for hybrid cloud computing environment," in Green Computing Communication and Electrical Engineering (ICGCCEE), 2014 International Conference on, 2014, pp. 1-5.
[8]B. Ramesh, V. C. J. Mohan, and V. V. Reddy, "Application of bat algorithm for combined economic load and emission dispatch," Int. J. of Electricl Engineering and Telecommunications, vol. 2, pp. 1-9, 2013.
[9]M. Saleem, G. A. Di Caro, and M. Farooq, "Swarm intelligence based routing protocol for wireless sensor networks: Survey and future directions," Information Sciences, vol. 181, pp. 4597-4624, 2011.
[10]X. S. Yang and S. Deb, "Engineering optimisation by cuckoo search," International Journal of Mathematical Modelling and Numerical Optimisation, vol. 1, pp. 330-343, 2010.
[11]X. S. Yang and X. He, "Firefly algorithm: recent advances and applications," International Journal of Swarm Intelligence, vol. 1, pp. 36-50, 2013.
[12]C. A. Floudas, et al., Handbook of test problems in local and global optimization, vol. 33: Springer Science & Business Media, 2013. Doi: 10.1007/978-1-4757-3040-1
[13]X. S. Yang and S. Deb, "Multiobjective cuckoo search for design optimization," Computers & Operations Research, vol. 40, pp. 1616-1624, 2013.
[14]X. S. Yang, "Bat algorithm for multi-objective optimisation," International Journal of Bio-Inspired Computation, vol. 3, pp. 267-274, 2011.
[15]P. Chaudhari, R. Dharaskar, and V. Thakare, "Computing the most significant solution from Pareto front obtained in multi-objective evolutionary," International Journal of Advanced Computer Science and Applications, vol. 1, pp. 63-68, 2010.
[16]A. Hatamlou, "Black hole: A new heuristic optimization approach for data clustering," Information Sciences, vol. 222, pp. 175-184, 2013.
[17]A. J. Ruiz-Torres, E. E. Enscore, and R. R. Barton, "Simulated annealing heuristics for the average flow-time and the number of tardy jobs bi-criteria identical parallel machine problem," Computers & industrial engineering, vol. 33, pp. 257-260, 1997.
[18]A. Rahimi-Vahed, B. Javadi, M. Rabbani, and R. Tavakkoli-Moghaddam, "A multi-objective scatter search for a bi-criteria no-wait flow shop scheduling problem," Engineering Optimization, vol. 40, pp. 331-346, 2008.
[19]P. T. Chang, et al., "Ant colony optimization system for a multi-quantitative and qualitative objective job-shop parallel-machine-scheduling problem," International Journal of Production Research, vol. 46, pp. 5719-5759, 2008.
[20]T. Eren, "A bicriteria m-machine flowshop scheduling with sequence-dependent setup times," Applied Mathematical Modelling, vol. 34, pp. 284-293, 2010.
[21]A. Berrichi, L. Amodeo, F. Yalaoui, E. Châtelet, and M. Mezghiche, "Bi-objective optimization algorithms for joint production and maintenance scheduling: application to the parallel machine problem," Journal of Intelligent Manufacturing, vol. 20, pp. 389-400, 2009.
[22]A. Berrichi, F. Yalaoui, L. Amodeo, and M. Mezghiche, "Bi-objective ant colony optimization approach to optimize production and maintenance scheduling," Computers & Operations Research, vol. 37, pp. 1584-1596, 2010.
[23]M. M. Mazdeh, F. Zaerpour, A. Zareei, and A. Hajinezhad, "Parallel machines scheduling to minimize job tardiness and machine deteriorating cost with deteriorating jobs," Applied Mathematical Modelling, vol. 34, pp. 1498-1510, 2010.
[24]E. Rashidi, M. Jahandar, and M. Zandieh, "An improved hybrid multi-objective parallel genetic algorithm for hybrid flow shop scheduling with unrelated parallel machines," The International Journal of Advanced Manufacturing Technology, vol. 49, pp. 1129-1139, 2010.
[25]M. Guezouri and A. Houacine, "Hybrid Flow Shop Scheduling Problem Using Artificial Immune System," International Journal of Intelligent Systems and Applications (IJISA), vol. 4, pp. 82, 2012.
[26]S. Larbi and S. Mohamed, "Modeling the Scheduling Problem of Identical Parallel Machines with Load Balancing by Time Petri Nets," International Journal of Intelligent Systems and Applications (IJISA), vol. 7, pp. 42, 2014.
[27]J. Q. Li, Q.K. Pan, and M. F. Tasgetiren, "A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities," Applied Mathematical Modelling, vol. 38, pp. 1111-1132, 2014.
[28]S. Sharma, D. Gupta, and S. Sharma, "Bicriteria scheduling on parallel machines: total tardiness and weighted flowtime in fuzzy environment," International Journal of Mathematics in Operational Research, vol. 5, pp. 492-507, 2013.
[29]A. Konak, D. W. Coit, and A. E. Smith, "Multi-objective optimization using genetic algorithms: A tutorial," Reliability Engineering & System Safety, vol. 91, pp. 992-1007, 2006.
[30]K. Deb, "Multi-objective optimization," in Search methodologies, E. K. Burke and G. Kendall, Eds. U.S.A: Springer, 2014, pp. 403-449. Doi: 10.1007/978-1-4614-6940-7_15
[31]C. A. C. Coello, G. T. Pulido, and M. S. Lechuga, "Handling multiple objectives with particle swarm
optimization," Evolutionary Computation, IEEE Transactions on, vol. 8, pp. 256-279, 2004.
[32]J. D. Knowles and D. W. Corne, "Approximating the nondominated front using the Pareto archived evolution strategy," Evolutionary computation, vol. 8, pp. 149-172, 2000.
[33]K. Deb, Multi-objective optimization using evolutionary algorithms, vol. 16. New York: John Wiley & Sons, 2009.
[34]K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan, "A fast and elitist multiobjective genetic algorithm: NSGA-II," Evolutionary Computation, IEEE Transactions on, vol. 6, pp. 182-197, 2002.
[35]In.mathworks.com. (2014, 16 December 2013). MATLAB - The Language of Technical Computing - B.
[36]D. J. Sheskin, Handbook of parametric and nonparametric statistical procedures, 4th ed., London: Crc Press, 2003, pp.189-199.