20.5. Optimum Schedule Properties

Try these first

1. 1.

   What is the maximum lateness?

   Hint

   Consider what happens if a job finishes after its deadline.

2. 2.

   Define a greedy algorithm.

   Hint

   What do these choices depend on?

3. 3.

   What is the main goal of the Minimize Lateness problem?

   • Minimize total processing time
   • Minimize maximum lateness
   • Schedule as many jobs as possible

   Hint

   Consider the outcomes if jobs are late.

4. 4.

   True or False: A greedy strategy may not always yield optimal solutions.

   • True
   • False

   Hint

   Reflect on the 'shortest job first' example.

5. 5.

   Consider a set of jobs with deadlines of 2, 3, and 5 and processing times of 1, 3, and 2 each respectively. Propose a schedule that minimizes maximum lateness and show your calculations.

   Hint

   Think about delaying longer jobs for later where possible.

6. 6.

   Given a scenario where certain jobs can preempt others, how would this change your scheduling approach? Discuss the implications.

   Hint

   Consider how preemption could reduce lateness across overlapping deadlines.