An Algorithm for the Generalized Assignment Problem with Special Ordered Sets

Journal of Heuristics, 11: 337350, 2005

c[circlecopyrt]2005 Springer Science + Business Media, Inc. Manufactured in The Netherlands.An Algorithm for the Generalized Assignment

Problem with Special Ordered SetsJOHN M. WILSONBusiness School, Loughborough University, Loughborough, LE113TU, England

email: [email protected] in October 2002 and accepted by Edmund Burke in May 2005 after 4 revisionsAbstractThe generalized assignment problem (GAP), the 01 integer programming (IP) problem of assigning a set of n

items to a set of m knapsacks, where each item must be assigned to exactly one knapsack and there are constraints

on the availability of resources for item assignment, has been further generalized recently to include cases where

items may be shared by a pair of adjacent knapsacks. This problem is termed the generalized assignment problem

with special ordered sets of type 2 (GAPS2). For reasonably large values of m and n the NP-hard combinatorial

problem GAPS2 becomes intractable for standard IP software, hence there is a need for the development of

heuristic algorithms to solve such problems. It will be shown how a heuristic algorithm developed previously for

the GAP problem can be modified and extended to solve GAPS2. Encouraging results, in terms of speed and

accuracy, have been achieved.Key Words: assignment, generalized assignment, heuristics, special ordered setsThe generalized assignment problem (GAP) is a familiar combinatorial problem. Using the

terminology of Martello and Toth (1990) it can be described as follows:Given n items and m knapsacks withpij =profit of item j if assigned to knapsack iwij =weight of item j if assigned to knapsack i

bi =capacity of knapsack i,GAP is the problem of assigning each item to exactly one knapsack to maximise the total

profit, without assigning to any knapsack a total weight of items greater than its capacity.

An integer programming (IP) formulation of GAP is the following.GAPmaximize z =mni=1j=1pij xij (1)subject tonwij xij bi , i M ={1, 2,..., m} (2)j=1338 WILSONm

i=11, j N ={1, 2,..., n} (3)where xij = 1 if item j is assigned to knapsack i0 otherwise. (4)Without loss of generality, pij ,wij , and bi are assumed to be non-negative integers. There is

no essential difference in GAP if (1) is a minimization objective function, for example in a

task allocation problem where the objective represents cost and...