TABU SEARCH FOR THE MULTILEVEL GENERALIZED ASSIGNMENT PROBLEM

The multilevel generalized assignment problem (MGAP) differs from the classical GAP in that agents can perform tasks at more than one effici ency level. Important manufacturing problems, such as lot sizing, can be formulated as MGAPs; however, the large number of variables in the related 0-1 integer program makes the use of commercial optimization p ackages impractical. In this paper, we present a heuristic approach to the solution of the MGAP, which consists of a novel application of ta bu search (TS). Our TS method employs neighborhoods defined by ejectio n chains, that produce moves of greater power without significantly in creasing the computational effort.