20.3. Proof of Correctness

Try these first

1. 1.

   Define 'lateness' in scheduling.

   Hint

   Think about what happens when a job is done late.

2. 2.

   What is a greedy algorithm?

   Hint

   Consider how these choices are evaluated.

3. 3.

   What is the primary goal of the Minimizing Lateness problem?

   • Minimize average lateness
   • Minimize maximum lateness
   • Maximize finish time

   Hint

   Think about which job's lateness affects the overall metric.

4. 4.

   True or False: A greedy algorithm always guarantees an optimal solution.

   • True
   • False

   Hint

   Evaluate instances of greedy failure.

5. 5.

   Given five jobs with durations 1, 2, 3, 4, 5 and deadlines 1, 2, 3, 4, 5 respectively, arrange them to minimize lateness.

   Hint

   Check for any jobs that are initially late when plotted together.

6. 6.

   If you have ten jobs with varying durations and overlapping deadlines, create a table comparing which scheduling order minimizes maximum lateness.

   Hint

   Make detailed time calculation for finishes to track lateness effectively.