Optimal scheduling for two-processor systems

DOI10.1007/BF00288685zbMath0248.68023DBLPjournals/acta/CoffmanG72OpenAlexW2092333800WikidataQ63353538 ScholiaQ63353538MaRDI QIDQ2556224

Ronald L. Graham, Edward G. jun. Coffman

Publication date: 1971

Published in: Acta Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf00288685

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)

Related Items (only showing first 100 items - show all)

Speeding-up parallel computation of large smooth-degree isogeny using precedence-constrained scheduling ⋮ New applications of the Muntz and Coffman algorithm ⋮ Performance of critical path type algorithms for scheduling on parallel processors ⋮ Profile Scheduling of Opposing Forests and Level Orders ⋮ A survey on how the structure of precedence constraints may change the complexity class of scheduling problems ⋮ Controlling the data space of tree structured computations ⋮ Applications of scheduling theory to formal language theory ⋮ A state-space search approach for parallel processor scheduling problems with arbitrary precedence relations ⋮ A note on scheduling multiprocessor tasks with precedence constraints on parallel processors ⋮ Multi-processor scheduling and expanders ⋮ Generating and characterizing the perfect elimination orderings of a chordal graph ⋮ UET scheduling with unit interprocessor communication delays ⋮ On two-processor scheduling and maximum matching in permutation graphs ⋮ Parallel Machine Scheduling with Uncertain Communication Delays ⋮ Multiprocessor scheduling with interprocessor communication delays ⋮ Static scheduling of directed acyclic data flow graphs onto multiprocessors using particle swarm optimization ⋮ Scheduling tasks with communication delays on parallel processors ⋮ Computing the bump number with techniques from two-processor scheduling ⋮ 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 ⋮ Optimal scheduling of unit-time tasks on two uniform processors under tree-like precedence constraints ⋮ Benchmarking the clustering algorithms for multiprocessor environments using dynamic priority of modules ⋮ Scheduling tree-structured tasks with restricted execution times ⋮ Unnamed Item ⋮ Worst-case analysis of heuristics for the local microcode optimization problem ⋮ `Strong'-`weak' precedence in scheduling: extensions to series-parallel orders ⋮ Performance of Coffman-Graham schedules in the presence of unit communication delays ⋮ On the Scalability of Constraint Solving for Static/Off-Line Real-Time Scheduling ⋮ Planar stage graphs: Characterizations and applications ⋮ Open shop problems with unit time operations ⋮ Complexity results for scheduling chains on a single machine ⋮ Identical parallel machines vs. unit-time shops and preemptions vs. chains in scheduling complexity ⋮ Scheduling loosely connected task graphs. ⋮ Compact Layered Drawings of General Directed Graphs ⋮ Coffman-Graham scheduling of UET task systems with 0-1 resources ⋮ Scheduling chained multiprocessor tasks onto large multiprocessor system ⋮ Normal-form preemption sequences for an open problem in scheduling theory ⋮ A new polynomial algorithm for a parallel identical scheduling problem ⋮ Minimizing total completion time for UET tasks with release time and outtree precedence constraints ⋮ Vyacheslav Tanaev: contributions to scheduling and related areas ⋮ A state-of-the-art review of parallel-machine scheduling research ⋮ An efficient parallel algorithm for scheduling interval ordered tasks ⋮ A flow formulation for horizontal coordinate assignment with prescribed width ⋮ Task splitting for three machine preemptive scheduling ⋮ Online scheduling of equal-processing-time task systems ⋮ On scheduling with the non-idling constraint ⋮ Scheduling trees with large communication delays on two identical processors ⋮ Four decades of research on the open-shop scheduling problem to minimize the makespan ⋮ Optimal shooting: Characterizations and applications ⋮ PREEMPTIVE SCHEDULING ON PARALLEL PROCESSORS WITH DUE DATES ⋮ Precedence constrained scheduling in \((2-\frac{7}{3p+1})\) optimal ⋮ PARAdeg-processor scheduling for acyclic SWITCH-less program nets ⋮ An approximation algorithm for scheduling dependent tasks on \(m\) processors with small communication delays ⋮ Timing analysis of the flexRay communication protocol ⋮ Bounds on the performance of a heuristic to schedule precedence-related jobs on parallel machines ⋮ On scheduling with the non-idling constraint ⋮ Processor bounding for an efficient non-preemptive task scheduling algorithm ⋮ Minimizing makespan for a bipartite graph on a single processor with an integer precedence delay. ⋮ Benchmark-problem instances for static scheduling of task graphs with communication delays on homogeneous multiprocessor systems ⋮ Graph layering by promotion of nodes ⋮ Scheduling two-machine no-wait open shops to minimize makespan ⋮ NP-complete scheduling problems ⋮ A note on optimal scheduling for two-processor systems ⋮ A best possible online algorithm for scheduling equal-length jobs on two machines with chain precedence constraints ⋮ Optimal scheduling of homogeneous job systems ⋮ Online scheduling with chain precedence constraints of equal-length jobs on parallel machines to minimize makespan ⋮ A graph model for scheduling processes in systems with parallel computations ⋮ Ideal schedules in parallel machine settings ⋮ 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 ⋮ Cyclic Leveling of Directed Graphs ⋮ Cooperativead hoccomputing: towards enabling cooperative processing in wireless environments ⋮ Drawing Graphs with GLEE ⋮ Polyhedral results for position-based scheduling of chains on a single machine ⋮ Preemptive scheduling with variable profile, precedence constraints and due dates ⋮ Bounds on list scheduling of UET tasks with restricted resource constraints ⋮ Optimality of HLF for scheduling divide-and-conquer UET task graphs on identical parallel processors ⋮ Scheduling of resource tasks ⋮ Inhomogeneous graph sorting and job distribution between two processors ⋮ 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 ⋮ A Flow Formulation for Horizontal Coordinate Assignment with Prescribed Width ⋮ An efficient algorithm for finding ideal schedules ⋮ Minimizing the number of machines for minimum length schedules ⋮ Single machine scheduling subject to precedence delays ⋮ List schedules for cyclic scheduling ⋮ PARALLEL MAXIMUM MATCHING ALGORITHMS IN INTERVAL GRAPHS ⋮ Scheduling Opposing Forests ⋮ Efficient maximum matching algorithms for trapezoid graphs ⋮ A standard task graph set for fair evaluation of multiprocessor scheduling algorithms ⋮ Optimal scheduling on parallel machines for a new order class ⋮ Approximation algorithms for bicriteria scheduling problems on identical parallel machines for makespan and total completion time ⋮ Lower bounds on precedence-constrained scheduling for parallel processors. ⋮ Width-restricted layering of acyclic digraphs with consideration of dummy nodes ⋮ Optimal multiprocessor task scheduling using dominance and equivalence relations

Cites Work

This page was built for publication: Optimal scheduling for two-processor systems