The Task Assignment Problem

 

 by Sourour Elloumi @
 

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

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