Resource constrained job scheduling with parallel constraint-based ACO

Dror Cohen, Antonio Gómez-Iglesias, Dhananjay Thiruvady, Andreas T. Ernst

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

Abstract

Hybrid methods are highly effective means of solving combinatorial optimization problems and have become increasingly popular. In particular, integrations of exact and incomplete methods have proved to be effective where the hybrid takes advantage of the relative performance of each individual method. However, these methods often require significant run-times to determine good feasible solutions. One way of reducing run-times is to parallelize these algorithms. For large NP-hard problems, parallelization must be done with care, since changes to the algorithm can affect its performance in unpredictable ways. In this paper we develop two parallel variants of constraint-based ACO and test them on a problem arising in the Australian mining industry. We demonstrate that parallelization significantly reduces run times with each parallel variant providing advantages with respect to feasibility and solution quality.

Original languageEnglish
Title of host publicationArtificial Life and Computational Intelligence
Subtitle of host publicationThird Australasian Conference, ACALCI 2017, Geelong, VIC, Australia, January 31 - Feburary 2, 2017, Proceedings
EditorsMarkus Wagner, Xiaodong Li, Tim Hendtlass
Place of PublicationCham, Switzerland
PublisherSpringer
Pages266-278
Number of pages13
ISBN (Electronic)9783319516912
ISBN (Print)9783319516905
DOIs
Publication statusPublished - 2017
EventAustralasian Conference on Artificial Life and Computational Intelligence (ACALCI) 2017 - Deakin University, Waterfront Campus, Geelong, Australia
Duration: 31 Jan 20172 Feb 2017
Conference number: 3rd
http://www.acalci.net/2017/
https://link.springer.com/book/10.1007/978-3-319-51691-2 (Springer Proceedings)

Publication series

NameLecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)
PublisherSpringer International Publishing
Volume10142
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

ConferenceAustralasian Conference on Artificial Life and Computational Intelligence (ACALCI) 2017
Abbreviated titleACALCI 2017
CountryAustralia
CityGeelong
Period31/01/172/02/17
OtherACACLI 2017 is co-located with the Australasian Computer Science Week (ACSW 2017), which will be held at Deakin University's Waterfront Campus, Geelong, which is about 70 kilometers west of Mebourne.

3rd Australasian Conference on Artificial Life and Computational Intelligence, ACALCI 2017
Internet address

Cite this

Cohen, D., Gómez-Iglesias, A., Thiruvady, D., & Ernst, A. T. (2017). Resource constrained job scheduling with parallel constraint-based ACO. In M. Wagner, X. Li, & T. Hendtlass (Eds.), Artificial Life and Computational Intelligence: Third Australasian Conference, ACALCI 2017, Geelong, VIC, Australia, January 31 - Feburary 2, 2017, Proceedings (pp. 266-278). (Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science); Vol. 10142). Cham, Switzerland: Springer. https://doi.org/10.1007/978-3-319-51691-2_23
Cohen, Dror ; Gómez-Iglesias, Antonio ; Thiruvady, Dhananjay ; Ernst, Andreas T. / Resource constrained job scheduling with parallel constraint-based ACO. Artificial Life and Computational Intelligence: Third Australasian Conference, ACALCI 2017, Geelong, VIC, Australia, January 31 - Feburary 2, 2017, Proceedings. editor / Markus Wagner ; Xiaodong Li ; Tim Hendtlass. Cham, Switzerland : Springer, 2017. pp. 266-278 (Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)).
@inproceedings{40256467b97442438bfd664707aa7155,
title = "Resource constrained job scheduling with parallel constraint-based ACO",
abstract = "Hybrid methods are highly effective means of solving combinatorial optimization problems and have become increasingly popular. In particular, integrations of exact and incomplete methods have proved to be effective where the hybrid takes advantage of the relative performance of each individual method. However, these methods often require significant run-times to determine good feasible solutions. One way of reducing run-times is to parallelize these algorithms. For large NP-hard problems, parallelization must be done with care, since changes to the algorithm can affect its performance in unpredictable ways. In this paper we develop two parallel variants of constraint-based ACO and test them on a problem arising in the Australian mining industry. We demonstrate that parallelization significantly reduces run times with each parallel variant providing advantages with respect to feasibility and solution quality.",
author = "Dror Cohen and Antonio G{\'o}mez-Iglesias and Dhananjay Thiruvady and Ernst, {Andreas T.}",
year = "2017",
doi = "10.1007/978-3-319-51691-2_23",
language = "English",
isbn = "9783319516905",
series = "Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)",
publisher = "Springer",
pages = "266--278",
editor = "Wagner, {Markus } and Xiaodong Li and Hendtlass, {Tim }",
booktitle = "Artificial Life and Computational Intelligence",

}

Cohen, D, Gómez-Iglesias, A, Thiruvady, D & Ernst, AT 2017, Resource constrained job scheduling with parallel constraint-based ACO. in M Wagner, X Li & T Hendtlass (eds), Artificial Life and Computational Intelligence: Third Australasian Conference, ACALCI 2017, Geelong, VIC, Australia, January 31 - Feburary 2, 2017, Proceedings. Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science), vol. 10142, Springer, Cham, Switzerland, pp. 266-278, Australasian Conference on Artificial Life and Computational Intelligence (ACALCI) 2017, Geelong, Australia, 31/01/17. https://doi.org/10.1007/978-3-319-51691-2_23

Resource constrained job scheduling with parallel constraint-based ACO. / Cohen, Dror; Gómez-Iglesias, Antonio; Thiruvady, Dhananjay; Ernst, Andreas T.

Artificial Life and Computational Intelligence: Third Australasian Conference, ACALCI 2017, Geelong, VIC, Australia, January 31 - Feburary 2, 2017, Proceedings. ed. / Markus Wagner; Xiaodong Li; Tim Hendtlass. Cham, Switzerland : Springer, 2017. p. 266-278 (Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science); Vol. 10142).

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

TY - GEN

T1 - Resource constrained job scheduling with parallel constraint-based ACO

AU - Cohen, Dror

AU - Gómez-Iglesias, Antonio

AU - Thiruvady, Dhananjay

AU - Ernst, Andreas T.

PY - 2017

Y1 - 2017

N2 - Hybrid methods are highly effective means of solving combinatorial optimization problems and have become increasingly popular. In particular, integrations of exact and incomplete methods have proved to be effective where the hybrid takes advantage of the relative performance of each individual method. However, these methods often require significant run-times to determine good feasible solutions. One way of reducing run-times is to parallelize these algorithms. For large NP-hard problems, parallelization must be done with care, since changes to the algorithm can affect its performance in unpredictable ways. In this paper we develop two parallel variants of constraint-based ACO and test them on a problem arising in the Australian mining industry. We demonstrate that parallelization significantly reduces run times with each parallel variant providing advantages with respect to feasibility and solution quality.

AB - Hybrid methods are highly effective means of solving combinatorial optimization problems and have become increasingly popular. In particular, integrations of exact and incomplete methods have proved to be effective where the hybrid takes advantage of the relative performance of each individual method. However, these methods often require significant run-times to determine good feasible solutions. One way of reducing run-times is to parallelize these algorithms. For large NP-hard problems, parallelization must be done with care, since changes to the algorithm can affect its performance in unpredictable ways. In this paper we develop two parallel variants of constraint-based ACO and test them on a problem arising in the Australian mining industry. We demonstrate that parallelization significantly reduces run times with each parallel variant providing advantages with respect to feasibility and solution quality.

UR - http://www.scopus.com/inward/record.url?scp=85011407714&partnerID=8YFLogxK

U2 - 10.1007/978-3-319-51691-2_23

DO - 10.1007/978-3-319-51691-2_23

M3 - Conference Paper

SN - 9783319516905

T3 - Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)

SP - 266

EP - 278

BT - Artificial Life and Computational Intelligence

A2 - Wagner, Markus

A2 - Li, Xiaodong

A2 - Hendtlass, Tim

PB - Springer

CY - Cham, Switzerland

ER -

Cohen D, Gómez-Iglesias A, Thiruvady D, Ernst AT. Resource constrained job scheduling with parallel constraint-based ACO. In Wagner M, Li X, Hendtlass T, editors, Artificial Life and Computational Intelligence: Third Australasian Conference, ACALCI 2017, Geelong, VIC, Australia, January 31 - Feburary 2, 2017, Proceedings. Cham, Switzerland: Springer. 2017. p. 266-278. (Lecture Notes in Artificial Intelligence (Subseries of Lecture Notes in Computer Science)). https://doi.org/10.1007/978-3-319-51691-2_23