ABSTRACT
The allocation of limited resources to various activities required in production and distribution of a good or service forms the basis of a majority of dicult operations planning problems. The knapsack problem, discussed in Chapter 2, considers the allocation of a single resource to multiple activities that essentially compete for the resource. In the knapsack problem class, we are free to omit items from the knapsack. In operations planning contexts where the knapsack capacity represents machine capacity and the items represent jobs, for example, this corresponds to leaving jobs unperformed. Many operations planning problems require that all members of a candidate set of jobs are assigned to some available resource, ensuring that all job processing requirements are met. In this chapter, we consider such a class of problems, where each member of a set of items must be assigned to some member of a set of available resources, and where each available resource has an associated capacity limit. The goal of this problem is to assign each item to a resource at minimum total cost while respecting resource capacities, where a cost is associated with the assignment of a given item to a specic resource. Unlike the knapsack problem, this generalized assignment problem (GAP) falls into the class of problems that are NP-Hard in the strong sense, which implies that we are not likely to nd even a pseudopolynomial time algorithm for its solution (unless P = NP). We will therefore focus on methods for determining good lower bounds on the optimal solution value, as well as high-quality heuristic solutions. These methods include Lagrangian relaxation, branch-and-price, and the use of an asymptotically optimal greedy heuristic approach.
