Strathprints logo
Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

Ants can solve difficult bin packing problems

Levine, J. and Ducatelle, F. (2003) Ants can solve difficult bin packing problems. In: Proceedings of the 1st Multidisciplinary International Conference on Scheduling. UNSPECIFIED.

Full text not available in this repository. (Request a copy from the Strathclyde author)

Abstract

The bin packing problem (BPP) is a well-known NP-hard combinatorial optimization problem which occurs in many contexts, including capital budgeting, scheduling and VLSI design. In this work, an ant colony optimization approach is presented for the BPP which is an adaptation of the Max-Min Ant System of Stuetzle and Hoos (2000). When ant colony algorithm is combined with a simple but effective iterated local search procedure, this was found to be competitive with the best known solution methods for certain classes of benchmark instances. We present results from a variety of benchmark instances due to Falkenauer (1996), Scholl, Klein and Juergens (1997), Schwerin and Waescher (1998), Waescher and Gau (1996) and a collection of large instances of our own devising. It was found that the ant colony approach was competitive for a significant number of these benchmark sets, and managed to find new optima for five instances in theWaescher and Gau (1996) set beyond those reported by Alvim, Glover, Ribeiro and Aliose (2002). We will also comment on the weaknesses of the current algorithm and will attempt to show, through experiments, how the hybrid ACO algorithm navigates the solution space to find good solutions.

Item type: Book Section
ID code: 32306
Keywords: ant colony optimization, bin packing, bin packing problems, scheduling, Electronic computers. Computer science
Subjects: Science > Mathematics > Electronic computers. Computer science
Department: Faculty of Science > Computer and Information Sciences
Related URLs:
Depositing user: Pure Administrator
Date Deposited: 26 Jul 2011 10:15
Last modified: 06 Sep 2014 06:50
URI: http://strathprints.strath.ac.uk/id/eprint/32306

Actions (login required)

View Item