2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ See multiprocessor scheduling. $\endgroup$ – Pål GD Apr 6 at 9:58
  • $\begingroup$ Do you want to find the optimal solution, or are approximations good enough? Are you implementing it, or looking for theoretical solutions? $\endgroup$ – Pål GD Apr 6 at 10:08
  • $\begingroup$ @PålGD I want a optimized and accurate solution. Just came up this question... I guess it is kinda NP hard problem... $\endgroup$ – Gaame Apr 6 at 10:22
  • $\begingroup$ It is definitely NP-hard, even with just 2 machines, with equal times for both machines. $\endgroup$ – Pål GD Apr 6 at 10:29
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I want to know exactly how those softwares work... $\endgroup$ – Gaame Apr 7 at 1:34
  • $\begingroup$ That's another question entirely. Anyway, at their core they need to do enumeration, giving something not too dissimilar from your $n^n$ bound. The main difference is that their average case is extremely optimized and often fast in practice. $\endgroup$ – Vincenzo Apr 8 at 12:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.