Scheduling all requests to minimise lateness
- We again have requests
- Each request has a duration given by
- Additionally, each request now also has a
- Choosing a start time for each request now gives a finish time
- A request is late if
Problem Definition
Schedule all the requests in non-conflicting way to minimise the maximum lateness
Simple greedy algorithms do not find an optimal scheduling:
- Always select the request which needs minimum time to be handled, i.e., the request which minimises
- Always select the request which has minimum “slack” time, i.e., the request which minimises