1
$\begingroup$

I have $x$ uniform machines that are identical, except that each runs at a different speed; machine $j$ runs at speed $s_j$. I have $n$ identical jobs. Each machine can handle one job at a time. The time to complete a job on machine $j$ will be $1/s_j$ seconds.

I want to prove that the optimal schedule that minimizes $C_\text{max}$ is in fact also an optimal schedule for minimizing $\sum_i C_i$. Here, $C_i$ is the time when job $i$ completes (under that schedule); $\sum_i C_i$ is the sum of completion times of all jobs; and $C_\text{max} = \max_i C_i$ is the time when the last job completes. In other words, I want to prove that, when minimizing $C_{max}$ with identical jobs, the optimal schedule is also the optimal schedule for minimizing $\sum C_i$.

How can I prove this?

Or, to put it another way, using the standard notation for scheduling problems, I want to prove that $$ Q|p_i=1|C_{max} \quad \equiv \quad Q|p_i=1|\sum C_i. $$

$\endgroup$
  • $\begingroup$ Now that I understand what your question is, here is the next piece of feedback for you. What did you try? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. I suggest you edit your question to show what you've tried, what progress you've made, and where you got stuck. Have you tried working through some examples? Have you tried proving some special cases (e.g., where $s_j$ is the same for all $j$)? $\endgroup$ – D.W. Mar 22 '17 at 20:57
  • $\begingroup$ @D.W. I know that this is true, but I need a starting tip on how to prove this because I need a proof $\endgroup$ – Simon Mar 22 '17 at 21:00
  • $\begingroup$ I suggest studying the material in cs.stackexchange.com/q/59964/755, then trying to apply it here. I also suggest trying the things in my prior comment: work through some examples; prove that it is true for some easier special cases (e.g., where $s_j=1$ for all $j$). Why don't you spend some time trying that, then if you are still stuck, come back and edit your question to show us what progress you've made so far and at what stage you got stuck? $\endgroup$ – D.W. Mar 22 '17 at 21:01

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.