Complexity of Scheduling Parallel Task Systems

DOI10.1137/0402042zbMath0676.90029OpenAlexW2057913648MaRDI QIDQ3832306

Publication date: 1989

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0402042

zbMATH Keywords

parallel algorithms strongly NP-hard nonpreemptive scheduling pseudo-polynomial time schedule length Parallel Task System

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Deterministic scheduling theory in operations research (90B35) Theory of operating systems (68N25)

Related Items

Complexity of scheduling tasks with time-dependent execution times, Preemptive open shop scheduling with multiprocessors: Polynomial cases and applications, Maximizing the throughput of parallel jobs on hypercubes, Real-time scheduling of linear speedup parallel tasks, Speed scaling scheduling of multiprocessor jobs with energy constraint and makespan criterion, Efficiency and effectiveness of normal schedules on three dedicated processors, Scheduling multiprocessor tasks on a dynamic configuration of dedicated processors, Distributed processing of divisible jobs with communication startup costs, Models and complexity of multibin packing problems, A constant-factor approximation for generalized malleable scheduling under \(M^\natural \)-concave processing speeds, On-line scheduling mesh jobs with dependencies, Deadline scheduling of multiprocessor tasks, A genetic algorithm for hybrid flow-shop scheduling with multiprocessor tasks, On the complexity of adjacent resource scheduling, Scheduling parallel jobs to minimize the makespan, On-line scheduling of parallel jobs, Improved upper bounds for online malleable job scheduling, Online multiple-strip packing, Malleable scheduling beyond identical machines, An improved approximation algorithm for scheduling monotonic moldable tasks, Heuristic algorithms for multiprocessor task scheduling in a two-stage hybrid flow-shop., Scheduling malleable tasks with precedence constraints, Optimal workforce assignment to operations of a paced assembly line, Approximation algorithms for scheduling monotonic moldable tasks on multiple platforms, On the complexity of scheduling problems with a fixed number of parallel identical machines, Unnamed Item, Hybrid flow-shop scheduling problems with multiprocessor task systems., A note on scheduling multiprocessor tasks with identical processing times., Scheduling and packing malleable and parallel tasks with precedence constraints of bounded width, Scheduling parallel jobs using migration and consolidation in the cloud, Competitive online scheduling of perfectly malleable jobs with setup times, On-line scheduling of parallel jobs in a list, Scheduling multiprocessor tasks on three dedicated processors, APPROXIMATION ALGORITHMS FOR SCHEDULING MALLEABLE TASKS UNDER PRECEDENCE CONSTRAINTS, Complexity and inapproximability results for parallel task scheduling and strip packing, A \(\frac 54\)-approximation algorithm for scheduling identical malleable tasks, On-line scheduling of parallel jobs with runtime restrictions, Linear algorithms for preemptive scheduling of multiprocessor tasks subject to minimal lateness, Bounding the Running Time of Algorithms for Scheduling and Packing Problems, Preemptive scheduling of multiprocessor tasks on the dedicated processor system subject to minimal lateness, List scheduling of parallel tasks, A note on online strip packing, Scheduling multiprocessor tasks -- An overview, Scheduling multiprocessor tasks with chain constraints, Online scheduling of parallelizable jobs in the directed acyclic graphs and speed-up curves models, Fairness in parallel job scheduling, Linear and quadratic algorithms for scheduling chains and opposite chains, An approximation algorithm for nonpreemptive scheduling on hypercube parallel task systems, Scheduling multiprocessor tasks on two parallel processors