0
$\begingroup$

Consider a set of jobs, each having its deadlines and process time. How to find a permutation of them such that if they are executed in that sequence, they all finish before their deadline
or figure out that no such permutation exists.

My Thoughts:
There could be some greedy strategy, but I am not sure how to arrive at that.

Improve this question
$\endgroup$
2
$\begingroup$

The greedy strategy you are looking for is Earliest-Deadline-First and it's optimal in minimizing maximum lateness.

Minimizing sum of latenesses is NP-complete.

Improve this answer
$\endgroup$
2
  • $\begingroup$ So we won't be considering process time at all? Simply sort the jobs by deadlines in ascending order and process them in that order. Is that correct? $\endgroup$
    – daniel
    Nov 17 '21 at 22:13
  • $\begingroup$ You can find more info in the text book Algorithm Design and the corresponding slides for greedy algorithms (pdf). $\endgroup$
    – Pål GD
    Nov 17 '21 at 22:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.