Algorithms for the Multi-Resource Generalized Assignment Problem

From MaRDI portal





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.




Cited in
(27)








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)