Skip to content

Instantly share code, notes, and snippets.

@arkanath

arkanath/Minimize Maximum Lateness - Pseudocode

Created February 8, 2014 10:31
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save arkanath/8881629 to your computer and use it in GitHub Desktop.
Save arkanath/8881629 to your computer and use it in GitHub Desktop.
Download ZIP
Minimize Maximum Lateness - Pseudocode
Raw
Minimize Maximum Lateness - Pseudocode
Problem: Variation of Interval Scheduling, with deadlines and duration given, all must be performed on a single resource, find the ordering with minimum maximum lateness of any interval.
Algorithm:
* Sort Jobs w.r.t the deadlines
* Let them be d1, d2, ... ,dn
* Initially f=s
* For (i=1:n)
* Assign s(i) f, f(i) = s(i) + t(i)
* f=f(i)
* EndFor
* Return <s,f>
Analysis:
* There is an optimal solution with no idle time.
* Proof of optimality by "Exchange Argument"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment