Complexity of scheduling multiprocessor tasks with prespecified processor allocations

J.A. Hoogeveen, S.L. van de Velde, B. Veltman

    Research output: Contribution to journalArticleAcademicpeer-review

    128 Citations (Scopus)
    77 Downloads (Pure)

    Abstract

    We investigate the computational complexity of scheduling multiprocessor tasks with prespecified processor allocations. We consider two criteria: minimizing schedule length and minimizing the sum of the task completion times. In addition, we investigate the complexity of problems when precedence constraints or release dates are involved.
    Original languageEnglish
    Pages (from-to)259-272
    JournalDiscrete applied mathematics
    Volume55
    Issue number3
    DOIs
    Publication statusPublished - 1995

    Keywords

    • Multiprocessor tasks
    • Prespecified processor allocations
    • Makespan
    • Total completion time
    • Release dates
    • Precedence constraints

    Cite this