Multi-Objective Artificial Bee Colony Algorithms and Chaotic-TOPSIS Method for Solving Flowshop Scheduling Problem and Decision Making
Abstract
Retrieval of optimal solution(s) for a permutation flowshop scheduling problem within a reasonable computational timeframe has been a challenge till yet. The problem includes optimization of various criterions like makespan, total flowtime, earliness, tardiness, etc and obtaining a Pareto solution for final decision making. This paper remodels a discrete artificial bee colony algorithm for permutation flowshop scheduling problem executed through three different scenarios raised the analysis of time complexity measure. To enhance the search procedure, we have explored the alternative and combined use of two local search algorithms named as: iterated greedy search algorithm and iterated local search algorithm in our discrete artificial bee colony algorithm and the results are summarized with respect to completion time, mean weighted tardiness, and mean weighted earliness. The two algorithms are prioritised on insertion and swap of neighbourhood structures which will intensify the local optima in the search space. Further the performance of the algorithm is compared with the test results of multi-objective artificial bee colony algorithm. The result of our optimization process concludes with a set of non-dominated solutions lead to different Pareto fronts. Finally, we propose a chaotic based technique for order of preference by similarity to ideal solution (chaotic-TOPSIS) using a suitable chaotic map for criteria adaptation in order to enhance the decision accuracy in the multi-objective problem domain.
Full Text:
PDFReferences
K R Baker. Introduction to sequencing and scheduling. John Wiley & Sons Inc. New York,1974.
S. M. Johnson. Optimal two- and three-stage production schedules with setup times included. Naval Research Logistics Quarterly, 1(1): 61–68, 1954. https://doi.org/10.1002/nav.3800010110
D. S. Palmer. Sequencing jobs through a multistage process in the minimum total time-a quick method of obtaining a near optimum. Operations Research Society, 16(1): 101–107, 1965. https://doi.org/10.2307/3006688
Jatinder N. D. Gupta. A functional heuristic algorithm for the flow shop scheduling problem. Operations Research Quarterly, 22(1)39–47, 1971. https://doi.org/10.2307/3008015
Herbert G. Campbell, Richard A. Dudek and Milton L. Smith. A heuristic algorithm for the n-job, mmachine sequencing problem. Management Science, 16(10): .630–637, 1970. https://doi.org/10.1287/mnsc.16.10.b630
David G. Dannenbring. An evaluation of flow shop sequencing heuristics. Management Science, 23(11):1174–1182, 1977. https://doi.org/10.1287/mnsc.23.11.1174
Nawaz, Muhammad, Enscore Jr, E Emory and Ham, Inyong. A heuristic for the m-machine n-job flow shop sequencing problem. Omega, 11(1): 91– 95, 1983.
S P Bansal. Minimizing the sum of completion times of n-jobs over m-machines in a flowshop: a branch and bound approach. AIIE Transactions, 9(3):306–311, 1977. https://doi.org/10.1080/05695557708975160
Chia-Shin Chung, James Flynn and Omer Kirca. A branch and bound algorithm to minimize the total flow time for m-machine permutation flowshop problems. International Journal of Production Economics, 79(3): 185–196, 2002. https://doi.org/10.1016/s0925-5273(02)00234-7
Edward Ignall and Linus Schrage. Application of the branch and bound technique to some flow-shop scheduling problems. Operations Research, 13( 3): 400–412, 1965. https://doi.org/10.1287/opre.13.3.400
S.L. van de Velde. Minimizing the sum of the job completion times in the two-machine flow shop by Lagrangian relaxation. Annals of Operations Research, 26(1-4):257–268, 1990. https://doi.org/10.1007/bf03500931
Willem J. Selen and David D. Hott. A mixedinteger goal-programming formulation of the standart flow-shop scheduling problem. Operation Research Society, 37(12) :1121–1128, 1986. https://doi.org/10.2307/2582302
J. M. Wilson. Alternative formulations of a flowshop scheduling problem. Operation Research Society, 40(4): 395–399, 1989. https://doi.org/10.1057/jors.1989.58
Richard L. Daniels and Robert J. Chambers. Multiobjective flowshop scheduling. Naval Research Logistics, 37(6): 981–995, 1990. https://doi.org/10.1002/1520- 6750(199012)37:6%3C981::aidnav3220370617% 3E3.0.co;2-h
Chandrasekharan Rajendran. Heuristics for scheduling in flowshop with multiple objectives. European Journal of Operation Research, 82(3):540–555, 1995. https://doi.org/10.1016/0377-2217(93)e0212-g
Neelam Tyagi, R. P. Tripathi and A. B. Chandramouli. Three Machines Flowshop Scheduling Model with Bicriterion Objective Function, 9(48): 1-14, 2016. https://doi.org/10.17485/ijst/2016/v9i48/103012
S.M. Mousavi, I. Mahdavi, J. Rezaeian and M. Zandieh. Bi-objective scheduling for the re-entrant hybrid flow shop with learning effect and setup times. Scientia Iranica, 25(4): 2233-2253, 2017. https://doi.org/10.24200/sci.2017.4451
Karunakaran Chakravarthy and Chandrasekharan Rajendran. A heuristic for scheduling in flowshop with bi-criteria of makespan and maximum tardiness minimization. Production Planning & Control, 10(7): 707–714, 1999. https://doi.org/10.1080/095372899232777
R.K. Suresh and K.M. Mohanasundaram. Pareto archived simulated annealing for permutation flow shop scheduling with multiple objective. Proceedings of the 2004 IEEE Conference on Cybernetics and Intelligent Systems, 712–717, 2004. https://doi.org/10.1109/iccis.2004.1460675
T.K. Varadharajan and Chandrasekharan Rajendran. A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs. Europian Journal of Operation Research, 167(3): 772–795, 2005. https://doi.org/10.1016/j.ejor.2004.07.020
B. Shahul Hamid Khan and Kannan Govindan. Multi-objective simulated annealing algorithm for permutation flow shop scheduling problem. International Journal of Advanced Operations Management, 3(1):88–100, 2011. https://doi.org/10.1504/ijaom.2011.040661
T. Loukil, J. Teghem and D. Tuyttens. Solving multi-objective production scheduling problems using metaheuristics. European Journal Operation Research, 161(1):42–61, 2005. https://doi.org/10.1016/j.ejor.2003.08.029
Xiangtao Li and Shijing Ma. Multi-objective memetic search algorithm for multi-objective permutation flow shop scheduling problem. IEEE Access, 4: 2154-2165, 2016. https://doi.org/10.1109/access.2016.2565622
Fuyu Yuan, Xin Xu and Minghao Yin. A novel fuzzy model for multi-objective permutation flow shop scheduling problem with fuzzy processing time. Advances in Mechanical Engineering, 11(4):1–9, 2019. https://doi.org/10.1177/1687814019843699
S. Chandrasekaran, S. G. Ponnambalam, R. K. Suresh and N. Vijayakumar. Multi-objective particle swarm optimization algorithm for scheduling in flowshops to minimize makespan, total flowtime and completion time variance. IEEE Congress on Evolutionary Computation, 4012– 4018, 2007. https://doi.org/10.1109/cec.2007.4424994
Vincent T'kindt, Nicolas Monmarché, Fabrice Tercinet and Daniel Laügt. An ant colony optimization algorithm to solve a 2-machine bicriteria flowshop scheduling problem. European Journal of Operation Research, 142(2):250–257, (2002). https://doi.org/10.1016/s0377-2217(02)00265-5
Betul Yagmahan and Mehmet Mutlu Yenisey. Ant colony optimization for multi-objective flow shop scheduling problem. Computers and Industrial Engineering, 54(3):411–420, 2008. https://doi.org/10.1016/j.cie.2007.08.003
B.M.T. Lin, C.Y. Lu, S.J. Shyu and C.Y. Tsai. Development of new features of ant colony optimization for flowshop scheduling. International Journal of Production Economics, 112( 2) :742– 755, 2008. https://doi.org/10.1016/j.ijpe.2007.06.007
M. Ziaee, S.J. Sadjadi, J.L. Bouquard. An Ant Colony Algorithm for the Flowshop Scheduling Problem. Journal of Applied Sciences. 8(21): 3938– 3944, 2008. https://doi.org/10.3923/jas.2008.3938.3944
Dervis Karaboga. An idea based on honey bee swarm for numerical optimization. Technical Report TR06. Computer Engineering Department. Erciyes University. Turkey, 2005.
Dervis Karaboga and Bahriye Basturk. A powerful and efficient algorithm for numerical function optimization: artificial bee colony (ABC) algorithm. Journal of Global Optimization, 39(3):459–471, 2007. https://doi.org/10.1007/s10898-007-9149-x
Dervis Karaboga and B. Basturk. On the performance of artificial bee colony (ABC) algorithm. Applied Soft Computing, 8(1): 687–697, 2008. https://doi.org/10.1016/j.asoc.2007.05.007
Nurhan Karaboga. A new design method based on artificial bee colony algorithm for digital IIR filters. Journal of the Franklin Institute, 346 (4): 328–348, 2009. https://doi.org/10.1016/j.jfranklin.2008.11.003
Dervis Karaboga and Bahriye Akay. A comparative study of artificial bee colony algorithm. Applied Mathematics and Computation, 214 (1):108-132, 2009. https://doi.org/10.1016/j.amc.2009.03.090
Dervis Karaboga and Bahriye Akay. A survey: Algorithms simulating bee swarm intelligence. Artificial Intelligence Review, 31(1-4):68-85, 2009. https://doi.org/10.1007/s10462-009-9127-4
Sangeeta Sharma and Pawan Bhambu. Artificial bee colony algorithm: A survey. International Journal of Computer Applications, 149(4):11-19, 2016. https://doi.org/10.5120/ijca2016911384.
Pradeep Kumar Singh. A systematic review on artificial bee colony optimization technique. International Journal of Control Theory and Applications, 9(11): 5487-5500, 2016.
Tuğçe Anılan, Ergun Uzlu, Murat Kankal and Omer Yuksek. The estimation of flood quantiles in ungauged sites using teaching-learning based optimization and artifcial bee colony algorithms. Scientia Iranica, 2017. https://doi.org/10.24200/sci.2017.4185
Valery Tereshko. Reaction-diffusion model of a honeybee colony’s foraging behaviour, in: PPSN VI. Proceedings of the Sixth International Conference on Parallel Problem Solving from Nature, Springer-Verlag, 807–816, 2000. https://doi.org/10.1007/3-540-45356-3_79
Su-jun Zhang and Xing-sheng Gu. An effective discrete artificial bee colony algorithm for flow shop scheduling problem with intermediate buffers. Journal of Central South University, 22(9):3471−3484, 2015. https://doi.org/10.1007/s11771-015-2887-x
Hoon-Shik Woo and Dong-Soon Yim. A heuristic algorithm for mean flowtime objective in flowshop scheduling. Computers and Operations Research, 25(3):175–182. https://doi.org/10.1016/s0305-0548(97)00050-6
I. Kassabalidis, M.A. El-Sharkawi, R.J. Marks, P. Arabshahi and A.A. Gray. Swarm intelligence for routing in communication networks. Global Telecommunications Conference, 3613–3617, 2001. https://doi.org/10.1109/glocom.2001.966355
M. Fatih Tasgetiren, Quan-Ke Pan, P.N. Suganthan and Angela H-L Chen. A discrete artificial bee colony algorithm for the total flowtime minimization in permutation flowshops. Information Sciences, 181(16): 3459–3475, 2011. https://doi.org/10.1016/j.ins.2011.04.018
Bertrand Mareschal. Weight stability intervals in multicriteria decision aid. Europian Journal of Operation Research, 33(1) :54–64,1988. https://doi.org/10.1016/0377-2217(88)90254-8
Dervis Karaboga, Beyza Gorkemli, Celal Ozturk and Nurhan Karaboga. A comprehensive survey: Artificial bee colony (ABC) algorithm and applications. Artificial Intelligence Review, 42(1): 21-57, 2014. https://doi.org/10.1007/s10462-012-9328-0
E. Taillard, E. Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2):278–285, 1993. https://doi.org/10.1016/0377-2217(93)90182-m
Peng Wang, Yang Li, Yong-Hu Wang and Zhou- Quan Zhu. A new method Based on TOPSIS and Response Surface Method for MCDM problems with interval numbers. Mathematical Problems in Engineering. Article ID 938535, 2015:1-11, 2015. https://doi.org/10.1155/2015/938535
Elissa Nadia Madi, Jonathan M. Garibaldi and Christian Wagner. An exploration of issues and limitations in current methods of TOPSIS and fuzzy TOPSIS. IEEE International Conference on Fuzzy Systems, 2098-2105, 2016. https://doi.org/10.1109/fuzz-ieee.2016.7737950
Alireza Sotoudeh-Anvari, Seyed Jafar Sadjadi, Seyed Mohammad Hadji Molana and Soheil Sadi- Nezhad. A stochastic multi-objective model based on the classical optimal search model for searching for the people who are lost in response stage of earthquake. Scientia Iranica, 26(3):1842:1864, 2019. https://doi.org/10.24200/sci.2018.20226
Edmundas Kazimieras Zavadskas, Abbas Mardani, Zenonas Turskis, Ahmad Jusoh and Khalil MD Nor. Development of TOPSIS method to solve complicated decision-making problems: An overview on developments from 2000 to 2015. International Journal of Information Technology & Decision Making, 15 (3): 1-38, 2016. https://doi.org/10.1142/s0219622016300019
Bing Wu, Likang Zong, Xinping Yan and C. Guedes Soares. Incorporating evidential reasoning and TOPSIS into group decision-making under uncertainty for handling ship without command. Ocean Engineering,164: 590-603, 2018. https://doi.org/10.1016/j.oceaneng.2018.06.054
Ching-Lai Hwang and Kwangsun Yoon. Multiple Attribute Decision Making. Springer-Verlag, Berlin, 58-191, 1981. https://doi.org/10.1007/978-3-642-48318-9_3
Sheldon M. Belenson and Kailash C. Kapur. An algorithm for solving multi-criterion linear programming problems with examples. Operational Research Quarterly, 24(1): 65-77, 1973. https://doi.org/10.2307/3008036
Milan Zelany. A concept of compromise solutions and the method of the displaced ideal’ Computers and Operations Research, 1( 3-4): 479-496,1974. https://doi.org/10.1016/0305-0548(74)90064-1
Gyutai Kim, Chan S Park and K.Paul Yoon. Identifying investment opportunities for advanced manufacturing systems with comparative-integrated performance measurement. International Journal of Production Economics, 50(1): 23-33, 1997. https://doi.org/10.1016/s0925-5273(97)00014-5
Steven Cheng, Christine W. Chan and Guo H. Huang. Using multiple criteria decision analysis for supporting decision of solid waste management. Journal of Environmental Science and Health. Part A, 37(6): 975-990, 2002. https://doi.org/10.1081/ese-120004517
Stelios H. Zanakis, Anthony Solomon, Nicole Wishart and Sandipa Dublish. Multi-attribute decision making: A simulation comparison of selection methods. European Journal of Operational Research, 107(3):507–529, 1998. https://doi.org/10.1016/s0377-2217(97)00147-1
Leandro dos Santos Coelho and Viviana Cocco. Use of chaotic sequences in a biologically inspired algorithm for engineering design and optimization. Expert Systems with Applications, 34(3):1905- 1913, 2008. https://doi.org/10.1016/j.eswa.2007.02.002
Bilal Altlas. Chaotic bee colony algorithms for global numerical optimization. Expert systems with applications, 37(8): 5682-5687, 2010. https://doi.org/10.1016/j.eswa.2010.02.042
Bilal Altlas. Chaotic harmony search algorithms. Applied mathematics and computation, 216( 9): 2687–2699, 2010. https://doi.org/10.1016/j.amc.2010.03.114
Amir Hossein Gandomi, Gun Jin Yun, Xin-She Yang and Siamak Talatahari. Chaos-enhanced accelerated particle swarm algorithm. Communications in Nonlinear Science and Numerical Simulation, 18(2):327–340, 2013. https://doi.org/10.1016/j.cnsns.2012.07.017
Amir Hossein Gandomi, X.-S. Yang, S. Talatahari and A.H. Alavi. Firefly algorithm with chaos. Communications in Nonlinear Science and Numerical Simulation, 18(1): 89–98, 2013. https://doi.org/10.1016/j.cnsns.2012.06.009
Golnar Gharooni-fard, Fahime Moein-darbari, Hossein Deldari and Anahita Morvaridi. Scheduling of scientific workflows using a chaos-genetic algorithm. Procedia Computer Science, 1(1): 1445– 1454, 2010. https://doi.org/10.1016/j.procs.2010.04.160
S. Talatahari, B. Farahmand Azar, R. Sheikholeslami and A.H. Gandomi. Imperialist competitive algorithm combined with chaos for global optimization. Communications in Nonlinear Science and Numerical Simulations, 17(3): 1312– 1319, 2012. https://doi.org/10.1016/j.cnsns.2011.08.021
Wei Gong and Shoubin Wang. Chaos ant colony optimization and application. 4th Inter-national Conference on Internet Computing for Science and Engineering, 301–303, 2009. https://doi.org/10.1109/icicse.2009.38
Ji Mingjun and Tang Huanwen. Application of chaos in simulated annealing. Chaos, Solitons & Fractals, 21(4): 933–941, 2004. https://doi.org/10.1016/j.chaos.2003.12.032
Amir H. Gandomi and Xin-She Yang. Chaotic bat algorithm. Journal of Computational Science, 5(2):224-234, 2014. https://doi.org/10.1016/j.jocs.2013.10.002
DOI: https://doi.org/10.31449/inf.v44i2.2616
This work is licensed under a Creative Commons Attribution 3.0 License.