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?

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

$$\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.
• 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. – Vincenzo Apr 8 '19 at 12:54