A Branch-and-Cut Algorithm for the Multilevel Generalized Assignment Problem

Abstract

The multilevel generalized assignment problem (MGAP) consists of minimizing the assignment cost of a set of jobs to machines, each having associated therewith a capacity constraint. Each machine can perform a job with different efficiency levels that entail different costs and amount of resources required. The MGAP was introduced in the context of large manufacturing systems as a more general variant of the well-known generalized assignment problem, where a single efficiency level is associated with each machine. In this paper, we propose a branch-and-cut algorithm whose core is an exact separation procedure for the multiple-choice knapsack polytope induced by the capacity constraints and single-level execution constraints. A computational experience on a set of benchmark instances is reported, showing the effectiveness of the proposed approach.

Keywords

• Generalized assignement problem
• branch-and-cut
• exact separation