3
$\begingroup$

Given $n$ jobs, schedule them such that the weighted sum is minimum.

weighted minimum sum S for the schedule $\sigma = \{ J_1, J_2, ... J_n \}$ is given by :

$S = \sum_{1\leqq i \leqq n} w_i C_i$ where $C_i\ = \sum_{1\leqq j \leqq i} t_j$ and $w_i$ is the weight of job $J_i$, $t_i$ is the time $J_i$ takes to complete.

I think the solution is to schedule the jobs in shortest weighted processing time i.e. to arrange them in the increasing order of $ t_i/w_i $.

But how to prove this.

$\endgroup$
4
$\begingroup$

Hint: Let $\sigma$ be the optimal schedule. Suppose that jobs $k$ and $k+1$ are switched. How is the cost affected? What does the optimality of $\sigma$ tell us about $w_k,w_{k+1},t_k,t_{k+1}$?

$\endgroup$

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.