A Novel Ant Colony Algorithm for the Single-Machine Total Weighted Tardiness Problem with Sequence Dependent Setup Times
- 10.2991/ijcis.2011.4.4.5How to use a DOI?
- Scheduling; Ant colony optimization; Genetic operators; Total weighted tardiness; Sequence dependent setups.
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.
- © 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/).
Cite this article
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 -