Algorithms and Complexity No.4 [latex][/latex]

WIS problem:
Given:
Suppose we are to schedule print jobs on a printer. Each job $j$ has a weight $w_j>0$ (representing how important the job is) and a processing time $t_j$ (representing how long the job takes). A schedule is an ordering $\sigma=\langle j_1,j_2,\dots,j_n \rangle$ of the jobs.

For a given schedule $\sigma$ , let $F(\sigma,j)$ be the finishing time of job $j$ in the schedule.

Want:
Design a greedy algorithm that computes a schedule with minimum weighted average finishing time that minimizing $\sum_j w_jF(\sigma,j)$ .

Solve:
Our greedy algorithm can be sorting the jobs in increasing $t_j/w_j$ order.

Assume for simplicity that no 2 jobs have the same ratio. To prove that the schedule is OPT, we resort to the usual exchange argument.
Suppose the OPT is $\sigma=\langle j_1,j_2,\dots,j_n \rangle$ and there are 2 adjacent indices $j_i$ and $j_{i+1}$ such that:

$\frac{t_{j_i}}{w_{j_i}}>\frac{t_{j_{i+1}}}{w_{j_{i+1}}}$

Now, consider:

$\sigma'=\langle j_1,j_2,\dots,j_{i-1},j_{i+1},j_{i},j_{i+2},\dots,j_n \rangle,$

where we swap the position of $j_{i}$ and $j_{i+1}$ , and leave other jobs in their places. We now need to prove the change decreases the cost of the schedule.
Notice that the finishing time of jobs other than $j_{i}$ and $j_{i+1}$ is the same in $\sigma$ and $\sigma '$ . Thus:

$\sum_j w_jF(\sigma,j)-\sum_j w_jF(\sigma ',j)$
$=$
$w_{j_{i}}F(\sigma,j_i)+w_{j_{i+1}}F(\sigma,j_{i+1})-w_{j_{i}}F(\sigma ',j_i)+w_{j_{i+1}}F(\sigma ',j_{i+1})$

Let $X=F(\sigma,j_{i-1})$ . Then:

$F(\sigma,j_{i}) = X+t_{j_{i}},$
$F(\sigma,j_{i+1})=X+t_{j_{i}}+t_{j_{i+1}}$
$F(\sigma ',j_{i+1})=X+t_{j_{i+1}}$
$F(\sigma ',j_{i})=X+t_{j_{i}}+t_{j_{i+1}}$