Let us consider the scheduling problem 1|ri,pi=1|Lmax (basically, this means there is one machine on which we have to schedule n jobs (all with identical procssing time 1) in such a way that the maximum lateness is minimzed).

I know that this problem can be solved by using the Earlist Avaible Due Date; which means that at each point in time we schedule the avaible job with the lowest due date. However, what would be the complexity of this?

I feel like i should start out by sorting the list of jobs by increasing due date, which can be done in O(n*log/n)). However, when I start scheduling, i always have to check whether a job is avaiable (ie whether its already released). We might have to check the whole list until we eventually find an avaible job. Since this might happen in each of the n scheduling steps, I feel like the total complexity should be O(n+(n-1)+(n-2)...+1)=O(n*n).

Is this correct? Is there some way to implement this algorithm in O(n*log/n))?


Your Answer

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

Browse other questions tagged or ask your own question.