Divide and conquer: Using single objective dispatching rules to improve convergence for multi-objective optimisation
Pages 1082 - 1090
Abstract
Dynamic multi-objective (MO) scheduling problems are encountered in various real-world situations. Due to dynamic events that occur in such problems, one has to resort to using simple constructive heuristics, called dispatching rules (DRs), when tackling them. Since DRs are difficult to design manually there is a lack of existing DRs suitable for solving MO problems. Due to that reason, genetic programming has successfully been applied to evolve DRs specifically for solving MO problems. The process of evolving new DRs is computationally expensive, requiring a significant amount of time to obtain DRs of good quality. For that reason it is worth investigating inwhich ways the convergence of algorithms could be improved. One option is to use DRs previously evolved for optimising individual criteria to initialise the starting population when optimising a MO problem. The goal of this study is to investigate how such an initialisation strategy affects the performance of NSGA-II and NSGA-III when evolving DRs for MO problems. Therefore, 8 MO unrelated machines scheduling problems, containing between 2 and 5 criteria, are considered. The obtained results demonstrate that using previously evolved DRs for single objective optimisation leads to a faster convergence, and in many cases significantly better results.
References
[1]
Jürgen Branke, Su Nguyen, Christoph W. Pickardt, and Mengjie Zhang. 2016. Automated Design of Production Scheduling Heuristics: A Review. IEEE Transactions on Evolutionary Computation 20, 1 (2016), 110--124.
[2]
Kalyanmoy Deb and Himanshu Jain. 2014. An Evolutionary Many-Objective Optimization Algorithm Using Reference-Point-Based Nondominated Sorting Approach, Part I: Solving Problems With Box Constraints. IEEE Transactions on Evolutionary Computation 18, 4 (2014), 577--601.
[3]
K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. 2002. A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation 6, 2 (2002), 182--197.
[4]
Ridvan Gedik, Darshan Kalathia, Gokhan Egilmez, and Emre Kirac. 2018. A constraint programming approach for solving unrelated parallel machine scheduling problem. Computers & Industrial Engineering 121 (2018), 139--149. https://doi.org/j.cie.2018.05.014
[5]
Francisco J. Gil-Gala, Carlos Mencía, María R. Sierra, and Ramiro Varela. 2019. Evolving priority rules for on-line scheduling of jobs on a single machine with variable capacity over time. Applied Soft Computing 85 (2019), 105782.
[6]
Francisco J. Gil-Gala, Carlos Mencía, María R. Sierra, and Ramiro Varela. 2020. Learning ensembles of priority rules for online scheduling by hybrid evolutionary algorithms. Integrated Computer-Aided Engineering 28, 1 (Dec. 2020), 65--80.
[7]
Atiya Masood, Gang Chen, Yi Mei, Harith Al-Sahaf, and Mengjie Zhang. 2019. Genetic Programming with Pareto Local Search for Many-Objective Job Shop Scheduling. In AI 2019: Advances in Artificial Intelligence. Springer International Publishing, 536--548.
[8]
Atiya Masood, Gang Chen, Yi Mei, Harith Al-Sahaf, and Mengjie Zhang. 2020. A Fitness-based Selection Method for Pareto Local Search for Many-Objective Job Shop Scheduling. In 2020 IEEE Congress on Evolutionary Computation (CEC). 1--8.
[9]
Atiya Masood, Yi Mei, Gang Chen, and Mengjie Zhang. 2016. Many-objective genetic programming for job-shop scheduling. In 2016 IEEE Congress on Evolutionary Computation (CEC). 209--216.
[10]
Su Nguyen, Yi Mei, and Mengjie Zhang. 2017. Genetic programming for production scheduling: a survey with a unified framework. Complex & Intelligent Systems 3, 1 (Feb. 2017), 41--66.
[11]
Su Nguyen, Mengjie Zhang, Mark Johnston, and Kay Chen Tan. 2013. Dynamic Multi-objective Job Shop Scheduling: A Genetic Programming Approach. In Studies in Computational Intelligence. Springer Berlin Heidelberg, 251--282.
[12]
Michael L. Pinedo. 2012. Scheduling. Springer US.
[13]
Riccardo Poli, William B. Langdon, and Nicholas Freitag McPhee. 2008. A Field Guide to Genetic Programming. Lulu Enterprises, UK Ltd.
[14]
Marko Ðurasević and Domagoj Jakobović. 2017. Comparison of ensemble learning methods for creating ensembles of dispatching rules for the unrelated machines environment. Genetic Programming and Evolvable Machines 19, 1--2 (April 2017), 53--92.
[15]
Marko Ðurasević and Domagoj Jakobović. 2017. Evolving dispatching rules for optimising many-objective criteria in the unrelated machines environment. Genetic Programming and Evolvable Machines 19, 1--2 (Sept. 2017), 9--51.
[16]
Marko Ðurasević and Domagoj Jakobović. 2018. A survey of dispatching rules for the dynamic unrelated machines environment. Expert Systems with Applications 113 (2018), 555--569. https://doi.org/j.eswa.2018.06.053
[17]
Marko Ðurasević and Domagoj Jakobović. 2022. Heuristic and metaheuristic methods for the parallel unrelated machines scheduling problem: a survey. Artificial Intelligence Review (Aug. 2022).
[18]
Marko Ðurasević, Domagoj Jakobović, and Karlo Knežević. 2016. Adaptive scheduling on unrelated machines with genetic programming. Applied Soft Computing 48 (2016), 419--430. https://doi.org/j.asoc.2016.07.025
[19]
Marko Ðurasević, Lucija Planinić, Francisco J. Gil-Gala, and Domagoj Jakobović. 2022. Constructing Ensembles of Dispatching Rules for Multi-objective Problems. In Bio-inspired Systems and Applications: from Robotics to Ambient Intelligence, José Manuel Ferrández Vicente, José Ramón Álvarez-Sánchez, Félix de la Paz López, and Hojjat Adeli (Eds.). Springer International Publishing, Cham, 119--129.
[20]
Lingxiao Wu and Shuaian Wang. 2018. Exact and heuristic methods to solve the parallel machine scheduling problem with multi-processor tasks. International Journal of Production Economics 201 (2018), 26--40. https://doi.org/j.ijpe.2018.04.013
[21]
Lian Yu, Heloisa M. Shih, Michele Pfund, W. Matthew Carlyle, and John W. Fowler. 2002. IIE Transactions 34, 11 (2002), 921--931.
[22]
Fangfang Zhang, Yi Mei, and Mengjie Zhang. 2019. Evolving Dispatching Rules for Multi-objective Dynamic Flexible Job Shop Scheduling via Genetic Programming Hyper-heuristics. In 2019 IEEE Congress on Evolutionary Computation (CEC). 1366--1373.
[23]
Fangfang Zhang, Su Nguyen, Yi Mei, and Mengjie Zhang. 2021. Learning Scheduling Heuristics for Multi-objective Dynamic Flexible Job Shop Scheduling. In Genetic Programming for Production Scheduling. Springer Singapore, 235--245.
[24]
E Zitzler and L Thiele. 1999. Multiobjective evolutionary algorithms: a comparative case study and the strength Pareto approach. IEEE T Evolut Comput 3, 4 (1999), 257--271.
Index Terms
- Divide and conquer: Using single objective dispatching rules to improve convergence for multi-objective optimisation
Recommendations
Evolving dispatching rules for optimising many-objective criteria in the unrelated machines environment
Dispatching rules are often a method of choice for solving various scheduling problems. Most often, they are designed by human experts in order to optimise a certain criterion. However, it is seldom the case that a schedule should optimise a single ...
Constructing ensembles of dispatching rules for multi-objective tasks in the unrelated machines environment
Scheduling is a frequently studied combinatorial optimisation problem that often needs to be solved under dynamic conditions and to optimise multiple criteria. The most commonly used method for solving dynamic problems are dispatching rules (DRs), simple ...
Constructing Ensembles of Dispatching Rules for Multi-objective Problems
Bio-inspired Systems and Applications: from Robotics to Ambient IntelligenceAbstractScheduling represents an important aspect of many real-world processes, which is why such problems have been well studied in the literature. Such problems are often dynamic and require that multiple criteria be optimised simultaneously. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
July 2023
1667 pages
Copyright © 2023 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 12 July 2023
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Croatian Science Foundation
- Spanish State Agency for Research
Conference
GECCO '23
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,669 of 4,410 submissions, 38%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 44Total Downloads
- Downloads (Last 12 months)11
- Downloads (Last 6 weeks)0
Reflects downloads up to 18 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in