Algorithms for the Multi-Resource Generalized Assignment Problem
The multi-resource generalized assignment problem can be formulated as follows: minimize \(\sum_{i\in I}\sum_{j\in J} c_{ij} x_{ij}\) subject to (1) \(\sum_{j\in J} x_{ij}=1\), \(\forall i\in I\), (2) \(\sum_{i\in I} a_{ijk} x_{ij}\leq b_{jk}\), \(\forall k\in K\), \(j\in J\), (3) \(x_{ij}=0\) or 1 \(\forall i\in I\), \(j\in J\), where \(I\) is the index set of tasks, \(J\) is the index set of agents and \(K\) is the index set of resources used by agents to perform these tasks. \(a_{ijk}\) is the amount of resource \(k\) used by agent \(j\) in performing task \(i\), \(b_{jk}\) is the amount of resource \(k\) available to agent \(j\), and \(c_{ij}\) is the cost of assigning task \(i\) to agent \(j\). Three Lagrangian-based relaxations are studied. The first is obtained by relaxing constraint set (1). For the second, a constraint in set (2) is chosen and all other constraints in (2) and (1) are used. The third relaxation is obtained by using only constraint set (2). Via subgradient optimization bounds are derived from these relaxations, relationships between these bounds are established and extensive computational experience is reported. With respect to these relaxations three heuristics are designed, whose performance is numerically tested. Sensitivity analysis is carried out in order to fix some of the variables and thus to speed up a subsequent implicit enumeration method. Finally, a branch-and-bound procedure is developed, which integrates one of the heuristics. Again, computational results are reported.
- Heuristics for the multi-resource generalized assignment problem
- Relaxation heuristics for a generalized assignment problem
- The generalized assignment problem
- Solving the generalized assignment problem: an optimizing and heuristic approach
- A survey of algorithms for the generalized assignment problem
- A two-stage model for a day-ahead paratransit planning problem
- Local search intensified: very large-scale variable neighborhood search for the multi-resource generalized assignment problem
- R \& D planning and the generalized assignment problem
- Low earth orbit satellite based communication systems -- research opportunities
- A contraction for the multiparametric integer linear programming problem
- A multi-product loading problem: A model and solution method
- Capacity planning by the dynamic multi-resource generalized assignment problem (DMRGAP)
- A robust heuristic for the generalized assignment problem
- The resource dependent assignment problem with a convex agent cost function
- Formulating and solving production planning problems
- Heuristics for the generalised assignment problem: Simulated annealing and tabu search approaches
- A binary-rounding heuristic for multi-period variable-task-duration assignment problems
- A pseudo-polynomial time algorithm for solving the resource dependent assignment problem
- A very large-scale neighborhood search algorithm for the multi-resource generalized assignment problem
- Fleet management: a vehicle and driver assignment model
- A survey of models and algorithms for winter road maintenance. II: System design for snow disposal
- On the variable-depth-search heuristic for the linear-cost generalized assignment problem
- Reducing multivalued discrete variables in solving separable task assignment problems
- Resource-constrained assignment problems with shared resource consumption and flexible demand
- Fast machine reassignment
- Heuristics for the multi-resource generalized assignment problem
- Bicriteria multiresource generalized assignment problem
- Heuristics and matheuristics for a real-life machine reassignment problem
- scientific article; zbMATH DE number 6796293 (Why is no real title available?)
- Dynamic generalized assignment problems with stochastic demands and multiple agent-task relationships
- A three-phase matheuristic algorithm for the multi-day task assignment problem
- A Survey of the Generalized Assignment Problem and Its Applications
This page was built for publication: Algorithms for the Multi-Resource Generalized Assignment Problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3981148)