Fact-checked by Grok 2 weeks ago

Generalized assignment problem

The generalized assignment problem (GAP) is a fundamental combinatorial optimization problem in applied mathematics that seeks to assign a set of indivisible tasks to a set of capacitated agents (such as machines, servers, or facilities) in order to minimize total assignment cost or maximize total profit, subject to the constraints that each task is assigned to exactly one agent and the total resource consumption assigned to each agent does not exceed its capacity.^[1]^[2] The problem was first formally studied in 1973 by V. Srinivasan and G. L. Thompson as a special class of transportation problems, where the objective is to assign uses (tasks) to sources (agents) entirely from one source while respecting capacity limits on sources.^[3] In its standard mathematical formulation, binary decision variables x_{ij} indicate whether task j is assigned to agent i, with the objective to optimize \sum_{i,j} c_{ij} x_{ij} (where c_{ij} represents cost or profit), subject to \sum_i x_{ij} = 1 for each task j (ensuring complete assignment) and \sum_j w_{ij} x_{ij} \leq b_i for each agent i (enforcing capacity b_i with resource weights w_{ij}).^[1]^[4] GAP is known to be NP-hard, meaning that no known polynomial-time algorithm exists for finding an optimal solution for general instances, and it remains computationally challenging even for moderate-sized problems with hundreds of tasks and agents.^[5]^[2] Due to its intractability, exact solution methods such as branch-and-bound, branch-and-cut-and-price, or Lagrangean relaxation are typically limited to instances with up to a few thousand binary variables, while heuristics and approximation algorithms (e.g., greedy methods achieving a $1 - 1/e approximation ratio) are employed for larger scales.^[2]^[4]^[6]^[7] The GAP arises in numerous real-world applications, including job scheduling on parallel machines, vehicle routing with capacity constraints, facility location decisions, production planning in manufacturing systems, and resource allocation in telecommunications networks.^[8]^[9] Over the decades, various extensions have been proposed to model more complex scenarios, such as multi-resource constraints, dynamic task arrivals, or minimum quantity requirements per agent, further broadening its relevance in operations research and industrial engineering.^[10]

Overview

Definition

The generalized assignment problem (GAP) is a combinatorial optimization problem that involves assigning a set of m tasks to n agents, where each agent i has a limited resource capacity b_i, and assigning task j to agent i incurs a cost c_{ij} and consumes a resource amount p_{ij}.^[11] The goal is to find an assignment that minimizes the total cost while ensuring that each task is assigned to exactly one agent and the total resource consumption for each agent does not exceed its capacity.^[12] In this framework, the key decision variables are binary indicators x_{ij}, where x_{ij} = 1 if task j is assigned to agent i, and $0 otherwise.^[11] This setup generalizes the classical assignment problem by incorporating resource constraints on the agents, making it applicable to scenarios where assignments must respect limited capacities, such as production planning or resource allocation.^[10] An informal example of the GAP is assigning jobs to machines in a manufacturing setting, where each machine has a total processing capacity limit, jobs vary in processing time depending on the machine, and the objective is to minimize overall operational costs while ensuring no machine is overloaded and every job is processed on exactly one machine.^[11]

Historical Development

The generalized assignment problem (GAP) originated in the field of operations research during the 1970s, building upon the classical assignment problem that had been formalized earlier through methods like the Hungarian algorithm. The problem formulation was first formally studied in 1973 by V. Srinivasan and G. L. Thompson as a special class of transportation problems.^[3] The term "generalized assignment problem" and a branch-and-bound algorithm for solving it were introduced in 1975 by G. T. Ross and R. M. Soland, establishing it as a key model for resource allocation scenarios in combinatorial optimization.^[13] By the late 1970s, the GAP's computational challenges were formally acknowledged in theoretical computer science. In their 1979 book Computers and Intractability: A Guide to the Theory of NP-Completeness, Michael R. Garey and David S. Johnson discussed the NP-completeness of related problems, proving the hardness of the GAP even for restricted cases and influencing subsequent research on approximation and exact methods. This classification spurred algorithmic developments in the 1980s, including an enumerative algorithm by Silvano Martello and Paolo Toth in 1981, which improved upon early branch-and-bound approaches for practical instances.^[14] The 1990s saw comprehensive surveys that synthesized progress, such as the 1992 review by Dirk G. Cattrysse and Luk N. Van Wassenhove, which categorized exact, heuristic, and Lagrangian relaxation techniques for the GAP, highlighting its applications in production planning and facility location.^[15] Post-1980s evolution extended the static model to dynamic variants, particularly in scheduling literature; for example, Kogan and Shtub introduced the dynamic GAP in 1997, incorporating time-dependent task arrivals and due dates to model evolving resource demands.^[16] A broader historical overview in David W. Pentico's 2007 survey on assignment problems underscored the GAP's growth from a niche extension to a foundational model in optimization, with ongoing refinements in multi-objective and stochastic forms.^[17]

Mathematical Formulation

Integer Linear Programming Model

The Generalized Assignment Problem (GAP) is commonly modeled as an integer linear program to minimize the total assignment cost while respecting capacity constraints on agents and ensuring each task is assigned exactly once. This formulation captures the core structure of the problem, where agents have limited resources measured in processing times or similar units. Consider a set of n agents indexed by i = 1, \dots, n and a set of m tasks indexed by j = 1, \dots, m. The parameters include the assignment cost c_{ij} \geq 0 for assigning task j to agent i, the processing requirement p_{ij} > 0 of task j on agent i, and the capacity b_i > 0 of agent i. The decision variables are binary indicators x_{ij} \in \{0,1\}, where x_{ij} = 1 if task j is assigned to agent i, and 0 otherwise. This standard formulation was first introduced by Srinivasan and Thompson in their study of a special class of transportation problems.^[3] The complete integer linear programming model is given by:

\begin{align*} \min \quad & \sum_{i=1}^n \sum_{j=1}^m c_{ij} x_{ij} \\ \text{s.t.} \quad & \sum_{i=1}^n x_{ij} = 1 & \forall j = 1, \dots, m \\ & \sum_{j=1}^m p_{ij} x_{ij} \leq b_i & \forall i = 1, \dots, n \\ & x_{ij} \in \{0,1\} & \forall i = 1, \dots, n, \, j = 1, \dots, m. \end{align*}

The first set of constraints ensures that every task is assigned to exactly one agent, while the second set enforces the capacity limits on each agent. The objective minimizes the total cost of the assignment. This model is widely adopted in optimization literature for exact solution methods such as branch-and-bound.^[15] To obtain lower bounds for bounding procedures in branch-and-bound algorithms, a key relaxation is the linear programming (LP) relaxation, which replaces the binary constraints with $0 \leq x_{ij} \leq 1 for all i, j. Solving this LP yields a lower bound on the optimal integer solution value, and computational studies have demonstrated that it often provides tight bounds, facilitating efficient enumeration of the search tree.^[4]

Network Flow Representation

The Generalized Assignment Problem (GAP) can be modeled as a minimum cost flow problem in a flow network derived from a bipartite graph structure. The network includes a source node s, a sink node t, agent nodes corresponding to the set of agents I = \{1, \dots, n\}, and task nodes corresponding to the set of tasks J = \{1, \dots, m\}. Arcs connect the source s to each agent node i with capacity b_i (the resource capacity of agent i) and cost 0. From each agent node i to each task node j, there is an arc with capacity 1 and cost c_{ij} (the assignment cost of task j to agent i). Finally, arcs connect each task node j to the sink t with capacity 1 and cost 0. The goal is to send a flow of value m (assuming \sum_{i=1}^n b_i \geq m) from s to t at minimum total cost, ensuring each task is assigned exactly once while respecting agent capacities. This formulation assumes unit processing times p_{ij} = 1 for all i, j, where the flow value represents the number of tasks assigned to each agent.^[18] The network diagram features the source s at the top, connected downward to the agent nodes arranged in a layer. Each agent node branches to all task nodes in a second layer below, forming the bipartite connections. The task nodes then connect downward to the sink t at the bottom. Capacities and costs are labeled on the arcs: b_i on source-to-agent arcs, c_{ij} on agent-to-task arcs, and 1 on task-to-sink arcs. This structure leverages the bipartite nature of the assignment, transforming the combinatorial problem into a capacitated transportation network solvable via flow algorithms.^[18] For the general case with arbitrary processing times p_{ij} \geq 0, the unit-flow model no longer suffices because the resource consumption at agent i from assigning task j varies. One approach is to formulate the GAP as a minimum cost multicommodity flow problem, where each task j represents a distinct commodity with unit flow demand (supply 1 at s, demand 1 at t). The flow for commodity j must route through exactly one agent i, using arcs s \to i \to j \to t, with cost c_{ij} on the i \to j arc. Node capacities at agents enforce \sum_{j} p_{ij} f_{ij} \leq b_i, where f_{ij} is the flow of commodity j through agent i (either 0 or 1). This captures the heterogeneous resource usage while ensuring integral flows for binary assignments.^[10] To address general p_{ij} using single-commodity minimum cost flow, techniques such as layered networks can be applied. In a layered construction for agent i, multiple copies of the task nodes are created, layered according to cumulative resource levels up to b_i, with arcs between layers enforcing incremental assignments and costs. Alternatively, convex cost functions can be imposed on the agent-to-sink arcs to model the piecewise linear or separable costs arising from discrete assignments and varying p_{ij}, allowing polynomial-time algorithms for convex objectives. These extensions maintain the graphical structure but increase complexity for exact solutions.^[19]^[20] The primary advantage of the network flow representation is its compatibility with established minimum cost flow algorithms, such as the successive shortest path algorithm with node potentials, which exploits reduced costs and Dijkstra's algorithm for efficiency. This enables exact solutions in polynomial time for the unit processing time case and provides a foundation for heuristics or relaxations in the general case, often outperforming direct integer programming for medium-sized instances.

Special Cases and Relations

Connection to Classical Assignment Problem

The classical assignment problem (CAP), also known as the linear sum assignment problem, emerges as a special case of the generalized assignment problem (GAP) under specific parameter settings. In the CAP, there are equal numbers of jobs and agents (n = m), each job requires unit resource consumption regardless of the agent (w_{ij} = 1 for all i, j), and each agent has a unit capacity (b_i = 1 for all i). These conditions ensure that the capacity constraints in the GAP formulation—∑j w{ij} x_{ij} ≤ b_i for each agent i—simplify to at most one job per agent, while the requirement that each job is assigned exactly once (∑i x{ij} = 1 for each job j) forces exactly one job per agent, yielding the minimum-cost perfect bipartite matching.^[21] This reduction transforms the GAP into the CAP, which can be solved in polynomial time using specialized algorithms such as the Hungarian method or the Jonker-Volgenant algorithm. The Hungarian method, originally developed for the CAP, iteratively finds optimal dual variables to solve the problem via augmenting paths in O(n^3) time, while the Jonker-Volgenant algorithm improves efficiency through cost-scaling and shortest-path techniques, often achieving practical speeds for instances up to n=1000. These methods exploit the balanced, unit-demand structure absent in the general GAP.^[21] A representative example is assigning n jobs to n machines where each job takes unit time on any machine and each machine can process exactly one job, minimizing total processing cost. Without the unit capacities and uniform resource demands of the GAP, such balanced assignments would allow overloads or underutilization, but the special case enforces the one-to-one matching central to the CAP.^[21] The GAP generalizes the CAP by incorporating heterogeneous agent capacities (varying b_i) and job-specific resource requirements (varying w_{ij}), which introduce the packing-like constraints that render the problem NP-hard in general while preserving the assignment core.^[21]

Links to Bin Packing and Knapsack Problems

The Generalized Assignment Problem (GAP) exhibits strong connections to classical packing problems, particularly through analogies and special-case reductions that highlight its capacity-constrained nature. In the bin packing analogy, agents are interpreted as heterogeneous bins each with a fixed capacity b_i, while tasks represent items whose sizes w_{ij} may vary depending on the specific agent they are assigned to, and the assignment incurs a cost c_{ij} analogous to a packing penalty or profit. This framing positions the GAP as a generalized form of bin packing where item sizes are not fixed but agent-dependent, and the objective involves minimizing total cost rather than solely minimizing the number of bins used.^[22] A direct reduction establishes the bin packing problem as a special case of the decision version of the GAP. Specifically, when all agent capacities b_i are identical, task resource consumptions w_{ij} = w_j are independent of the agent i, and the problem checks whether all tasks can be feasibly assigned without exceeding capacities, this is equivalent to the classical bin packing decision problem. This reduction underscores how the GAP extends bin packing by incorporating variable costs and heterogeneous capacities.^[22] The GAP also links closely to the knapsack problem family, with the multiple knapsack problem emerging as a key special case. When task resource consumptions w_{ij} = w_j and costs c_{ij} = c_j are independent of the agent i, the GAP reduces to the multiple knapsack problem, where tasks are assigned to multiple knapsacks of capacities b_i to maximize total profit without exceeding capacities. In the single-agent case (m = 1), this further simplifies to the classical 0-1 knapsack problem, focusing on selecting a subset of tasks for the single agent's capacity b_1 to optimize profit. These reductions arise naturally when agent-task interactions are uniform, bridging the GAP to unconstrained selection in knapsack variants.^[22]^[23] An illustrative example of these links appears in scheduling tasks on limited-resource servers, where servers act as capacitated agents (bins) and tasks as items to be packed, with resource usage w_{ij} reflecting server-specific demands like CPU or memory. This setup mirrors bin packing for feasibility checks or multiple knapsack for profit maximization under uniform task values, common in cloud computing resource allocation.^[24] Through these reductions and analogies, the GAP inherits the NP-hardness of bin packing and multiple knapsack problems, as solving the general case encompasses these NP-complete special instances. This shared complexity motivates similar approximation techniques across the problems, though the GAP's agent-dependent parameters amplify the challenge.^[22]

Computational Complexity

NP-Hardness Proofs

The decision version of the Generalized Assignment Problem (GAP), which determines whether there exists an assignment of all jobs to agents such that the total assignment cost is at most some bound K while respecting the capacity constraints on agents, is NP-complete.^[25] This NP-completeness follows directly from a reduction from the partition problem, a classic NP-complete problem. Specifically, consider a partition instance consisting of a set of positive integers with total sum $2S; the corresponding GAP instance has two agents each with capacity b_i = S (i=1,2), one job per integer with processing requirement p_{ij} equal to the integer value for both agents, and assignment costs c_{1j} set to the integer value and c_{2j} = 0 (with K = S). A feasible assignment achieving cost at most K exists if and only if the integers can be partitioned into two subsets each summing to S. This establishes the basic NP-hardness of GAP.^[21]^[25] GAP is in fact strongly NP-hard, meaning it remains NP-hard even when all numerical parameters (costs, processing times, and capacities) are encoded in unary. This is shown by a polynomial-time reduction from the 3-partition problem, which is strongly NP-complete. Given a 3-partition instance with $3m positive integers a_1, \dots, a_{3m} such that \sum a_t = mB and B/4 < a_t < B/2 for each t (ensuring each subset has exactly three elements), construct a GAP instance with m agents each having capacity b_i = B, $3m jobs with processing times p_{ij} = a_t for the corresponding job t and all agents i, and uniform costs c_{ij} = 0 (with K = 0). An assignment respecting capacities exists if and only if the integers can be partitioned into m triplets each summing to B, as the size bounds prevent subsets of other cardinalities from fitting. This reduction preserves strong NP-hardness since the input sizes remain polynomial in unary encoding.^[25]^[22] Even in the special case of uniform costs (where c_{ij} = c for all i,j), GAP is strongly NP-hard, as minimizing total cost reduces to feasibility of assignment under capacities, which is equivalent to the decision version of the bin packing problem (determining if all items can be packed into at most m bins of capacity B). The latter is strongly NP-complete via a direct reduction from 3-partition, mirroring the construction above but interpreting agents as bins.^[25]^[26] These hardness results are cataloged in the comprehensive classification of NP-complete problems, where GAP appears as [MP9] and its variants align with multiple knapsack problems under [KPn].^[25]

Parameterized Complexity

The parameterized complexity of the Generalized Assignment Problem (GAP) examines its solvability when analyzed with respect to specific parameters beyond the input size, such as the number of agents n, the number of tasks m, bounds on capacities b_i, or profit thresholds. These analyses reveal that while GAP remains intractable under some natural parameters, it admits fixed-parameter tractable (FPT) algorithms and kernelizations for others, often leveraging dynamic programming (DP) techniques adapted from related problems like the multiple knapsack problem (MKP), a special case of GAP where profits are uniform.^[27] When parameterized by the number of agents n, GAP is W^[28]-hard, indicating that no FPT algorithm exists unless the parameterized hierarchy collapses, a result following from the corresponding hardness of MKP under the same parameter. In contrast, for the parameter consisting of the maximum capacity \max b_i, GAP admits a pseudo-polynomial time DP algorithm that runs in time O(m n (\max b_i)^n), filling tables that track feasible assignments and profits for subsets of tasks per agent; this approach is FPT when combined with other small parameters like n. Kernelization results further support tractability: for the number of tasks m, a kernel of size O(m^8) exists via reduction rules that prune redundant tasks based on profit-to-size ratios, while for capacity vectors (b_1, \dots, b_n), a constant-size kernel is achievable through bounding and equivalence transformations.^[27]^[27]^[27] For instances where the profit threshold k (the target total profit in the decision version) is small, GAP is FPT with a running time of O((n \log n + m) \cdot 2^k \cdot \ln^2 k), employing a DP over subsets of high-profit tasks combined with greedy filling for the remainder. Although direct results for bounded treewidth are less explicit for GAP, its formulation as an integer linear program with bounded-width constraint matrices implies FPT solvability via monadic second-order logic encodings on tree decompositions, aligning with general results for packing problems. Post-2010 advances, such as refined kernelization for multi-dimensional variants, have extended these techniques to budgeted GAP extensions where agents have multiple resource budgets, yielding FPT algorithms parameterized by the number of budget types.^[27]^[29]

Solution Approaches

Exact Solution Methods

Exact solution methods for the Generalized Assignment Problem (GAP) aim to find optimal assignments guaranteeing minimality of the total cost while respecting capacity constraints, typically employing integer programming techniques due to the problem's NP-hard nature. These methods are suitable for moderate-sized instances where computational resources allow exhaustive enumeration or tight bounding. Common approaches include branch-and-bound algorithms enhanced with relaxations, dynamic programming for small-scale problems, and cutting-plane procedures to strengthen formulations, often integrated into mixed-integer programming (MIP) solvers. Branch-and-bound methods form the cornerstone of exact solvers for GAP, systematically exploring the solution space by branching on assignment variables x_{ij} (indicating whether task j is assigned to agent i) while using lower bounds to prune suboptimal branches. Lagrangian relaxation is frequently employed to derive these bounds by dualizing the assignment constraints (ensuring each task is assigned exactly once), transforming the problem into separable subproblems solvable via dynamic programming or greedy methods, yielding a Lagrangian dual that provides a tight lower bound through subgradient optimization. For instance, relaxing the assignment constraints allows computing reduced costs for variable fixing, enabling early pruning of infeasible or suboptimal branches in a depth-first search. Seminal implementations, such as those combining Lagrangian relaxation with feasible-solution generators, have demonstrated effectiveness on instances with up to 3,000 binary variables, corresponding to approximately 30 agents and 100 tasks. Dynamic programming offers an exact approach for small instances, particularly when the number of agents m or tasks n is limited, by defining states that track the set of assigned tasks and the remaining capacities of agents. A pseudo-polynomial time algorithm can be formulated by processing tasks sequentially, with the state space comprising the current remaining capacities of the agents, computing the minimum cost recursively while ensuring feasibility. This method is viable for n \leq 20 or m \leq 10, as the state complexity grows exponentially with the number of agents but polynomially with capacities if they are bounded. Cutting-plane methods enhance exact solvers by generating valid inequalities to tighten the linear programming relaxation of the MIP formulation, focusing on the knapsack-like capacity constraints for each agent. Cover inequalities, derived from the bin-packing structure of agent capacities, exclude fractional solutions by identifying subsets of tasks whose total resource demand exceeds available capacity unless properly assigned. Exact separation procedures for these knapsack polytopes, implemented via dynamic programming, have been integrated into branch-and-cut frameworks, significantly reducing the branch-and-bound tree size for GAP instances. Integration with commercial MIP solvers like CPLEX facilitates practical exact solutions by modeling GAP as a binary integer program and leveraging built-in branch-and-cut capabilities, augmented with GAP-specific enhancements such as custom Lagrangian bounds or user-defined cuts. These solvers apply preprocessing, presolving, and advanced branching strategies tailored to the assignment structure, often outperforming pure custom implementations for instances up to moderate sizes. Empirical performance of these exact methods on benchmark instances, such as Beasley's OR-Library datasets, shows solvability to optimality for problems with up to 50 tasks and 100 agents within reasonable time limits (e.g., hours on modern hardware), though larger instances require significant computation due to the combinatorial explosion. For example, branch-and-bound with variable fixing and Lagrangian relaxation solves all instances with 20 agents and 100 tasks exactly, highlighting the scalability limits for dense, tightly capacitated problems. Recent advances include network flow-based algorithms that reformulate GAP for efficient exact solving on larger instances using min-cost flow techniques.^[18]

Approximation and Heuristic Algorithms

The generalized assignment problem (GAP) admits several approximation algorithms with guaranteed performance ratios, particularly for the maximization variant where the goal is to maximize profit subject to capacity constraints. A seminal (1 - 1/e)-approximation algorithm, due to Shmoys and Tardos, solves a linear programming relaxation of the problem and rounds the fractional solution using a greedy procedure that assigns items to bins (agents) based on their marginal profit contributions.^[30] This approach achieves an approximation ratio of approximately 0.632 and runs in polynomial time, making it suitable for instances where exact solutions are intractable.^[30] Greedy algorithms for GAP typically prioritize assignments based on measures of efficiency, such as profit density (profit per unit resource for maximization) or cost density (cost per unit resource for minimization). In one class of such algorithms, jobs are ordered by decreasing desirability, defined via weight functions that evaluate the pseudo-cost or pseudo-profit of assigning a job to a machine, and assigned sequentially to the most suitable feasible machine.^[31] Romeijn and Romero Morales analyze a family of these greedy methods and show that, under probabilistic assumptions on instance generation, they are asymptotically optimal relative to the LP relaxation, with performance improving as instance size grows.^[31] For instances with a constant number of agents, a polynomial-time approximation scheme (PTAS) exists based on dynamic programming for related problems like class-constrained packing, with similar techniques applying to GAP. The running time is polynomial in the number of tasks but exponential in the number of agents, limiting its practicality to small m. Heuristic methods, such as local search and metaheuristics, are widely used for large-scale GAP instances to obtain near-optimal solutions efficiently. Local search explores neighborhoods defined by swaps (exchanging tasks between agents) and relocations (moving a task to another agent), accepting improving or non-worsening moves to escape local optima.^[32] Tabu search enhances this by maintaining a tabu list to forbid recent moves, preventing cycling, and has been shown to achieve average optimality gaps of less than 1% on benchmark instances from the OR-Library and Yagiura datasets, even for problems with up to 100 agents and 1000 tasks.^[32] Yagiura et al. further refine this with ejection chains in the neighborhood structure for better exploration.^[33] Auction-based algorithms, originally developed by Bertsekas for the classical assignment problem, have been extended to GAP by incorporating capacity constraints through iterative bidding and price adjustments. In these extensions, unassigned tasks "bid" on agents based on cost reductions, with agents selecting the highest bidder until capacities are filled, yielding near-optimal assignments with ε-optimality guarantees for a tunable parameter ε.^[34]^[35] Such methods are particularly effective in distributed settings, like multi-robot task allocation, where they converge quickly to solutions within 5-10% of optimality on large instances.^[36] Emerging approaches include graph neural networks for approximating solutions to related assignment problems, showing promise for scalable heuristics in GAP variants as of 2024.^[37]

Applications and Extensions

Real-World Applications

The Generalized Assignment Problem (GAP) is widely applied in real-world scenarios across multiple industries, where it optimizes the allocation of tasks to resources under capacity and cost constraints, often leading to improved efficiency and reduced operational expenses. In logistics and computing sectors, GAP models help balance workloads while adhering to heterogeneous resource limits, such as time, memory, or personnel availability. These applications leverage exact and heuristic solution methods to handle large-scale instances, enabling practical decision-making in dynamic environments.^[8] In job shop scheduling, GAP assigns tasks to machines, treating processing times as assignment costs and machine availability as capacity limits to minimize total completion time or setup overheads. This approach decomposes complex scheduling into subproblems solvable via GAP variants, enhancing robustness against uncertainties like machine breakdowns. For instance, decomposition heuristics based on GAP have been used to generate feasible schedules in manufacturing settings with multiple constraints.^[38] Resource allocation in cloud computing employs GAP to assign virtual machines to physical servers, incorporating CPU, memory, and bandwidth capacities as resource bounds while minimizing energy costs or migration overheads. This formulation ensures efficient utilization of heterogeneous infrastructure, supporting scalable deployments in data centers. A joint allocation system for cloud environments has demonstrated how GAP heuristics can balance load distribution across servers to achieve cost-effective provisioning.^[39] In transportation, particularly for vehicle routing with heterogeneous fleets, GAP assigns loads or customers to vehicles, using capacity constraints for cargo volume and costs for routing distances to optimize delivery efficiency. This application is crucial for logistics firms managing mixed vehicle types, where GAP-based heuristics provide near-optimal routes. The classic generalized assignment heuristic for vehicle routing, developed by Fisher and Jaikumar, has been foundational, yielding solutions within 2-5% of optimality in practical distribution networks.^[40] Healthcare applications of GAP focus on nurse scheduling, assigning personnel to shifts based on skill levels, preferences, and ward capacities to ensure full coverage while minimizing overtime or dissatisfaction costs. This models nurses as agents with limited shift slots and patients/shifts as tasks with varying demands, often extended via goal programming for multi-objective balance. Case studies highlight GAP's impact in high-stakes sectors. In airline crew assignment, GAP formulations assign pilots and cabin staff to flight pairings under legal rest and qualification constraints, reducing payroll and deadhead travel expenses. Optimization techniques rooted in GAP have contributed to substantial savings; for example, as of 1993, crew scheduling enhancements at United Airlines yielded annual cost reductions of $16 million on a $600 million pilot payroll base.^[41] In manufacturing line balancing, GAP allocates tasks to assembly workstations to equalize workloads and respect ergonomic or tool capacities, shortening cycle times and boosting throughput. A task bottleneck variant of GAP in inspection processes reported manufacturing cost and delivery time savings by optimizing supervisor assignments to stages.^[42]^[43]

Variants and Generalizations

The multi-objective generalized assignment problem (MO-GAP) extends the standard formulation by incorporating multiple conflicting objectives, such as minimizing total assignment cost while simultaneously balancing agent loads to avoid overloads. This variant seeks Pareto-optimal solutions, where no objective can be improved without degrading another, often addressed through scalarization techniques like weighted sums that combine objectives into a single function or epsilon-constraint methods that optimize one objective subject to bounds on others. For instance, in a bi-objective setting with linear cost and nonlinear completion time objectives, iterative reallocation procedures generate the non-dominated set by prioritizing assignments and applying time penalties.^[44] The stochastic generalized assignment problem (S-GAP) introduces uncertainty, typically in job demands or processing requirements modeled as random variables, such as Bernoulli-distributed subsets of jobs requiring execution. Solutions employ recourse actions, like reassignments or penalties for unprocessed jobs, formulated as two-stage stochastic programs and solved via branch-and-bound with convex approximations of the recourse function for exact optimality. Scenario-based programming aggregates multiple realizations of uncertain parameters to derive robust assignments, ensuring feasibility across probable outcomes.^[45] In the nonlinear generalized assignment problem (NL-GAP), capacity constraints incorporate nonlinear interactions among assigned tasks, such as convex or concave cost functions reflecting economies of scale or diminishing returns, which links to quadratic assignment variants through mutual task dependencies. This extension arises in production planning where agent capacities exhibit subadditive effects, solved using branch-and-bound algorithms that integrate nonlinear programming relaxations with GAP-specific bounds; recent advances provide tighter lower and upper bounds via reformulations for continuous relaxations.^[46]^[47] The dynamic generalized assignment problem (D-GAP) accounts for time-varying task arrivals or demands, often under stochastic conditions, requiring online algorithms that make irrevocable decisions as tasks appear sequentially. In settings with stochastic unit demands, pseudo-polynomial dynamic programming reduces the problem to deterministic assignments at discrete time points, converging to global optima as time discretization refines, with applications in real-time scheduling. Online variants, assuming bounded item sizes, achieve competitive ratios through adaptive thresholds that balance immediate costs against future uncertainties.^[48]^[24] Recent variants emphasize sustainability, integrating environmental costs like carbon emissions into the objective function alongside traditional costs, particularly in logistics where assignments to facilities minimize both economic and ecological impacts. Multi-objective models in sustainable location problems allocate customers to agents using emission-based rules, solved via evolutionary algorithms like NSGA-II, revealing that distance heuristics provide near-optimal trade-offs with substantial computational savings.^[49]

References

[1]
Example 14.2 Generalized Assignment Problem - SAS Help Center
The generalized assignment problem (GAP) is that of finding a maximum profit assignment from n tasks to m machines such that each task is assigned to precisely ...
[2]
Solving the Generalized Assignment Problem: An Optimizing and ...
Aug 10, 2025 · The classical generalized assignment problem (GAP) may be stated as finding a minimum-cost assignment of tasks to agents such that each task ...
[3]
An Algorithm for Assigning Uses to Sources in a Special Class of ...
This paper considers a special class of transportation problems in which the needs of each user are to be supplied entirely by one of the available sources.
[4]
[PDF] A Branch-and-Price Algorithm for the Generalized Assignment ...
The generalized assignment problem examines the maximum profit assignment of jobs to agents such that each job is assigned to precisely one agent subject to ...Missing: definition | Show results with:definition
[5]
Generalized Assignment Problem - an overview | ScienceDirect Topics
Most applications of branch and price involve an assignment problem with complicating constraints. One example is the generalized assignment problem, which ...
[6]
[PDF] Stabilized Branch-and-cut-and-price for the Generalized Assignment ...
The Generalized Assignment Problem (GAP) is a classic scheduling problem with many applications. We propose a branch-and-cut-and- price for that problem ...
[7]
A Survey of the Generalized Assignment Problem and Its Applications
In this survey we mainly concentrate on its real-life applications in scheduling, timetabling, telecommunication, facility location, transportation, production ...
[8]
Solving the Generalized Assignment Problem: An Optimizing and ...
This NP-hard problem has applications that include job scheduling, routing, loading for flexible manufacturing systems, and facility location. Due to the ...
[9]
[PDF] Formulations and Solution Algorithms for a Dynamic Generalized ...
This paper studies a Dynamic Generalized Assignment Problem (DGAP) which extends the well-known generalized assignment problem by considering a discretized time.
[10]
https://www.cirrelt.ca/documentstravail/cirrelt-2007-16.pdf
[11]
[PDF] Adaptive Search Heuristics for The Generalized Assignment Problem
The Generalized Assignment Problem consists of assigning a set of tasks to a set of agents at minimum cost. Each agent has a limited amount of a single.
[12]
A branch and bound algorithm for the generalized assignment ...
Srinivasan and G. Thompson, “An algorithm for assigning uses to sources in a speical class of transportation problems”,Operations Research 21 (1) (1973) 284– ...
[13]
Generalized assignment problems | SpringerLink
V. Srinivasan, G.L. Thompson (1973). An algorithm for assigning uses to sources in a special class of transportation problems. Operations Research 21, 284–295 ...
[14]
A survey of algorithms for the generalized assignment problem
This paper surveys algorithms for the well-known problem of finding the minimum cost assignment of jobs to agents so that each job is assigned exactly once.
[15]
DGAP - The Dynamic Generalized Assignment Problem
The Generalized Assignment Problem (GAP) is a well-known operations research model. Given a set of tasks to be assigned to a group of agents and the cost o.
[16]
Assignment problems: A golden anniversary survey - ScienceDirect
Jan 16, 2007 · Assignment problems involve matching elements of two or more sets, often tasks and agents, to optimize an objective, such as minimizing total ...
[17]
A Network Flow Algorithm for Solving Generalized Assignment ...
Jan 12, 2021 · The generalized assignment problem (GAP) is an open problem in which an integer k is given and one wants to assign k′ agents to k(k′ ≤ k) ...
[18]
[PDF] 8.5 Minimum-Cost Network Flow Problems
1 Formulate the problem of finding the shortest path from node 1 to node 6 in Figure 2 as an MCNFP. (Hint: Think of finding the shortest path as the problem of ...
[19]
A Primal Algorithm to Solve Network Flow Problems with Convex ...
The problem of determining continuous flows of minimum cost in a network with convex cost functions is considered. The approach used is that of finding, ...
[20]
[PDF] The Generalized Assignment Problem with Minimum Quantities
unit sizes) the problem is strongly NP-complete. Moreover, we show that it is weakly NP-hard to approximate the problem within any factor. In addition, we.
[21]
[PDF] A PTAS for the Multiple Knapsack Problem*
We defined the generalized assignment problem as a maximization problem. ... Our problem is related to both the knapsack problem and the bin packing problem and ...
[22]
[PDF] The Online Stochastic Generalized Assignment Problem
In this paper we consider the online stochastic variant of the problem: Definition 2 (Online Stochastic Generalized Assignment Problem). There are n items.
[23]
[PDF] COMPUTERS AND INTRACTABILITY A Guide to the Theory of NP ...
In general, we are interested in finding the most "efficient" algorithm for solving problem. In its broadest sense, the notion of efficiency in- volves all the ...
[24]
None
### Standard Definition of the Generalized Assignment Problem (GAP)
[25]
None
Error: Could not load webpage.<|control11|><|separator|>
[26]
Knapsack Problems: A Parameterized Point of View - arXiv
Nov 23, 2016 · The idea behind fixed-parameter tractability is to split the complexity into two parts - one part that depends purely on the size of the input, ...
[27]
Knapsack problems: A parameterized point of view - ScienceDirect
Jul 5, 2019 · We give several upper and some lower bounds on the parameterized complexity and kernel sizes for the following parameters: the number of items, ...
[28]
[PDF] An approximation algorithm for the generalized assignment problem
The generalized assignment problem can be viewed as the following problem of scheduling parallel machines with costs. Each job is to be processed by exactly ...
[29]
A class of greedy algorithms for the generalized assignment problem
We propose a class of greedy algorithms for the GAP. A family of weight functions is defined to measure a pseudo-cost of assigning a job to a machine.
[30]
[PDF] Polynomial time approximation schemes for class-constrained ...
Shachnai and Tamir considered in Reference [27] a special case of the CCMK, in which ... An approximation algorithm for the generalized assignment problem.
[31]
None
### Summary of Tabu Search Heuristic Performance for GAP
[32]
An Ejection Chain Approach for the Generalized Assignment Problem
We propose a tabu search algorithm for the generalized assignment problem, which is one of the representative combinatorial optimization problems known to be NP ...
[33]
[PDF] New auction algorithms for the assignment problem and extensions
Jan 26, 2024 · We consider the classical linear assignment problem, and we introduce new auction algorithms for its optimal and suboptimal solution.
[34]
[PDF] Use of the Auction Algorithm for Target Object Mapping - DTIC
Feb 9, 1998 · The auction algorithm as developed by Bertsekas [5] will be used to solve the generalized assignment problem. In Section 2, we derive a ...
[35]
[PDF] Generalized Assignment for Multi-Robot Systems via Distributed ...
The Generalized Assignment Problem (GAP) is a well known combinatorial optimization problem with several appli- cations as vehicle routing, facility location, ...
[36]
https://arxiv.org/pdf/2004.11857
[37]
A Joint resource allocation system for cloud computing / - OpenMETU
The problem is formulated as a simple generalized assignment problem and is solved by employing a suitable heuristic algorithm. All in all, an alternative ...
[38]
A generalized assignment heuristic for vehicle routing - Fisher - 1981
We consider a common variant of the vehicle routing problem in which a vehicle fleet delivers products stored at a central depot to satisfy customer orders.
[39]
[PDF] Pairing Generation for Airline Crew Scheduling - UWSpace
United Airlines' annual savings due to crew scheduling optimization is $16-$18 million on a total crew payroll of $600 million.
[40]
[PDF] Evaluation of Task Bottleneck Generalized Assignment Problem in ...
Jun 5, 2019 · Assigning the appropriate supervisor to a specific inspection stage plays a major role because of manufacturing cost and delivery time saving of ...<|control11|><|separator|>
[41]
Pareto optimal solutions for multi-objective generalized assignment ...
Aug 6, 2025 · In this paper, we consider a bi-objective generalized assignment problem (BOGAP) and find all non-dominated points using two methods; Two ...Missing: seminal | Show results with:seminal
[42]
Exact solutions to a class of stochastic generalized assignment ...
Sep 1, 2006 · This paper deals with a stochastic Generalized Assignment Problem with recourse. Only a random subset of the given set of jobs will require ...
[43]
Generalized Assignment with Nonlinear Capacity Interaction
This paper introduces an important generalization of the GAP, which is called the 0-1 generalized assignment problem with nonlinear capacity constraints (NLGAP) ...
[44]
Lower and upper bounds for the non-linear generalized assignment ...
We consider a non-linear version of the Generalized Assignment Problem, a well-known strongly NP -hard combinatorial optimization problem.
[45]
Dynamic Generalized Assignment Problems with Stochastic ...
Feb 15, 2016 · This paper focuses on a dynamic generalization of the assignment problem where each task consists of a number of units to be performed by an ...
[46]
Efficient Allocation of Customers to Facilities in the Multi-Objective ...
This paper aims to evaluate the impact of customer allocation on the facility location in the multi-objective location problem for sustainable logistics.