Reallocation Problems in Scheduling

Michael A. Bender, Martin Farach-Colton, Sándor P. Fekete, Jeremy T. Fineman, Seth Gilbert

    Research output: Contribution to journalArticlepeer-review


    In traditional on-line problems, such as scheduling, requests arrive over time, demanding available resources. As each request arrives, some resources may have to be irrevocably committed to servicing that request. In many situations, however, it may be possible or even necessary to reallocate previously allocated resources in order to satisfy a new request. This reallocation has a cost. This paper shows how to service the requests while minimizing the reallocation cost. We focus on the classic problem of scheduling jobs on a multiprocessor system. Each unit-size job has a time window in which it can be executed. Jobs are dynamically added and removed from the system. We provide an algorithm that maintains a valid schedule, as long as a schedule with sufficient slack exists. The algorithm reschedules only a total number of (Formula Presented.) jobs for each job that is inserted or deleted from the system, where n is the number of active jobs and (Formula Presented.) is the size of the largest window.

    Original languageEnglish (US)
    Pages (from-to)389-409
    Number of pages21
    Issue number2
    StatePublished - Oct 5 2015


    • Online problems
    • Reallocation
    • Scheduling

    ASJC Scopus subject areas

    • General Computer Science
    • Computer Science Applications
    • Applied Mathematics


    Dive into the research topics of 'Reallocation Problems in Scheduling'. Together they form a unique fingerprint.

    Cite this