A Review of Implementing Ant System Algorithms on Scheduling Problems

Kashef, Samar; ElShaer, Raafat

doi:10.21608/eijest.2021.63497.1049

A Review of Implementing Ant System Algorithms on Scheduling Problems

Document Type : Original Article

Authors

Samar Kashef ¹
Raafat ElShaer ²

¹ Industrial Engineering Department, Faculty Of Engineering, Zagazig University.

² Industrial Engineering Dept., Faculty of Engineering, Zagazig University, Zagazig, Sharkia, Egypt.

10.21608/eijest.2021.63497.1049

Abstract

The ant system (AS) and scheduling problem are well-known concepts in literature. Ant algorithms have been known to be an effective tool for solving combinatorial optimization problems. Elitist AS (EAS), rank-based AS (RAS), ant colony system (ACS), and max-min AS (MMAS) are the variants of the AS algorithm; they are triggered by the different ways of updating the pheromone trail τ, computing the visibility η, and/or other parameters in the basic AS model. The main contribution of this article is twofold. First, the basic AS and its controlled parameters are presented, the key variants of the ant algorithms are explained, and major changes of each variant from the basic model are tracked. Second, 60 papers are collected between 2015 and 2020 based on a search strategy for tracking the implementation of different AS variants in solving scheduling problems. Numerous findings based on a statistical analysis of the collected papers are reported and discussed. This study will allow the researcher to understand the essence of the ant algorithm, recognize the fundamental differences in its five systems, and determine how each of them can be implemented. Tracking a sample of articles that apply an ant algorithm for a specific case study gives researchers new ideas on how to adjust the original model to fit their problem.

Keywords