20. Greedy Algorithms: Minimizing Lateness

Try these first

1. 1.

   What is the definition of lateness?

   Hint

   Think about what happens when a job exceeds its deadline.

2. 2.

   Name one greedy strategy discussed in this section.

   Hint

   What would you typically choose first in a greedy approach?

3. 3.

   What does minimizing lateness aim to achieve?

   • Maximize job utilization
   • Minimize maximum lateness
   • Increase job duration

   Hint

   Focus on what 'minimize' means in the context.

4. 4.

   True or False: The shortest job first strategy guarantees minimum lateness.

   • True
   • False

   Hint

   Think of the counter-examples previously discussed.

5. 5.

   Design a set of jobs with varied durations and deadlines. Create a schedule that minimizes maximum lateness, and justify your reasoning.

   Hint

   Consider testing different orders.

6. 6.

   Discuss alternative strategies for minimizing lateness. Analyze their effectiveness compared to the earliest deadline first approach.

   Hint

   Reflect on cases where one strategy may succeed while another fails.