COMPARISON OF ANT COLONY ALGORITHM WITH OTHER METAHEURISTICS IN BATCH SCHEDULING
Systematic methods and tools for managing the complexity
Advances in Computational & Numerical Methods (T4-4P)
Keywords: scheduling, metaheuristics, ant colony optimization
Scheduling plays a central role in short and medium-term activities of manufacturing and process industries. It is a complex problem defined by time and resource restrictions, so their solution consumes a large amount of human and computational resources.
Finding fast and effective solution strategies to solve scheduling problems is a challenging area. Available algorithms are classified into either exact or approximate. Exact algorithms guarantee finding the optimal solution even though required times grow exponentially with problem size. Approximate algorithms sacrifice optimal solutions for the sake of lower computation times.
This paper focuses on approximate methods, also called heuristics. These methods represent a solution for solving large scale problems in relatively short times. However, they usually generate only a very limited number of different solutions, as greedy construction heuristics, or they stop at poor quality local optima, as iterative improvement methods. In this background, appeared metaheuristics. A metaheuristic is general algorithmic framework which can be applied to different optimization problems with relatively few modifications to make them adapted to a specific problem [1].
Ant colony optimization has been extensively used in scheduling. In particular, Jayaraman2 presents an ant colony algorithm for a multipurpose batch scheduling problem. In this paper, a modification in the proposed algorithm is implemented in order to achieve better results.
An additional objective of this work is the comparison, in terms of efficiency and effectiveness, of several metaheuristic methods, namely ant colony optimization, simulated annealing, and evolutionary computation, in solving scheduling problems. Efficiency is measured by means of computation time, whereas effectiveness is the capacity of the metaheuristic of finding the optimal solution. The performance of the former metaheuristics is checked through different case studies, so that their strengths and limitations are characterized. Moreover, the proposed examples are modelled using mixed-integer linear programming in order to calculate an exact solution. Thus, it is possible to compare exact results with those obtained with metaheuristics, as well as their computation times.
Bibliography
1. Dorigo, M.; Stützle, T. Ant Colony Optimization; Cambridge(etc):MIT Press: United States of America, 2004; , pp 305.
2. Jayaraman, V. K.; Kulkarni, B. D.; Karale, S.; Shelokar, P. Comput. Chem. Eng. 2000, 8, 1901-1912.
Presented Tuesday 18, 13:30 to 15:00, in session Advances in Computational & Numerical Methods (T4-4P).
