Hybrid metaheuristic for generalised assignment. (19th February 2020)

• Record Type: Journal Article
• Authors: Haddadi, Salim
• Is Part Of: International journal of innovative computing and applications. Volume 11:Number 1(2020)
• Page Start: 46
• Page End: 60
• Publication Date: 2020-02-19
• Subjects: generalised assignment problem -- hybrid metaheuristic -- very large scale neighbourhood -- iterated local search -- guided search -- variable-fixing; Evolutionary computation -- Periodicals; Neural networks (Computer science) -- Periodicals; Genetic programming (Computer science) -- Periodicals; Biologically-inspired computing -- Periodicals; Swarm intelligence -- Periodicals; Quantum computers -- Periodicals; 006.3
• Languages: English
• ISSNs: 1751-648X

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.