Scheduling multiprocessor tasks on three dedicated processors
From MaRDI portal
The authors analyse the problem of scheduling a set of uni- and duo- processor tasks on three dedicated processors. The objective of the problem is to find a schedule with minimum length. The general problem is shown to be strongly NP-hard, which strengthens the best known complexity result. Finally, they present polynomially solvable special cases as well as an approximation algorithm for some hard subproblems.
Recommendations
- Scheduling groups of tasks with precedence constraints on three dedicated processors.
- Efficiency and effectiveness of normal schedules on three dedicated processors
- Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors
- scientific article; zbMATH DE number 1979516
- Scheduling multiprocessor tasks -- An overview
- Task splitting for three machine preemptive scheduling
- On multiprocessor system scheduling
- Shared processor scheduling of multiprocessor jobs
Cites work
Cited in
(32)- Scheduling three chains on two parallel machines
- Task splitting for three machine preemptive scheduling
- Preemptive scheduling of multiprocessor tasks on the dedicated processor system subject to minimal lateness
- A comparison of heuristics for scheduling multiprocessor tasks on three dedicated processors: Short communication: Special issue on task sheduling problems on parallel and distributed systems
- A branch and bound algorithm for a single-machine scheduling problem with positive and negative time-lags
- Complexity of scheduling multiprocessor tasks with prespecified processors allocations
- Efficiency and effectiveness of normal schedules on three dedicated processors
- Branch and bound methods for scheduling problems with multiprocessor tasks on dedicated processors
- 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.
- An approximation algorithm for nonpreemptive scheduling on hypercube parallel task systems
- A graph based model for survivability applications
- An approximation algorithm for scheduling on three dedicated machines
- Shop scheduling problems with multiprocessor tasks on dedicated processors
- Scheduling independent tasks with multiple modes
- Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors
- Processor bounding for an efficient non-preemptive task scheduling algorithm
- Scheduling: agreement graph vs resource constraints
- An approximation result for a duo-processor task scheduling problem
- On minimizing dataset transfer time in an acyclic network with four servers
- Lower bound algorithms for multiprocessor task scheduling with ready times
- scientific article; zbMATH DE number 1472149 (Why is no real title available?)
- scientific article; zbMATH DE number 2086778 (Why is no real title available?)
- Linear algorithms for preemptive scheduling of multiprocessor tasks subject to minimal lateness
- Comparability graph augmentation for some multiprocessor scheduling problems
- Scheduling wagons to unload in bulk cargo ports with uncertain processing times
- Effect of skewing strategies on solving scheduling problems for multiprocessor tasks on two dedicated processors
- Preemptive open shop scheduling with multiprocessors: Polynomial cases and applications
- A simple linear time approximation algorithm for multi-processor job scheduling on four processors
- On the complexity of adjacent resource scheduling
- New perspectives in scheduling theory
This page was built for publication: Scheduling multiprocessor tasks on three dedicated processors
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1197982)
