A Novel Ant Colony Algorithm for the Single-Machine Total Weighted Tardiness Problem with Sequence Dependent Setup Times

DOI

10.2991/ijcis.2011.4.4.5How to use a DOI?

Keywords

Scheduling; Ant colony optimization; Genetic operators; Total weighted tardiness; Sequence dependent setups.

Abstract

This paper deals with the NP-hard single-machine total weighted tardiness problem with sequence dependent setup times. Incorporating fuzzy sets and genetic operators, a novel ant colony optimization algorithm is developed for the problem. In the proposed algorithm, artificial ants construct solutions as orders of jobs based on the heuristic information as well as pheromone trails. To calculate the heuristic information, three well-known priority rules are adopted as fuzzy sets and then aggregated. When all artificial ants have terminated their constructions, genetic operators such as crossover and mutation are applied to generate new regions of the solution space. A local search is then performed to improve the performance quality of some of the solutions found. Moreover, at run-time the pheromone trails are locally as well as globally updated, and limited between lower and upper bounds. The proposed algorithm is experimented on a set of benchmark problems from the literature and compared with other metaheuristics.

Copyright

© 2011, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - JOUR
AU  - Fardin Ahmadizar
AU  - Leila Hosseini
PY  - 2011
DA  - 2011/06/01
TI  - A Novel Ant Colony Algorithm for the Single-Machine Total Weighted Tardiness Problem with Sequence Dependent Setup Times
JO  - International Journal of Computational Intelligence Systems
SP  - 456
EP  - 466
VL  - 4
IS  - 4
SN  - 1875-6883
UR  - https://doi.org/10.2991/ijcis.2011.4.4.5
DO  - 10.2991/ijcis.2011.4.4.5
ID  - Ahmadizar2011
ER  -