Optimal scheduling for two-processor systems
From MaRDI portal
In Mehrprozessorsystemen spielt die Arbeitsreihenfolge der anstehenden Tasks eine fundamentale Rolle. Der Durchsatz dieser Systeme, bzw. die Zeit für die Fertigstellung einer gegebenen Taskmenge hängt entscheidend davon ab. Die Autoren behandeln Systeme mit zwei identischen Prozessoren. Alle Tasks haben konstante Abarbeitungszeit. Die Taskmenge ist halbgeordnet entsprechend ihren Abhängigkeitsbeziehungen. Unter Berücksichtigung der gegebenen Halbordnung wird eine Abarbeitungsreihenfolge gesucht, die kürzeste Gesamtheit ergibt. Die Taskmenge wird als zyklenfreier gerichteter Graph zugelassen. Damit gehen die Autoren über die bis dahin behandelten hierarchischen Anordnungen hinaus. Es wird ein Algorithmus für die Konstruktion einer optimalen Reihenfolge gegeben. Die Anzahl der Schritte ist von der Ordnung \(N^2\), wenn \(N\) die Anzahl der Tasks ist. Das Ergebnis verbessert auch die bisherigen Möglichkeiten für den hierarchischen Fall, in dem bisher Algorithmen der Ordnung \(N^4\) bekannt sind. Durch Zeitquantelung lassen sich Aufgaben behandeln, in denen die Abarbeitungszeit der einzelnen Tasks unterschiedlich ist. Mit einigen Einschränkungen lassen sich die Resultate auf Systeme mit mehr als zwei Prozessoren ausdehnen.
Cites work
- Bounds for Certain Multiprocessing Anomalies
- Bounds on Multiprocessing Timing Anomalies
- Erratum “Optimal Sequencing of Two Equivalent Processors”
- Flow Networks and Combinatorial Operations Research
- Optimal Preemptive Scheduling on Two-Processor Systems
- Optimal Sequencing of Two Equivalent Processors
- Paths, Trees, and Flowers
Cited in
(only showing first 100 items - show all)- Optimality of HLF for scheduling divide-and-conquer UET task graphs on identical parallel processors
- Minimizing the number of machines for minimum length schedules
- Applications of scheduling theory to formal language theory
- UET scheduling with unit interprocessor communication delays
- Multiprocessor scheduling with interprocessor communication delays
- Computing the bump number with techniques from two-processor scheduling
- Scheduling tree-structured tasks with restricted execution times
- Worst-case analysis of heuristics for the local microcode optimization problem
- Complexity results for scheduling chains on a single machine
- Coffman-Graham scheduling of UET task systems with 0-1 resources
- Task splitting for three machine preemptive scheduling
- NP-complete scheduling problems
- A note on optimal scheduling for two-processor systems
- Optimal scheduling of homogeneous job systems
- A graph model for scheduling processes in systems with parallel computations
- A note on optimal preemptive scheduling for two-processor systems
- Antwortzeitgesteuerte Prozessorzuteilung unter strengen Zeitbedingungen
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- Bounds on list scheduling of UET tasks with restricted resource constraints
- Methods for task allocation via agent coalition formation
- The complexity of a cyclic scheduling problem with identical machines and precedence constraints
- Scheduling multiprocessor tasks with chain constraints
- List schedules for cyclic scheduling
- Optimal scheduling on parallel machines for a new order class
- Optimal multiprocessor task scheduling using dominance and equivalence relations
- A state-space search approach for parallel processor scheduling problems with arbitrary precedence relations
- Multi-processor scheduling and expanders
- On two-processor scheduling and maximum matching in permutation graphs
- Performance of Coffman-Graham schedules in the presence of unit communication delays
- Planar stage graphs: Characterizations and applications
- Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity
- Scheduling loosely connected task graphs.
- Width-restricted layering of acyclic digraphs with consideration of dummy nodes
- A survey on how the structure of precedence constraints may change the complexity class of scheduling problems
- Scheduling chained multiprocessor tasks onto large multiprocessor system
- Normal-form preemption sequences for an open problem in scheduling theory
- A flow formulation for horizontal coordinate assignment with prescribed width
- Preemptive scheduling with variable profile, precedence constraints and due dates
- Scheduling of resource tasks
- A standard task graph set for fair evaluation of multiprocessor scheduling algorithms
- Lower bounds on precedence-constrained scheduling for parallel processors.
- Algorithms for dynamic scheduling of unit execution time tasks
- An efficient deterministic parallel algorithm for two processors precedence constraint scheduling
- Controlling the data space of tree structured computations
- Generating and characterizing the perfect elimination orderings of a chordal graph
- Scheduling tasks with communication delays on parallel processors
- Processor bounding for an efficient non-preemptive task scheduling algorithm
- Ideal schedules in parallel machine settings
- Approximation algorithms for bicriteria scheduling problems on identical parallel machines for makespan and total completion time
- Four decades of research on the open-shop scheduling problem to minimize the makespan
- Polyhedral results for position-based scheduling of chains on a single machine
- Minimizing total completion time for UET tasks with release time and outtree precedence constraints
- Vyacheslav Tanaev: contributions to scheduling and related areas
- Scheduling trees with large communication delays on two identical processors
- Timing analysis of the flexRay communication protocol
- Benchmark-problem instances for static scheduling of task graphs with communication delays on homogeneous multiprocessor systems
- Graph layering by promotion of nodes
- Single machine scheduling subject to precedence delays
- Non-preemptive profile scheduling and quasi-interval orders
- A note on scheduling multiprocessor tasks with precedence constraints on parallel processors
- On the Scalability of Constraint Solving for Static/Off-Line Real-Time Scheduling
- Compact layered drawings of general directed graphs
- Scheduling multiprocessor tasks on two parallel processors
- Bounds on the performance of a heuristic to schedule precedence-related jobs on parallel machines
- Static scheduling of directed acyclic data flow graphs onto multiprocessors using particle swarm optimization
- Benchmarking the clustering algorithms for multiprocessor environments using dynamic priority of modules
- Optimal scheduling of unit-time tasks on two uniform processors under tree-like precedence constraints
- A new polynomial algorithm for a parallel identical scheduling problem
- Cyclic Leveling of Directed Graphs
- Profile Scheduling of Opposing Forests and Level Orders
- scientific article; zbMATH DE number 3970497 (Why is no real title available?)
- Scheduling Tree-Structured Tasks on Two Processors to Minimize Schedule Length
- Inhomogeneous graph sorting and job distribution between two processors
- Open shop problems with unit time operations
- A two-stage hardware scheduler combining greedy and optimal scheduling
- Optimal shooting: Characterizations and applications
- Scheduling Opposing Forests
- Parallel Machine Scheduling with Uncertain Communication Delays
- AN EFFECTIVE APPROACH FOR DISTRIBUTED PROGRAM ALLOCATION
- ON CONSIDERING COMMUNICATION IN SCHEDULING TASK GRAPHS ON PARALLEL PROCESSORS
- A PARALLEL SCHEDULING ALGORITHM FOR PARALLEL APPLICATIONS
- ON OPTIMAL LOOP UNROLLING IN TWO-PROCESSOR SCHEDULING
- SCHEDULING INTERVAL ORDERS IN PARALLEL
- Efficient maximum matching algorithms for trapezoid graphs
- A flow formulation for horizontal coordinate assignment with prescribed width
- Parallel maximum matching algorithms in interval graphs
- Cooperativead hoccomputing: towards enabling cooperative processing in wireless environments
- Drawing Graphs with GLEE
- PREEMPTIVE SCHEDULING ON PARALLEL PROCESSORS WITH DUE DATES
- On scheduling with the non-idling constraint
- On scheduling with the non-idling constraint
- PARAdeg-processor scheduling for acyclic SWITCH-less program nets
- An approximation algorithm for scheduling dependent tasks on m processors with small communication delays
- New applications of the Muntz and Coffman algorithm
- Performance of critical path type algorithms for scheduling on parallel processors
- `Strong'-`weak' precedence in scheduling: extensions to series-parallel orders
- Speeding-up parallel computation of large smooth-degree isogeny using precedence-constrained scheduling
- An efficient parallel algorithm for scheduling interval ordered tasks
- Resource leveling: complexity of a unit execution time two-processor scheduling variant and related problems
- Streaming algorithms for scheduling jobs with priorities
This page was built for publication: Optimal scheduling for two-processor systems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2556224)
