 |
    |
An Artificial Bee Colony Algorithm for the Unrelated Parallel Machines Scheduling Problem
Francisco J. Rodriguez1, Carlos García-Martínez3, Christian Blum2, and Manuel Lozano1
1Department of Computer Science and Artificial Intelligence, University of Granada, Granada, Spain
fjrodriguez@decsai.ugr.es
lozano@decsai.ugr.es
2ALBCOM Research Group, Technical University of Catalonia, Barcelona, Spain
cblum@lsi.upc.edu
3Department of Computing and Numerical Analysis, University of Córdoba, Córdoba, Spain
cgarcia@uco.es
Abstract. In this work, we tackle the problem of scheduling a set of jobs on a set of non-identical parallel machines with the goal of minimising the total weighted completion times. Artificial bee colony (ABC) algorithm is a new optimization technique inspired by the intelligent foraging behaviour of honey-bee swarm. These algorithms have shown a better or similar performance to those of other population-based algorithms, with the advantage of employing fewer control parameters. This paper proposes an ABC algorithm that combines the basic scheme with two significant elements: (1) a local search method to enhance the exploitation capability of basic ABC and (2) a neighbourhood operator based on iterated greedy constructive-destructive procedure. The benefits of the proposal in comparison to three different metaheuristic proposed in the literature are experimentally shown.
Keywords: discrete optimisation, metaheuristics, artificial bee colony, unrelated parallel machines schedulling problem
LNCS 7492, p. 143 ff.
lncs@springer.com
© Springer-Verlag Berlin Heidelberg 2012