(Solved): Minimizing lateness problem: Scheduling to minimize lateness Specifications: Single resource proces ...

Minimizing lateness problem: Scheduling to minimize lateness Specifications: Single resource processes one job at a time. Job j requires $t_{\text{, }}$ units of processing time and is due at time $d_j$ If $j$ starts at time $s_j$, it finishes at time $f_1=s_1+t$. Lateness: $l_i=\max \left\{0,f_i?d_j\right\}$. Goal: Schedule all jobs to minimize maximum lateness $L=\max I_1$. Example: If we apply the the following greedy strategy: [Shortest processing time first]: Consider jobs in ascending order of processing time $t_4$. 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 the counter job schedule (using the above data in the yellow table). Because in that case you can get a different job schedule with a lesser maximum lateness. 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.