Title: Hybrid metaheuristic for generalised assignment

Authors: Salim Haddadi

Addresses: LabSTIC, 8 Mai 1945 University, P.O. Box 401, 24000 Guelma, Algeria

Abstract: This paper investigates the classical generalised assignment problem (GAP), a challenging combinatorial optimisation problem that arises in numerous applications and that has attracted a great deal of research. For solving it we propose a hybrid metaheuristic combining guided search (GS), iterated local search (ILS), and very large-scale neighbourhood search (VLSN). The hybrid method is iterative. It starts with a random assignment, and in every iteration it acts in the following way: 1) The best current assignment is perturbed. 2) An exponential size neighbourhood of the perturbed assignment is constructed. It is the feasible solution set of a special GAP where only two fixed machines can execute a job. The neighbourhood construction is guided by a technique penalising poor machine/job selections. 3) The exponential neighbourhood is searched for improvement. Exploring the neighbourhood amounts to solving a monotone binary program (BP) – a monotone BP is one with two non-zero coefficients of opposite sign per column. We prove that the proposed metaheuristic runs in polynomial-time when applied to a variation of GAP. Good computational results in terms of solution quality, as well as of computation speed, are obtained with two new best values on hard instances.

Keywords: generalised assignment problem; hybrid metaheuristic; very large scale neighbourhood; iterated local search; guided search; variable-fixing.

DOI: 10.1504/IJICA.2020.105317

International Journal of Innovative Computing and Applications, 2020 Vol.11 No.1, pp.46 - 60

Received: 24 Jun 2019
Accepted: 10 Jul 2019
Published online: 24 Feb 2020 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article