Text:

Problem. We shall consider a set J of jobs where each job j has a duration D(j) and a priorityP(j), both > 0. Only one job can be executed at a time, and once a job j has started (at time t) it will be finished (at time t + D(j)). Example: if j1 is the first job to run and j2 is the second, j1will finish at time D(j1) and j2 will finish at time D(j1) + D(j2).

For a given schedule S, let FS(j) denote the time at which job j finishes according to S. Our goal is to find a schedule that minimizes

C (S ) = ?? P (j ) FS (j )j?J

We shall consider the following four strategies, all potentially non-deterministic: 1. Schedule the jobs in decreasing order of their priority, that is:

for all i,k ? J, if P(i) > P(k) then job i must execute before job k. 2. Schedule the jobs in increasing order of their duration, that is:

for all i,k ? J, if D(i)

for all i,k ? J, if P(i)?D(i) > P(k)?D(k) then job i must execute before job k. 4. Combine strategies 1 and 2 into a strategy where, with R = P :

D for all i,k ? J, if R(i) > R(k) then job i must execute before job k.

Your task is:

(15p) For each of the strategies (1-3) above, find an example where that strategy does not

produce an optimal schedule, but strategy 4 does.

Problem. We shall consider a set J of jobs where each job j has a duration D(j) and a priority P(j), both > 0. Only one job can be executed at a time, and once a job j has started (at time t) it will be finished (at time t D(j)). Example: if ji is the first job to run and j2 is the second, j? will finish at time D(i) and j2 will finish at time D(ji) + D (j2) For a given schedule S, let Fs (j) denote the time at which job j finishes according to S. Our goal is to find a schedule that minimizes C(s)- P(j) Fs(j) JE.J We shall consider the following four strategies, all potentially non-deterministic: 1. Schedule the jobs in decreasing order of their priority, that is: for all i, k E J, if P(i) > P(k) then job i must execute before job k. 2. Schedule the jobs in increasing order of their duration, that is: for all i, k E J, if D(i) P(k) - D(k) then job i must execute before job k. 4. Combine strategies 1 and 2 into a strategy where, with R - for all i, k E J, if R(i) > R(k) then job i must execute before job k. Your task 2S. 1. (15p) For each of the strategies (1-3) above, find an example where that strategy does not produce an optimal schedule, but strategy 4 does Problem. We shall consider a set J of jobs where each job j has a duration D(j) and a priority P(j), both > 0. Only one job can be executed at a time, and once a job j has started (at time t) it will be finished (at time t D(j)). Example: if ji is the first job to run and j2 is the second, j? will finish at time D(i) and j2 will finish at time D(ji) + D (j2) For a given schedule S, let Fs (j) denote the time at which job j finishes according to S. Our goal is to find a schedule that minimizes C(s)- P(j) Fs(j) JE.J We shall consider the following four strategies, all potentially non-deterministic: 1. Schedule the jobs in decreasing order of their priority, that is: for all i, k E J, if P(i) > P(k) then job i must execute before job k. 2. Schedule the jobs in increasing order of their duration, that is: for all i, k E J, if D(i) P(k) - D(k) then job i must execute before job k. 4. Combine strategies 1 and 2 into a strategy where, with R - for all i, k E J, if R(i) > R(k) then job i must execute before job k. Your task 2S. 1. (15p) For each of the strategies (1-3) above, find an example where that strategy does not produce an optimal schedule, but strategy 4 does