Scheduling with tails and deadlines

F. Sourd, W.P.M. Nuijten

    Research output: Contribution to journalArticleAcademicpeer-review

    5 Citations (Scopus)
    1 Downloads (Pure)


    This paper discusses scheduling problems that combine tails and deadlines or, equivalently, due dates and deadlines. This approach is illustrated to be of practical interest to strengthen some lower bounds in shop scheduling problems. We show that both deadlines and tails can efficiently be modelled via a non-decreasing cost function of the completion time so that we can use the O(n2) algorithm due to Baker, Lawler, Lenstra and Rinnooy Kan for the 1pmtn,prec,rj,fmax problem to solve 1pmtn,prec,rj,dj,qjCmax. For this problem, we present an algorithm with improved complexity of O(e+nlogn) where e is the number of precedence constraints and we present some extensions of this algorithm to solve two parallel machine problems with unit execution time operations.
    Original languageEnglish
    Pages (from-to)105-121
    JournalJournal of Scheduling
    Issue number2
    Publication statusPublished - 2001


    Dive into the research topics of 'Scheduling with tails and deadlines'. Together they form a unique fingerprint.

    Cite this