Scheduling multiprocessor tasks on three dedicated processors

DOI10.1016/0020-0190(92)90172-RzbMath0776.68023OpenAlexW2038534673MaRDI QIDQ1197982

Jacek Błażewicz, Paolo Dell'Olmo, Maciej Drozdowski, Maria Grazia Speranza

Publication date: 16 January 1993

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90172-r

zbMATH Keywords

schedulingresource allocationpolynomial algorithmparallel processingNP-complete

Mathematics Subject Classification ID

Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (25)

Preemptive open shop scheduling with multiprocessors: Polynomial cases and applications ⋮ Complexity of scheduling multiprocessor tasks with prespecified processors allocations ⋮ Scheduling: agreement graph vs resource constraints ⋮ An approximation algorithm for scheduling on three dedicated machines ⋮ Shop scheduling problems with multiprocessor tasks on dedicated processors ⋮ Efficiency and effectiveness of normal schedules on three dedicated processors ⋮ Scheduling independent tasks with multiple modes ⋮ Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors ⋮ A simple linear time approximation algorithm for multi-processor job scheduling on four processors ⋮ Branch and bound methods for scheduling problems with multiprocessor tasks on dedicated processors ⋮ On the complexity of adjacent resource scheduling ⋮ New perspectives in scheduling theory ⋮ Scheduling wagons to unload in bulk cargo ports with uncertain processing times ⋮ On minimizing dataset transfer time in an acyclic network with four servers ⋮ Hybrid flow-shop scheduling problems with multiprocessor task systems. ⋮ Complexity and approximation results for scheduling multiprocessor tasks on a ring. ⋮ Scheduling groups of tasks with precedence constraints on three dedicated processors. ⋮ Processor bounding for an efficient non-preemptive task scheduling algorithm ⋮ A graph based model for survivability applications ⋮ Linear algorithms for preemptive scheduling of multiprocessor tasks subject to minimal lateness ⋮ Comparability graph augmentation for some multiprocessor scheduling problems ⋮ Preemptive scheduling of multiprocessor tasks on the dedicated processor system subject to minimal lateness ⋮ Lower bound algorithms for multiprocessor task scheduling with ready times ⋮ A branch and bound algorithm for a single-machine scheduling problem with positive and negative time-lags ⋮ An approximation algorithm for nonpreemptive scheduling on hypercube parallel task systems

Cites Work

• The complexity of scheduling independent two-processor tasks on dedicated processors
• Scheduling Multiprocessor Tasks to Minimize Schedule Length
• Complexity of Scheduling Parallel Task Systems
• `` Strong NP-Completeness Results

This page was built for publication: Scheduling multiprocessor tasks on three dedicated processors