On-line scheduling of jobs with fixed start and end times

G.J. Woeginger

    Research output: Contribution to journalArticleAcademicpeer-review

    108 Citations (Scopus)


    We investigate an on-line scheduling problem on a single machine where jobs have fixed start and end times. If a job is not processed immediately after its arrival or if its processing is aborted, the job is lost. The goal is to maximize the total value of all processed jobs. In general, this problem does not allow on-line approximations with finite worst case guarantee. We give an approximation algorithm with worst case ratio four for large classes of special instances, and we also prove that the factor four is best possible. One of our classes contains the instances where the job values are proportional to the job lengths.
    Original languageEnglish
    Pages (from-to)5-16
    Number of pages12
    JournalTheoretical Computer Science
    Issue number1
    Publication statusPublished - 1994


    Dive into the research topics of 'On-line scheduling of jobs with fixed start and end times'. Together they form a unique fingerprint.

    Cite this