Structural advantages for ant colony optimisation inherent in permutation scheduling problems

James Montgomery, M Randall, T Hendtlass

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

4 Citations (Scopus)
54 Downloads (Pure)

Abstract

When using a constructive search algorithm, solutions to scheduling problems such as the job shop and open shop scheduling problems are typically represented as permutations of the operations to be scheduled. The combination of this representation and the use of a constructive algorithm introduces a bias typically favouring good solutions. When ant colony optimisation is applied to these problems, a number of alternative pheromone representations are available, each of which interacts with this underlying bias in different ways. This paper explores both the structural aspects of the problem that introduce this underlying bias and the ways two pheromone representations may either lead towards poorer or better solutions over time. Thus it is a synthesis of a number of recent studies in this area that deal with each of these aspects independently.

Original languageEnglish
Title of host publicationInnovations in Applied Artificial Intelligence
EditorsM Ali, F Esposito
PublisherSpringer
Pages218-228
Number of pages11
ISBN (Print)3-540-26551-1
DOIs
Publication statusPublished - 2005
Event18th International Industrial and Engineering Applications of Artificial Intelligence and Expert Systems - Bari, Italy
Duration: 22 Jun 200524 Jun 2005
Conference number: 18

Publication series

NameLECTURE NOTES IN ARTIFICIAL INTELLIGENCE
PublisherSPRINGER-VERLAG BERLIN
Volume3533
ISSN (Print)0302-9743

Conference

Conference18th International Industrial and Engineering Applications of Artificial Intelligence and Expert Systems
Abbreviated title IEA/AIE
CountryItaly
CityBari
Period22/06/0524/06/05

Cite this

Montgomery, J., Randall, M., & Hendtlass, T. (2005). Structural advantages for ant colony optimisation inherent in permutation scheduling problems. In M. Ali, & F. Esposito (Eds.), Innovations in Applied Artificial Intelligence (pp. 218-228). (LECTURE NOTES IN ARTIFICIAL INTELLIGENCE; Vol. 3533). Springer. https://doi.org/10.1007/11504894_31
Montgomery, James ; Randall, M ; Hendtlass, T. / Structural advantages for ant colony optimisation inherent in permutation scheduling problems. Innovations in Applied Artificial Intelligence. editor / M Ali ; F Esposito. Springer, 2005. pp. 218-228 (LECTURE NOTES IN ARTIFICIAL INTELLIGENCE).
@inproceedings{cb3fc5dbb9f744e584187fc65b501859,
title = "Structural advantages for ant colony optimisation inherent in permutation scheduling problems",
abstract = "When using a constructive search algorithm, solutions to scheduling problems such as the job shop and open shop scheduling problems are typically represented as permutations of the operations to be scheduled. The combination of this representation and the use of a constructive algorithm introduces a bias typically favouring good solutions. When ant colony optimisation is applied to these problems, a number of alternative pheromone representations are available, each of which interacts with this underlying bias in different ways. This paper explores both the structural aspects of the problem that introduce this underlying bias and the ways two pheromone representations may either lead towards poorer or better solutions over time. Thus it is a synthesis of a number of recent studies in this area that deal with each of these aspects independently.",
author = "James Montgomery and M Randall and T Hendtlass",
year = "2005",
doi = "10.1007/11504894_31",
language = "English",
isbn = "3-540-26551-1",
series = "LECTURE NOTES IN ARTIFICIAL INTELLIGENCE",
publisher = "Springer",
pages = "218--228",
editor = "M Ali and F Esposito",
booktitle = "Innovations in Applied Artificial Intelligence",
address = "Germany",

}

Montgomery, J, Randall, M & Hendtlass, T 2005, Structural advantages for ant colony optimisation inherent in permutation scheduling problems. in M Ali & F Esposito (eds), Innovations in Applied Artificial Intelligence. LECTURE NOTES IN ARTIFICIAL INTELLIGENCE, vol. 3533, Springer, pp. 218-228, 18th International Industrial and Engineering Applications of Artificial Intelligence and Expert Systems, Bari, Italy, 22/06/05. https://doi.org/10.1007/11504894_31

Structural advantages for ant colony optimisation inherent in permutation scheduling problems. / Montgomery, James; Randall, M; Hendtlass, T.

Innovations in Applied Artificial Intelligence. ed. / M Ali; F Esposito. Springer, 2005. p. 218-228 (LECTURE NOTES IN ARTIFICIAL INTELLIGENCE; Vol. 3533).

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

TY - GEN

T1 - Structural advantages for ant colony optimisation inherent in permutation scheduling problems

AU - Montgomery, James

AU - Randall, M

AU - Hendtlass, T

PY - 2005

Y1 - 2005

N2 - When using a constructive search algorithm, solutions to scheduling problems such as the job shop and open shop scheduling problems are typically represented as permutations of the operations to be scheduled. The combination of this representation and the use of a constructive algorithm introduces a bias typically favouring good solutions. When ant colony optimisation is applied to these problems, a number of alternative pheromone representations are available, each of which interacts with this underlying bias in different ways. This paper explores both the structural aspects of the problem that introduce this underlying bias and the ways two pheromone representations may either lead towards poorer or better solutions over time. Thus it is a synthesis of a number of recent studies in this area that deal with each of these aspects independently.

AB - When using a constructive search algorithm, solutions to scheduling problems such as the job shop and open shop scheduling problems are typically represented as permutations of the operations to be scheduled. The combination of this representation and the use of a constructive algorithm introduces a bias typically favouring good solutions. When ant colony optimisation is applied to these problems, a number of alternative pheromone representations are available, each of which interacts with this underlying bias in different ways. This paper explores both the structural aspects of the problem that introduce this underlying bias and the ways two pheromone representations may either lead towards poorer or better solutions over time. Thus it is a synthesis of a number of recent studies in this area that deal with each of these aspects independently.

U2 - 10.1007/11504894_31

DO - 10.1007/11504894_31

M3 - Conference contribution

SN - 3-540-26551-1

T3 - LECTURE NOTES IN ARTIFICIAL INTELLIGENCE

SP - 218

EP - 228

BT - Innovations in Applied Artificial Intelligence

A2 - Ali, M

A2 - Esposito, F

PB - Springer

ER -

Montgomery J, Randall M, Hendtlass T. Structural advantages for ant colony optimisation inherent in permutation scheduling problems. In Ali M, Esposito F, editors, Innovations in Applied Artificial Intelligence. Springer. 2005. p. 218-228. (LECTURE NOTES IN ARTIFICIAL INTELLIGENCE). https://doi.org/10.1007/11504894_31