İhsan SABUNCUOĞLU, Berna DENGİZ, Çiğdem ALABAŞ USLU, Canan AĞLAN

Modified self-adaptive local search algorithm for a biobjective permutation flow shop scheduling problem

Interest in multiobjective permutation flow shop scheduling (PFSS) has increased in the last decade toensure effective resource utilization. This study presents a modified self-adaptive local search (MSALS) algorithm for thebiobjective permutation flow shop scheduling problem where both makespan and total flow time objectives are minimized.Compared to existing sophisticated heuristic algorithms, MSALS is quite simple to apply to different biobjective PFSSinstances without requiring effort or time for parameter tuning. Computational experiments showed that MSALS is eithersuperior to current heuristics for Pareto sets or is incomparable due to other performance indicators of multiobjectiveproblems.

PDF

___

[1] Minella G, Ruiz R, Ciavotta M. Restarted iterated Pareto greedy algorithm for multi-objective flowshop scheduling problems. Computers & Operations Research 2011; 38 (11): 1521-1533.
[2] Fowler JW, Kim B, Carlyle WM, Senturk Gel E, Horng SM. Evaluating solution sets of a posterior solution techniques for bi-criteria combinatorial optimization problems. Journal of Scheduling 2005; 8: 75-96.
[3] Yenisey M, Yagmahan B. Multi-objective permutation flow shop scheduling problem: literature review, classification and current trends. Omega 2014; 45: 119-135.
[4] Minella G, Ruiz R, Ciavotta M. A review and evaluation of multiobjective algorithms for the flowshop scheduling problem. INFORMS Journal on Computing 2008; 20 (3): 451-471.
[5] Coy SP, Golden BL, Runger GC, Wasil EA. Using experimental design to find effective parameter settings for heuristics. Journal of Heuristics 2000; 7: 77-97.
[6] Adenso-Diaz B, Laguna M. Fine-tuning of algorithms using fractional experimental design and local search. Operations Research 2006; 54 (1): 99–114.
[7] Bartz-Beielstein T. Experimental Research in Evolutionary Computation: The New Experimentalism Natural Computing Series. Berlin, Germany: Springer Verlag, 2006.
[8] Dobslaw F. A parameter tuning framework for metaheuristics based on design of experiments and artificial neural networks. In: Proceedings of the International Conference on Computer Mathematics and Natural Computing; Rome, Italy; 2010. pp. 1–4.
[9] Arin A, Rabadi G, Unal R. Comparative studies on design of experiments for tuning parameters in a genetic algorithm for a scheduling problem. International Journal of Experimental Design and Process Optimisation 2011; 2 (2): 103–124.
[10] Birattari M, Stutzle T, Paquete L, Varrentrapp K. A racing algorithm for configuring metaheuristics. In: GECCO 2002 Proceedings of the Genetic and Evolutionary Computation Conference; New York, NY, USA; 2002. pp. 11–18.
[11] Balaprakash P, Birattari M, Stutzle T. Improvement strategies for the F-Race algorithm: sampling design and iterative refinement. In: Bartz Beielstein T (editor). 4th International Workshop on Hybrid Metaheuristics, Proceedings of Lecture Notes in Computer Science. Berlin, Germany: Springer Verlag, 2007. pp. 108–122.
[12] Barbosa EBM, Senne ELF, Silva MB. Improving the performance of metaheuristics: an approach combining response surface methodology and racing algorithms. International Journal of Engineering Mathematics 2015; 2015: 167031. doi: 1155/2015/167031
[13] López-Ibáñez M, Dubois-Lacoste J, Pérez Cáceres L, Stützle T, Birattari M. The irace package: iterated racing for automatic algorithm configuration. Operations Research Perspectives 2016; 3: 43-58.
[14] Eberhart R, Kennedy J. A new optimizer using particle swarm theory. In: Proceedings of the Sixth International Symposium on Micro Machine and Human Science; Nogaya, Japan; 1995. pp. 39–43.
[15] Nannen V, Eiben AE. A method for parameter calibration and relevance estimation in evolutionary algorithms. In: Proceedings of Genetic and Evolutionary Computation Conference; Seattle, WA, USA; 2006. pp. 183–190.
[16] Meissner M, Schmuker M, Schneider G. Optimized particle swarm optimization (OPSP) and its application to artificial neural network training. BMC Bioinformatics 2006; 7: 125. doi: 10.1186/1471-2105-7-125
[17] Hutter F, Hoos H, Stutzle T. Automatic algorithm configuration based on local search. In: Proceedings of the Twenty-Second Conference on Artificial Intelligence; Vancouver, Canada; 2007. pp. 1152–1157.
[18] Hutter F, Hoos HH, Leyton-Brown K, Stutzle T. ParamILS: An automatic algorithm configuration framework. Journal of Artificial Intelligence Research 2009; 36: 267–306.
[19] Smit SK, Eiben AE. Comparing parameter tuning methods for evolutionary algorithms. In: IEEE Congress on Evolutionary Computation; Trondheim, Norway; 2009. pp. 399–406.
[20] Neumüller C, Wagner S, Kronberger G, Affenzeller M. Parameter meta-optimization of metaheuristic optimization algorithms. In: Proceedings of the 13th International Conference on Computer Aided Systems Theory; Las Palmas de Gran Canaria, Spain; 2011. pp. 367-374.
[21] Eiben AE, Smit SK. Parameter tuning for configuring and analyzing evolutionary algorithms. Swarm and Evolutionary Computation 2011; 1 (1): 19-31.
[22] Ren Z, Jiang H, Xuan J, Luo Z. Hyper-heuristics with low level parameter adaptation. Evolutionary Computation 2012; 20 (2): 189-227.
[23] Hansen N. An analysis of mutative σ -self-adaptation on linear fitness functions. Evolutionary Computation 2006; 14 (3): 255–275.
[24] Eiben AE, Michalewicz Z, Schoenauer M, Smith JE. Parameter control in evolutionary algorithms. In: Lobo F, Lima CF, Michalewicz Z (editors). Parameter Setting in Evolutionary Algorithms. Berlin, Germany: Springer, 2007. pp. 19-46.
[25] Meignan D, Koukam A, Creput JC. Coalition-based metaheuristic: a self-adaptive metaheuristic using reinforcement learning and mimetism. Journal of Heuristics 2010; 16 (6): 859–879.
[26] Serpell MC, Smith JE. Self-adaptation of mutation operator and probability for permutation representations in genetic algorithms. Evolutionary Computation 2010; 18 (3): 491–514.
[27] Stützle T, López-Ibáñez M, Pellegrini P, Maur M, Montes de Oca MA et al. Parameter adaptation in ant colony optimization. In: Hamadi Y, Monfroy E, Saubion F (editors). Autonomous Search. Berlin, Germany: Springer, 2012. pp. 191-215.
[28] Alabas-Uslu C, Dengiz B. A self-adaptive heuristic algorithm for combinatorial optimization problems. International Journal of Computational Intelligence Systems 2014; 7 (5): 827-852.
[29] Dengiz B, Alabas-Uslu C. A self-tuning heuristic for design of communication networks. Journal of the Operational Research Society 2015; 66 (7): 1101-1114.
[30] Alabas-Uslu C. A self-tuning heuristic for a multi-objective vehicle routing problem. Journal of the Operational Research Society 2008; 59 (7): 988-996.
[31] Taillard E. Benchmarks for basic scheduling problems. European Journal of Operational Research 1993; 64 (2): 278-285.
[32] Varadharajan TK, Rajendran C. A multi-objective simulated-annealing algorithm for scheduling in flowshops to minimize the makespan and total flowtime of jobs. European Journal of Operational Research 2005; 167 (3): 772-795.
[33] Arroyo JEC, Armentano VA. Genetic local search for multi-objective flowshop scheduling problems. European Journal of Operational Research 2005; 167 (3): 717-738.
[34] Armentano VA, Claudio JE. An application of a multi-objective tabu search algorithm to a bicriteria flowshop problem. Journal of Heuristics 2004; 10 (5): 463-481.
[35] Framinan JM, Leisten R. A multi-objective iterated greedy search for flowshop scheduling with makespan and flowtime criteria. OR Spectrum 2008; 30 (4): 787-804.
[36] Rajendran C, Ziegler H. Computational Intelligence in Flow Shop and Job Shop Scheduling: A Multi-Objective Ant-Colony Algorithm for Permutation Flowshop Scheduling to Minimize the Makespan and Total Flowtime of Jobs. Berlin, Germany: Springer, 2009.
[37] Dubois-Lacoste J, López-Ibáñez M, Stützle T. A hybrid TP+PLS algorithm for bi-objective flow-shop scheduling problems. Computers & Operations Research 2011; 38 (8): 1219-1236.
[38] Lin SW, Ying KC. Minimizing makespan and total flowtime in permutation flowshops by a bi-objective multi-start simulated-annealing algorithm. Computers & Operations Research 2013; 40 (6): 1625-1647.
[39] Blot A, Kessaci MÉ, Jourdan L, Hoos HH. Automatic configuration of multi-objective local search algorithms for permutation problems. Evolutionary Computation 2019; 27 (1): 147-171.
[40] Sanjeev Kumar R, Padmanaban KP, Rajkumar M. Minimizing makespan and total flow time in permutation flow shop scheduling problems using modified gravitational emulation local search algorithm. Proceedings of the Institution of Mechanical Engineers Part B: Journal of Engineering Manufacture 2018; 232 (3): 534-545.
[41] Almeida C, Gonçalves R, Venske S, Lüuders R, Delgado M. Multi-armed bandit based hyper-heuristics for the permutation flow shop problem. In: 7th Brazilian Conference on Intelligent Systems; São Paulo, Brazil; 2018. pp. 139-144.
[42] Dengiz B, Alabas-Uslu C, Dengiz O. Optimization of manufacturing systems using a neural network metamodel with a new training approach. Journal of operational Research Society 2009; 60 (9): 1191-1197.
[43] Zitzler E, Thiele L, Laumanns M, Fonseca CM, Da Fonseca VG. Performance assessment of multiobjective optimizers: an analysis and review. IEEE Transactions on evolutionary computation 2003; 7 (2): 117-132.