20.7. Transforming Schedule

Try these first

1. 1.

   Define lateness in the context of scheduling jobs.

   Hint

   Think about the relationship between finishing a job and the deadline.

2. 2.

   What is a greedy algorithm?

   Hint

   Focus on how decisions are made in stages.

3. 3.

   What is the goal of the Minimizing Lateness problem?

   • To minimize the total time taken by all jobs.
   • To minimize the maximum lateness of jobs.
   • To ensure all jobs are finished by their deadlines.

   Hint

   Think about what we are trying to achieve with the schedule.

4. 4.

   True or False: The greedy strategy that sorts jobs by their shortest time to completion will always yield the best solution for minimizing lateness.

   • True
   • False

   Hint

   Review the counterexamples discussed.

5. 5.

   You have five jobs with the following lengths and deadlines: { (1, 2), (2, 4), (3, 6), (1, 3), (4, 8) }. Which order minimizes maximum lateness?

   Hint

   Prioritize jobs based on deadlines.

6. 6.

   If a job takes 5 units of time and has a deadline of 10, but another job takes 1 unit of time with a deadline of 5, analyze the best scheduling approach.

   Hint

   Think about the implications of finishing one before the other.