Practice Optimum Schedule Properties (20.5) - Greedy Algorithms: Minimizing Lateness

Practice: Optimum Schedule Properties

Lesson 20.5Greedy Algorithms: Minimizing Lateness

Practise this section

9 questions

Flashcard drill
2 cards from this section. Quick, good the night before a test.
Exercise
6 questions · about 4 min · pass mark 70%. Hints available.
Sign up to start the exercise
Quiz
3 questions · about 2 min · pass mark 70%. Hints available.
Sign up to start the quiz

6 sample questions

Question 1.
What is the maximum lateness?
Show hintHide hint
Consider what happens if a job finishes after its deadline.
Question 2.
Define a greedy algorithm.
Show hintHide hint
What do these choices depend on?
3Question 3.
What is the main goal of the Minimize Lateness problem?
- Minimize total processing time
- Minimize maximum lateness
- Schedule as many jobs as possible
Show hintHide hint
Consider the outcomes if jobs are late.
4Question 4.
True or False: A greedy strategy may not always yield optimal solutions.
- True
- False
Show hintHide hint
Reflect on the 'shortest job first' example.
Question 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.
Show hintHide hint
Think about delaying longer jobs for later where possible.
Question 6.
Given a scenario where certain jobs can preempt others, how would this change your scheduling approach? Discuss the implications.
Show hintHide hint
Consider how preemption could reduce lateness across overlapping deadlines.

5 more questions in this section. Enroll free to practise them all.