# The Task Assignment Problem

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

Our objective is to make instances of the Task Assignmenet Problem available to the communauty of reasearchers

Any contribution would be appreciated

Task Assignment Problem Description

Constrained Task Assignment Problem Description

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

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

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

 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