Openly accessible

Solution merging in Matheuristics for resource constrained job scheduling

Thiruvady, Dhananjay, Blum, Christian and Ernst, Andreas T. 2020, Solution merging in Matheuristics for resource constrained job scheduling, Algorithms, vol. 13, no. 10, doi: 10.3390/a13100256.

Attached Files
Name Description MIMEType Size Downloads

Title Solution merging in Matheuristics for resource constrained job scheduling
Author(s) Thiruvady, DhananjayORCID iD for Thiruvady, Dhananjay orcid.org/0000-0002-8011-933X
Blum, Christian
Ernst, Andreas T.
Journal name Algorithms
Volume number 13
Issue number 10
Article ID 256
Total pages 31
Publisher M D P I AG
Place of publication Basel, Switzerland
Publication date 2020-10
ISSN 1999-4893
Keyword(s) merge search
construct
solve
merge and adapt
mixer integer programming
ant colony optimisation
rsource constrained job scheduling
Summary Matheuristics have been gaining in popularity for solving combinatorial optimisation problems in recent years. This new class of hybrid method combines elements of both mathematical programming for intensification and metaheuristic searches for diversification. A recent approach in this direction has been to build a neighbourhood for integer programs by merging information from several heuristic solutions, namely construct, solve, merge and adapt (CMSA). In this study, we investigate this method alongside a closely related novel approach—merge search (MS). Both methods rely on a population of solutions, and for the purposes of this study, we examine two options: (a) a constructive heuristic and (b) ant colony optimisation (ACO); that is, a method based on learning. These methods are also implemented in a parallel framework using multi-core shared memory, which leads to improving the overall efficiency. Using a resource constrained job scheduling problem as a test case, different aspects of the algorithms are investigated. We find that both methods, using ACO, are competitive with current state-of-the-art methods, outperforming them for a range of problems. Regarding MS and CMSA, the former seems more effective on medium-sized problems, whereas the latter performs better on large problems.
Language eng
DOI 10.3390/a13100256
Indigenous content off
Field of Research 01 Mathematical Sciences
08 Information and Computing Sciences
09 Engineering
HERDC Research category C1 Refereed article in a scholarly journal
Copyright notice ©2020, The Authors
Free to Read? Yes
Persistent URL http://hdl.handle.net/10536/DRO/DU:30143884

Connect to link resolver
 
Unless expressly stated otherwise, the copyright for items in DRO is owned by the author, with all rights reserved.

Every reasonable effort has been made to ensure that permission has been obtained for items included in DRO. If you believe that your rights have been infringed by this repository, please contact drosupport@deakin.edu.au.

Versions
Version Filter Type
Citation counts: TR Web of Science Citation Count  Cited 0 times in TR Web of Science
Scopus Citation Count Cited 0 times in Scopus
Google Scholar Search Google Scholar
Access Statistics: 11 Abstract Views, 0 File Downloads  -  Detailed Statistics
Created: Sat, 10 Oct 2020, 15:20:09 EST

Every reasonable effort has been made to ensure that permission has been obtained for items included in DRO. If you believe that your rights have been infringed by this repository, please contact drosupport@deakin.edu.au.