patternMinor
Single machine job scheduling to minimize weighted sum of completion time
Viewed 0 times
minimizecompletionschedulingweightedtimesinglesummachinejob
Problem
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.
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.
Solution
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}$?
Context
StackExchange Computer Science Q#7521, answer score: 4
Revisions (0)
No revisions yet.