# Scheduling to Minimize Lateness

4/December/2015 by Valkryst, Updated 29/June/2017

The following post is derived from notes taken while reading through this textbook.

## Assumptions and Statements:

- We have a set of jobs to schedule where each has a duration and a time that it's due at.
- We have a single processor that can run the jobs, so only one job can be run at a time.
- The processor should always be running a job.
- Our goal is to schedule the jobs so that they run in a way that causes the minimum amount of lateness. So, if we have a job that takes 2 time and is due at time 2 along with a job that takes 1 time and is due at time 2, then we run the first job. The first job finishes at time 2, then the second job runs and finishes at time 3. The lateness is 1.

## Algorithm:

**Algorithm** - minLateSchedule(Job[] jobs)

**Input** - An array of jobs to be scheduled.

**Output** - A list of jobs sorted in a way to minimize lateness and so that the processor is always running a job.

` ````
Sort the jobs by their deadlines, so that the job that is due
first is in the first position of the list and the job that is
due last is at the end of the array.
Then return the sorted array.
```