Question

Exercise 37-40 deal with the problem of scheduling n jobs on a single processor. To complete job j, the processor must run job j for time without interruption. Each job has a deadline $d_j$. If we start job at time , it will be completed at time $e_j=s_j+t_j$. The lateness of the job measures how long it finishes after its deadline, that is, the lateness of job j is $max\left(0,e_j-d_j\right)$. We wish to devise a greedy algorithm that minimizes the maximum lateness of a job among the jobs.

38. The slackness of a job requiring time and with deadline d is d - t , the difference between its deadline and the time it requires. Find an example that shows that scheduling jobs by increasing slackness does not always yield a schedule with the smallest possible maximum lateness.

Short answer

Answers could vary

For example, use the five jobs of the previous exercise.

The ordering job 3, job1, job 4,job 2, job 5 in the previous exercise resulted in a maximal lateness of 5, which implies that scheduling jobs by increasing slackness does not always yield a schedule with the smallest possible maximum lateness.

Step-by-step solution

Step 1

GIVEN

n jobs

To complete job j, processor must run job j for time $t_j$without interruption.

Job j had $d_j$deadline

When job is started at then it will be completed at$e_j=s_j+t_j$

Lateness job $j=max\left(0,e_j-d_j\right)$

Slackness job j is _{$d_j-t_j$}

We are interested in minimizing the maximum lateness of a n job among jobs using a greedy algorithm.

For example, I will use the five jobs in the previous exercise.

$\begin{array}{r}{t}_1=25\\ d_1=50\\ t_2=15\\ d_2=60\\ t_3=20\\ d_3=60\\ t_4=5\\ d_4=55\\ t_5=10\\ d_5=75\end{array}$

Let us determine the slackness of each job

$\begin{array}{r}{d}_1-t_1=50-25=25\\ d_2-t_2=60-15=45\\ d_3-t_3=60-20=40\\ d_4-t_4=55-5=50\\ d_5-t_5=75-10=65\end{array}$

The jobs in the order of increasing slackness are then : job 1, Job 3, Job 2, Job 4 and Job 5.

Step 2

Ordering jobs: Job 1 ,Job 3,Job 2,Job 4,Job 5

We first complete job 1 starting at $s_1=0$, which requires a time $t_1=25$of which is within the deadline of $d_1=50$

Lateness job $1=max\left(0,e_1-d_1\right)=max(0,0+25-50)=0$

Next, job 3 would start at $s_3=e_1=s_1+t_1=0+25=25$, which requires a time of $t_3=20$and thus job 3 is completed at $e_3=s_3+t_3=20+25=45$which is within the deadline of $d_3=60$

Lateness job $3=max\left(0,e_3-d_3\right)=max(0,45-60)=0$

Next, job 2 would start at $s_2=e_3=45$, which requires a time of $t_2=15$and thus job is completed at $e_2=s_2+t_2=45+15=60$which is not within the deadline of $d_2=60$

Lateness job $2=max\left(0,e_2-d_2\right)=max(0,60-60)=0$

Next, job 4 would start at $s_4=e_2=60$, which requires a time of ${\mathrm{t}}_4=5$and thus job 4 is completed at $e_4=s_4+t_4=60+5=65$which is within the deadline of $d_4=55$

Lateness job $4=max\left(0,e_4-d_4\right)=max(0,65-55)=10$

Next, job 5 would start at $s_5=e_2=65$, which requires a time of $t_5=10$and thus job 5 is completed at $e_5=s_5+t_5=65+10=75$ which is within the deadline of

Lateness job $5=max\left(0,e_5-d_5\right)=max(0,75-75)=0$

We then note that the maximal lateness is max (0,0,0,10,0) = 10

However , the ordering job 3, job1, job 4,job 2, job 5 in the previous exercise resulted in a maximal lateness of , which implies that scheduling jobs by increasing slackness does not always yield a schedule with the smallest possible maximum lateness.