Minimizing lateness problem: Scheduling to minimize lateness

Specifications:

Single resource processes one job at a time.

Job $j$ requires $t_j$ units of processing time and is due at time $d_j.$

If $j$ starts at time $s_j,$ it finishes at time $f_j=s_j+t_j.$

Lateness: $I_j=$max$\{0,f_j-d_j\}.$

Goal: Schedule all jobs to minimize maximum lateness $)j.$

Example:

If we apply the the following greedy strategy:

$[$Shortest processing time first$]$:

Consider jobs in ascending order of processing time $t_j.$

The job schedule looks like this:

The lateness of each job is drawn in red.

The above job schedule has resulted because we have sorted the jobs in ascending

order by the job processing times. The working is shown in table below. For the jobs

with the same processing times, the one with the earlier number $($index$)$ comes first.

The finishing and lateness times of this scheduling are also listed in the table below:

As you can see, the maximum lateness, $L$ is $6.$

Does the above greedy strategy work? $($No proof required$)$

If yes, write a greedy algorithm $($pseudocode$).$

If no$,$ draw a counter job schedule $($using the above data in the yellow table$)$

following some other greedy strategy. Because in that case you can get a

different job schedule with a lesser maximum lateness. What greedy strategy

did you use $?$ No algorithm needed in this case.

Hint: It can only be either yes or no$.$ So find out if it is yes or no first, then only

do what is required for that case.