Hyper-heuristic approaches for the dynamic generalized assignment problem

Abstract

The generalized assignment problem is a well-known NP-complete problem whose objective is to find a minimum cost assignment of a set of jobs to a set of agents by considering the resource constraints. Dynamic instances of the generalized assignment problem can be created by changing the resource consumptions, capacity constraints and costs of jobs. Memory-based approaches are among a set of evolutionary techniques that are proposed for dynamic optimization problems. On the other hand, a hyper-heuristic is a high-level method which decides an appropriate low-level heuristic to apply on a given problem without using problem-specific information. In this paper, we present the applicability of hyper-heuristic methods for the dynamic generalized assignment problem. Our technique extends a memory-based approach by integrating it with various hyper-heuristics for the search population. Experimental evaluation performed on various benchmark instances indicates that our hyper-heuristic based approaches outperform the memory-based technique with respect to quality of solutions. © 2010 IEEE.