Question

Exercise 37-40 deal with the problem of scheduling n jobs on a single processor. To complete job , the processor must run job j for time $t_j$without interruption. Each job has a deadline $d_j$. If we start job at time$s_j$ , 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 n jobs

40. Prove that scheduling jobs in order of increasing deadlines always produces a scheduling that minimizes the maximum lateness of a job. [Hint: First show that for a schedule to be optimal, jobs must be scheduling with no idle time between them and so that no job is scheduled before another with an earlier deadline. ]

Short answer

Scheduling jobs in order of increasing deadlines always produces a schedule that minimizes the maximum lateness of a job

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 had 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.

To proof: Scheduling jobs in order of increasing deadlines always produces a schedule that minimizes the maximum lateness of a job

PROOF BY CONTRADICTION:

There cannot be any idle times between jobs when the schedule minimizes the maximum lateness of a job, because if there is idle time then we can reduce the lateness by reducing the idle time.

Let us assume, for the sake of contraction that there is some job j with deadline $d_j$ , and some job with deadline ,such that _{$d_j<d_j$} but the maximum lateness with job j occurring before job is i less than the maximum lateness with job j occurring before job (that is, we simply switch the two jobs)

$$\begin{gathered} \mathrm{Lateness}\mathrm{job}\mathrm{j}=max\left(0,{\mathrm{e}}_{\mathrm{j}}-{\mathrm{d}}_{\mathrm{j}}\right) \\ \mathrm{Lateness}\mathrm{job}\mathrm{j}=max\left(0,{\mathrm{e}}_{\mathrm{i}}-{\mathrm{d}}_{\mathrm{i}}\right) \end{gathered}$$

Let $e_j+e_i$be the completion time with the job occurring before job j and $e_j^{\mathrm{\prime }}+e^{\mathrm{\prime }}$be the completion time with job occurring before job . Note that and

$e_j^{\mathrm{\prime }}+e_i^{\mathrm{\prime }}<e_j+e_i$

Since the maximum lateness with job occurring before job is less than the maximum lateness with job occurring before job . We require that

$max\left(0,e_j^1-d_j\right)+max\left(0,e_i^1-d_i\right)<max\left(0,e_j-d_j\right)+max\left(0,e_i-d_i\right)$

Step 2

When the maximum lateness is reduced by interchanging the jobs, then we requires that the lateness of the two jobs are non zero

_{$e_j^{\mathrm{\prime }}-d_j+e_i^{\mathrm{\prime }}-d_i<e_j-d_j+e_i-d_i$}

Add $d_j+d_i$ to each sides of the inequality

_{$e_j^{\mathrm{\prime }}+e_i^{\mathrm{\prime }}<e_j+e_i$}

Since the jobs and were simply interchanged which is contraction with

_{$e_j^{\mathrm{\prime }}+e_i^{\mathrm{\prime }}<e_j+e_i$}

This then implies that no two jobs can be interchanged $e_j^{\mathrm{\prime }}+e_i^{\mathrm{\prime }}=e_j+e_i$to reduce the maximum lateness and the scheduling jobs in order of increasing deadlines always produces a schedule that minimizes the maximum lateness of a job.