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

A few references on the Task Allocation Problem

Each

.datfile contains one instance, in the following format : Number of tasks, Number of processors, execution costs, communication costsN

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

.solfile contains an optimal solution, in the following format : For each task i, the processor p(i) it is assigned to; the value of that solutionFor {i in 1..N} i p(i)

Solution value

2- CTAP InstancesEach

.datfile 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 processorsN

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

.solfile contains an optimal solution, in the following format : For each task i, the processor p(i) it is assigned to; the value of that solutionFor {i in 1..N} i p(i)

Solution value

[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