3. Scheduling to Minimize Lateness: Given a set of jobs specified by the length of time it will take to accomplish the jobs and a deadline for the job to be completed and a single resource to complete those jobs. For instance, job; requires li units of time to complete and has a deadline of di. You goal is to create a schedule for the jobs, that is an order in which they should run on the resource that will minimize the maximum lateness of the jobs. Lateness is the maximum of {completion time of the job - the deadline for the job, 0} To keep things simple we will assume that: Time begins at 0 all lengths and deadlines are integers A task may start at the same time another finishes and it is not considered overlapping the earlier task. We will disregard schedules that contain any gaps between jobs and assume that as soon as one job finishes the next job begins. This is not a real restriction since if a schedule did contain any gaps, removing them cannot increase the lateness of any job, and thus the resulting schedule would be at least as good as the original schedule. - 3.a Give a counterexample consisting of two jobs and two schedules that show that Shortest job first does not always result in finding the optimal schedule. You must use the table below lidi Schedule Max lateness of schedule Shortest is Job 1 Job 1, Job 2 Job 2 Job 2, Job 1 - 3.b Give a counterexample consisting of two jobs and two schedules that show that Shortest slack time first does not always result in finding the optimal schedule. I di Schedule Max lateness of schedule Job 1 has Shortest Job 1, Job 2 slack time Job 2 Job 2, Job 1 - 3.c Prove that Earliest deadline first finds an optimal schedule 3. Scheduling to Minimize Lateness: Given a set of jobs specified by the length of time it will take to accomplish the jobs and a deadline for the job to be completed and a single resource to complete those jobs. For instance, job; requires li units of time to complete and has a deadline of di. You goal is to create a schedule for the jobs, that is an order in which they should run on the resource that will minimize the maximum lateness of the jobs. Lateness is the maximum of {completion time of the job - the deadline for the job, 0} To keep things simple we will assume that: Time begins at 0 all lengths and deadlines are integers A task may start at the same time another finishes and it is not considered overlapping the earlier task. We will disregard schedules that contain any gaps between jobs and assume that as soon as one job finishes the next job begins. This is not a real restriction since if a schedule did contain any gaps, removing them cannot increase the lateness of any job, and thus the resulting schedule would be at least as good as the original schedule. - 3.a Give a counterexample consisting of two jobs and two schedules that show that Shortest job first does not always result in finding the optimal schedule. You must use the table below lidi Schedule Max lateness of schedule Shortest is Job 1 Job 1, Job 2 Job 2 Job 2, Job 1 - 3.b Give a counterexample consisting of two jobs and two schedules that show that Shortest slack time first does not always result in finding the optimal schedule. I di Schedule Max lateness of schedule Job 1 has Shortest Job 1, Job 2 slack time Job 2 Job 2, Job 1 - 3.c Prove that Earliest deadline first finds an optimal schedule
