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

    129 Citations (Scopus)
    106 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

    Fingerprint

    Dive into the research topics of 'Complexity of scheduling multiprocessor tasks with prespecified processor allocations'. Together they form a unique fingerprint.

    Cite this