Organizer:

Marco Dorigo

Chercheur Qualifie' du FNRS

IRIDIA CP 194/6

Universite' Libre de Bruxelles

Avenue Franklin Roosevelt 50

1050 Bruxelles

Belgium

Phone: +32-2-6503169; Fax: +32-2-6502715

1. An Ant Colony Optimization Approach for the Single Machine Total

Tardiness Problem

Bauer A., Bullnheimer B., Hartl R.F., Strauss C.

Machine Scheduling is a central task in production planning. In general it consists of the problem of scheduling job operations on a given number of available machines. In this paper we consider a machine scheduling problem with one machine, the Single Machine Total Tardiness Problem. As this problem is NP-hard, we apply the ant colony optimization metaphor, a recently developed meta-heuristic that has proven its potential for various other combinatorial optimization problems, and present computational results.

Keywords

Ant Colony Optimization, Machine Scheduling, Meta-Heuristics, Single Machine Total Tardiness Machine Scheduling using ACO

2. A Cooperative Ant Algorithm for Dynamic Routing and Load Balancing

P. Kuntz and Dominique Snyers

pluntz@ireste.fr

snyers@ieee.org

This paper presents new experimental results on a recently developed heuristic inspired by dead body clustering and larval sorting behavior of ants. The heuristic highlights organization of connected graphs by displaying spatially separate clusters of highly connected vertex subsets on a two-dimensional grid. After discussing some theoretical properties of graph vizualisation in small dimensional metric spaces, we compare our heuristic with more classical approaches based on spectral decompositions.

3. A New Version of Ant System for Subset Problems

Guillermo Leguizamon

Interest Group on Computer Systems

Universidad Nacional de San Luis

Argentina

legui@unsl.edu.ar

Zbigniew Michalewicz

Department of Computer Science

University of North Carolina at Charlotte

USA

zbyszek@uncc.edu

Ant Colony Optimization (ACO) is a relatively new meta-heuristic for hard combinatorial optimization problems. This meta-heuristic belongs to the class of heuristics derived from nature, which includes Evolutionary Algorithms, Neural Networks, Simulated Annealing, Tabu Search. An ACO algorithm is based on the result of low-level interaction among many cooperating simple agents that are not explicitly aware of their cooperative behavior. Each simple agent is called ant and the ACO algorithm (a distributed algorithm) is based on a set of ants working independently and cooperating sporadically in a common problem solving activity. Since the design of Ant System, the first example of ACO algorithm, plenty of work has been done in this area with applications to problems such as the Traveling Salesman Problem, the Bin Packing Problem, and the Quadratic Assignment Problem. In this paper we present the original Ant System as well as a new version applied to three subset problems: the Multiple Knapsack Problem (MKP), the Set Covering Problem (SCP), and the Maximum Independent Set Problem (MISP). The results show the potential power of the ACO approach for solving subset problems.

4. Hamiltonian(t) – An Ant-Inspired Heuristic for Recognizing Hamiltonian Graphs

Israel A. Wagner (1,2)

Alfred M. Bruckstein (2)

(1) IBM Haifa Research Lab, Matam, Haifa 31905, Israel

(2) Department of Computer Science, Technion City, Haifa 32000, Israel

israelw@vnet.ibm.com, freddy@cs.technion.ac.il

Given a graph G(V,E), we consider the problem of deciding whether G is Hamiltonian, i.e., whether or not there is a simple cycle in E spanning all vertices in V. This problem is known to be NP-complete, hence cannot be solved in time polynomial in |V| unless P=NP. The problem is a special case of the Travelling Salesperson Problem (TSP), that was extensively studied in the literature, and has recently been attacked by various ant-colony methods. We address the Hamiltonian cycle problem using a new ant-inspired approach, based on repeated covering of the graph. Our method is based on a process in which an ant traverses the graph by moving from vertex to vertex along the edges, occasionally leaving traces in the vertices, and deciding on the next step according to the level of traces in the surrounding neighborhood. We show that Hamiltonian cycles are limit cycles of the process, and investigate the average time needed by our ant process to recognize a Hamiltonian graph, on the basis of simulations made over large samples of random graphs with varying structure and density.