The Task Assignment Problem

 by Sourour Elloumi @
 

This problem is also known as the Module Allocation Problem or the Quadratic Semi-Assignment Problem

---

Task Assignment Problem Description

Constrained Task Assignment Problem Description

Files format

The TAP instances files

The CTAP instances files

A few references on the Task Allocation Problem

---

Instances and Solution files format  

1- TAP Instances

Each .dat file contains one instance, in the following format : Number of tasks, Number of processors, execution costs, communication costs

N
M
For  {i in 1..N}  For {j in 1..M} e(i,j)
For {i in 1..N-1} For {j in i+1..N} For {k in 1..M} For{l in 1..M} c(i,k,j,l)

The corresponding .sol file contains an optimal solution, in the following format : For each task i, the processor p(i) it is assigned to; the value of that solution

For  {i in 1..N}  i p(i)
Solution value

2- CTAP Instances

Each .dat file contains one instance, in the following format : Number of tasks, Number of processors, execution costs, communication costs, memory requirements of the tasks, memory capacity of the processors

N
M
For {i in 1..N}  For {k in 1..M} e(i,k)
For {i in 1..N-1} For {j in i+1..N} c(i,j)
For {i in 1..N} s(i)
For {k in 1..M} n(k)

The corresponding .sol file contains an optimal solution, in the following format : For each task i, the processor p(i) it is assigned to; the value of that solution

For  {i in 1..N}  i p(i)
Solution value

---

References

[1] A. Billionnet and S. Elloumi. Best reduction of the quadratic semi-assignment problem - Discrete Applied Mathematics (DAM) vol. 109(3), 2001.

[2] S. Elloumi, F. Roupin and E. Soutif. Comparison of Different Lower Bounds for the Constrained Module Allocation Problem - TR CEDRIC No 473, 2003. Details

[3] F. Roupin. From Linear to Semidefinite Programming: an Algorithm to obtain Semidefinite Relaxations for Bivalent Quadratic Problems - TR CEDRIC No 388, 2003. Details

---

Back to Sourour Elloumi's Homepage

Back to Equipe Optimisation Combinatoire