Complexity of scheduling multiprocessor tasks with prespecified processors allocations
From MaRDI portal
Publication:1343144
DOI10.1016/0166-218X(94)90012-4zbMath0938.68671MaRDI QIDQ1343144
Steef L. van de Velde, Hoogeveen, J. A., Bart Veltman
Publication date: 1 February 1995
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items
Scheduling on parallel machines considering job-machine dependency constraints, Preemptive open shop scheduling with multiprocessors: Polynomial cases and applications, Scheduling: agreement graph vs resource constraints, An approximation algorithm for scheduling on three dedicated machines, Shop scheduling problems with multiprocessor tasks on dedicated processors, Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterion, Efficiency and effectiveness of normal schedules on three 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, A makespan-optimal schedule for processing jobs with possible operation preemptions as an optimal mixed graph coloring, On maximizing the throughput of multiprocessor tasks., On minimizing dataset transfer time in an acyclic network with four servers, Discrete optimization with polynomially detectable boundaries and restricted level sets, A polynomial algorithm for some preemptive multiprocessor task scheduling problems, On spectrum assignment in elastic optical tree-networks, Exploiting incomplete information to manage multiprocessor tasks with variable arrival rates, Scheduling problem with multi-purpose parallel machines, Processor bounding for an efficient non-preemptive task scheduling algorithm, The complexity of path coloring and call scheduling, Minimum sum multicoloring on the edges of trees, Open block scheduling in optical communication networks, Multistage stochastic programming approach for joint optimization of job scheduling and material ordering under endogenous uncertainties, Comparability graph augmentation for some multiprocessor scheduling problems, On Multi-product Lot-Sizing and Scheduling with Multi-machine Technologies, Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems, Scheduling multiprocessor tasks -- An overview, Preemptive versus nonpreemptive scheduling for biprocessor tasks on dedicated processors, 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, Nonpreemptive scheduling of independent tasks with prespecified processor allocations, An approximation algorithm for nonpreemptive scheduling on hypercube parallel task systems, Scheduling multiprocessor tasks on two parallel processors, Minimizing total completion time in multiprocessor job systems with energy constraint
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Multiprocessor scheduling with communication delays
- Scheduling subject to resource constraints: Classification and complexity
- The complexity of scheduling independent two-processor tasks on dedicated processors
- Scheduling multiprocessor tasks on three dedicated processors
- Integer Programming with a Fixed Number of Variables
- Scheduling Multiprocessor Tasks to Minimize Schedule Length
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
