×

zbMATH — the first resource for mathematics

Automatic algorithm design for hybrid flowshop scheduling problems. (English) Zbl 1431.90062
Summary: Industrial production scheduling problems are challenges that researchers have been trying to solve for decades. Many practical scheduling problems such as the hybrid flowshop are \(\mathcal{NP} \)-hard. As a result, researchers resort to metaheuristics to obtain effective and efficient solutions. The traditional design process of metaheuristics is mainly manual, often metaphor-based, biased by previous experience and prone to producing overly tailored methods that only work well on the tested problems and objectives. In this paper, we use an Automatic Algorithm Design (AAD) methodology to eliminate these limitations. AAD is capable of composing algorithms from components with minimal human intervention. We test the proposed AAD for three different optimization objectives in the hybrid flowshop. Comprehensive computational and statistical testing demonstrates that automatically designed algorithms outperform specifically tailored state-of-the-art methods for the tested objectives in most cases.

MSC:
90B35 Deterministic scheduling theory in operations research
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Experimental methods for the analysis of optimization algorithms, (Bartz-Beielstein, T.; Chiarandini, M.; Paquete, L.; Preuss, M. (2010), Springer: Springer Berlin, Heidelberg) · Zbl 1203.68003
[2] Bożejko, W.; Gnatowski, A.; Niżyński, T.; Affenzeller, M.; Beham, A., Local optima networks in solving algorithm selection problem for TSP, (Zamojski, W.; Mazurkiewicz, J.; Sugier, J.; Walkowiak, T.; Kacprzyk, J., Advances in intelligent systems and computing, 761 (2018), Springer), 83-93
[3] Bożejko, W.; Pempera, J.; Smutnicki, C., Parallel tabu search algorithm for the hybrid flow shop problem, Computers & Industrial Engineering, 65, 3, 466-474 (2013)
[4] Burke, E. K.; Hyde, M. R.; Kendall, G., Grammatical evolution of local search heuristics, IEEE Transactions on Evolutionary Computation, 16, 3, 406-417 (2012)
[5] Cahon, S.; Melab, N.; Talbi, E.-G., ParadisEO: A framework for the reusable design of parallel and distributed metaheuristics, Journal of Heuristics, 10, 3, 357-380 (2004)
[6] Carlier, J.; Néron, E., An exact method for solving the multi-processor flow-shop, RAIRO - Operations Research, 34, 1, 1-25 (2000) · Zbl 0963.90027
[7] Chung, T.-P.; Liao, C.-J., An immunoglobulin-based artificial immune system for solving the hybrid flow shop problem, Applied Soft Computing, 13, 8, 3729-3736 (2013)
[8] Cui, Z.; Gu, X., An improved discrete artificial bee colony algorithm to minimize the makespan on hybrid flow shop problems, Neurocomputing, 148, 248-259 (2015)
[9] Ding, J.-Y.; Song, S.; Gupta, J. N.D.; Zhang, R.; Chiong, R.; Wu, C., An improved iterated greedy algorithm with a tabu-based reconstruction strategy for the no-wait flowshop scheduling problem, Applied Soft Computing, 30, 604-613 (2015)
[10] 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, 38, 8, 1219-1236 (2011) · Zbl 1208.90059
[11] Dubois-Lacoste, J.; Pagnozzi, F.; Stützle, T., An iterated greedy algorithm with optimization of partial solutions for the permutation flowshop problem, Computers & Operations Research, 81, 160-166 (2017) · Zbl 1391.90257
[12] Framiñan, J. M.; Leisten, R.; Ruiz, R., Manufacturing scheduling systems: An integrated view on models, methods and tools (2014), Springer Science & Business Media · Zbl 1354.90005
[13] Franzin, A.; Stützle, T., Exploration of metaheuristics through automatic algorithm configuration techniques and algorithmic frameworks, Proceedings of the 2016 on genetic and evolutionary computation conference, GECCO ’16 companion, 1341-1347 (2016), ACM: ACM New York, NY, USA
[14] Gupta, J. N.D., Two-stage, hybrid flowshop scheduling problem, Journal of the Operational Research Society, 39, 4, 359-364 (1988) · Zbl 0639.90049
[15] Gupta, J. N.D.; Stafford, E. F., Flowshop scheduling research after five decades, European Journal of Operational Research, 169, 3, 699-711 (2006) · Zbl 1079.90001
[16] Hidri, L.; Haouari, M., Bounding strategies for the hybrid flow shop scheduling problem, Applied Mathematics and Computation, 217, 21, 8248-8263 (2011) · Zbl 1231.90197
[17] Hoos, H. H.; Stützle, T., Stochastic local search: Foundations and applications (2004), Elsevier · Zbl 1126.68032
[18] Rome, Italy.
[19] Hutter, F.; Stützle, T.; Leyton-Brown, K.; Hoos, H. H., ParamILS: An automatic algorithm configuration framework, Journal of Artificial Intelligence Research, 36, 267-306 (2009) · Zbl 1192.68831
[20] Johnson, S. M., Optimal two- and three-stage production schedules with setup times included, Naval Research Logistics Quarterly, 1, 1, 61-68 (1954) · Zbl 1349.90359
[21] Khalouli, S.; Ghedjati, F.; Hamzaoui, A., A meta-heuristic approach to solve a JIT scheduling problem in hybrid flow shop, Engineering Applications of Artificial Intelligence, 23, 5, 765-771 (2010)
[22] KhudaBukhsh, A. R.; Xu, L.; Hoos, H. H.; Leyton-Brown, K., SATenstein: Automatically building local search SAT solvers from components, Artificial Intelligence, 232, 20-42 (2016) · Zbl 1351.68255
[23] Li, J.-Q.; Pan, Q.-K.; Wang, F.-T., A hybrid variable neighborhood search for solving the hybrid flow shop scheduling problem, Applied Soft Computing, 24, 63-77 (2014)
[24] Liao, C.-J.; Tjandradjaja, E.; Chung, T.-P., An approach using particle swarm optimization and bottleneck heuristic to solve hybrid flow shop scheduling problem, Applied Soft Computing, 12, 6, 1755-1764 (2012)
[25] López-Ibáñez, M.; Stützle, T., The automatic design of multiobjective ant colony optimization algorithms, IEEE Transactions on Evolutionary Computation, 16, 6, 861-875 (2012)
[26] López-Ibáñez, M.; Dubois-Lacoste, J.; Pérez Cáceres, L.; Birattari, M.; Stützle, T., The irace package: Iterated racing for automatic algorithm configuration, Operations Research Perspectives, 3, 43-58 (2016)
[27] TR/IRIDIA/2017-012.
[28] chapter 9.
[29] Marichelvam, M.; Prabaharan, T.; Yang, X.-S., A discrete firefly algorithm for the multi-objective hybrid flowshop scheduling problems, IEEE Transactions on Evolutionary Computation, 18, 2, 301-305 (2014)
[30] Marichelvam, M.; Prabaharan, T.; Yang, X.-S., Improved cuckoo search algorithm for hybrid flow shop scheduling problems to minimize makespan, Applied Soft Computing, 19, 93-101 (2014)
[31] Marichelvam, M.; Prabaharan, T.; Yang, X.-S.; Geetha, M., Solving hybrid flow shop scheduling problems using bat algorithm, International Journal of Logistics Economics and Globalisation, 5, 1, 15-29 (2013)
[32] Ischia, Italy.
[33] Mascia, F.; López-Ibáñez, M.; Dubois-Lacoste, J.; Stützle, T., Grammar-based generation of stochastic local search heuristics through automatic algorithm configuration tools, Computers & Operations Research, 51, 190-199 (2014) · Zbl 1348.68230
[34] Montgomery, D. C., Design and analysis of experiments (2012), John Wiley & Sons
[35] Nawaz, M.; Enscore, E.; Ham, I., A heuristic algorithm for the m-machine, n-job flow-shop sequencing problem, OMEGA: The International Journal of Management Science, 11, 1, 91-95 (1983)
[36] Pan, Q.-K.; Dong, Y., An improved migrating birds optimisation for a hybrid flowshop scheduling with total flowtime minimisation, Information Sciences, 277, 643-655 (2014) · Zbl 1354.90052
[37] Pan, Q.-K.; Ruiz, R.; Alfaro-Fernández, P., Iterated search methods for earliness and tardiness minimization in hybrid flowshops with due windows, Computers & Operations Research, 80, 50-60 (2017) · Zbl 1391.90301
[38] Pan, Q.-K.; Wang, L.; Li, J.-Q.; Duan, J.-H., A novel discrete artificial bee colony algorithm for the hybrid flowshop scheduling problem with makespan minimisation, OMEGA: The International Journal of Management Science, 45, 42-56 (2014)
[39] Rajendran, C.; Ziegler, H., An efficient heuristic for scheduling in a flowshop to minimize total weighted flowtime of jobs, European Journal of Operational Research, 103, 1, 129-138 (1997) · Zbl 0922.90089
[40] Ruiz, R.; Stützle, T., A simple and effective iterated greedy algorithm for the permutation flowshop scheduling problem, European Journal of Operational Research, 177, 3, 2033-2049 (2007) · Zbl 1110.90042
[41] Ruiz, R.; Vázquez-Rodríguez, J. A., The hybrid flow shop scheduling problem, European Journal of Operational Research, 205, 1, 1-18 (2010) · Zbl 1188.90110
[42] Sörensen, K., Metaheuristics - The metaphor exposed, International Transactions in Operational Research, 22, 1, 3-18 (2015) · Zbl 1309.90127
[43] Stützle, T.; López-Ibáñez, M., Automated design of metaheuristic algorithms, (Gendreau, M.; Potvin, J.-Y., Handbook of metaheuristics (2019), Springer: Springer Cham), 541-579
[44] Talbi, E.-G., Metaheuristics: from design to implementation, 74 (2009), John Wiley & Sons · Zbl 1190.90293
[45] Vignier, A.; Billaut, J. C.; Proust, C., Les problemes d’ordonnancement de type flow-shop hybride: Etat de l’art, RAIRO Recherche Operationnelle, 33, 2, 117 (1999) · Zbl 0960.90042
[46] Wang, S.; Wang, L.; Liu, M.; Xu, Y., An enhanced estimation of distribution algorithm for solving hybrid flow-shop scheduling problem with identical parallel machines, The International Journal of Advanced Manufacturing Technology, 68, 9, 2043-2056 (2013)
[47] Wasik, S.; Antczak, M.; Badura, J.; Laskowski, A.; Sternal, T., Optil.io: Cloud based platform for solving optimization problems using crowdsourcing approach, Proceedings of the 19th ACM conference on computer supported cooperative work and social computing companion, CSCW ’16 companion, 433-436 (2016), ACM: ACM New York, NY, USA
[48] Xu, Y.; Wang, L.; Wang, S.; Liu, M., An effective shuffled frog-leaping algorithm for solving the hybrid flow-shop scheduling problem with identical parallel machines, Engineering Optimization, 45, 12, 1409-1430 (2013)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.