Task Distribution Algorithm

Question

Different machine has different efficiency on different tasks, like:

| T/M | M1  | M2  | M3  |
| T1  | a11 | a21 | a31 |
| T2  | a12 | a22 | a32 |
| T3  | a13 | a23 | a33 |

So, Machine $M_1$ needs $a_{11}$ time on finishing Task $T_1$.

Each machine can process one task everytime. Each single task cannot be splited up. How to find the min finishing time for all tasks in sum? (finishing time of each task include its waiting time and processing time).

I only has a awful enumerate algorithm for this, enumerate all possible solution and find out the min one. That costs $O(n^n)$.

Is there any optimized algorithm for this question?

Vincenzo · Answer

The problem is also called scheduling unrelated machines and as observed in the comments, it is NP-hard.

If you really want an optimal solution, I recommend to use an integer linear programming solver, such as lp_solve, SYMPHONY or GLPK. The problem can be formulated as an integer linear program as follows:

$$
sum_{i=1}^m x_{ij}=1, qquad j = 1,...,n 
$$
$$
sum_{j=1}^n p_{ij} x_{ij} le T, qquad i = 1, ..., m
$$
$$
x_{ij}=0, qquad text{if} p_{ij}>T
$$
$$
x_{ij} in {0,1}, qquad forall i, j.
$$

Here $m$ is the number of machines, $n$ the number of jobs, $p_{ij}$ the time required to run job $j$ on machine $i$, and the variable $x_{ij}$ stands for 1 or 0 depending whether the job $j$ will be assigned to machine $i$ or not. The number $T$ is a parameter: if the integer linear system can be satisfied, then there is an assignment of jobs to machines that has overall finishing time (makespan) at most $T$. For any given $T$, the integer linear programming solver will tell you if the system is feasible (and if so, what are the values $x_{ij}$). Then you can find the best value of $T$ (and the corresponding $x_{ij}$s) by running a simple binary search.

Task Distribution Algorithm

One Answer

Add your own answers!

Ask a Question