Think about a setting where there are $n$ tasks and $m$ machines. We are interested in task-machine assignment. Let $p_i$ be a non-negative completion time of job $i$. Also, $x_i$ denotes the machine where task $i$ is scheduled. A machine processes the task having the smallest completion time, then the second etc. So for simplicity we assume the tasks available are ordered such that $p_1\leq p_2 \leq \ldots \leq p_n$.

The completion time of each task is given with:

$C_j(x) = \sum_{k \leq j,x_k=x_j} p_k $.

And the social cost is defined as:

$C(x)= \sum_{j \in [n]}C_j(x)$.

An optimal solution $x^*$ is a strategy that minimizes $C(x)$.

How can we prove that there exists an efficient polynomial time algorithm that computes the optimal solution?

  • $\begingroup$ Greedy algorithm works after sorting the jobs in increasing time. But can't prove it. $\endgroup$ – independentvariable May 4 '18 at 12:55

Your Answer

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

Browse other questions tagged or ask your own question.