C.P.M. Scheduling with Small Communication Delays and Task Duplication

J. Y. Colin
J. Y. Colin
Office National d'Etudes et de Recherches Aerospatiales, Châtillon, France
Search for more papers by this author
,
P. Chrétienne
P. Chrétienne
Université Pierre et Marie Curie, Paris, France
Search for more papers by this author

J. Y. Colin

Office National d'Etudes et de Recherches Aerospatiales, Châtillon, France

Search for more papers by this author

P. Chrétienne

Université Pierre et Marie Curie, Paris, France

Search for more papers by this author

Published Online:1 Aug 1991https://doi.org/10.1287/opre.39.4.680

Abstract

This paper addresses a machine scheduling problem that arises in the case of scheduling tasks over an idealized distributed multiprocessor. Precedence constraints with small communication delays have to be taken into account and task duplication is allowed. A critical path-like algorithm is presented, which is shown to construct an optimal schedule in polynomial time.

Cited by
- Toward resilient green cloud computing: Joint operations of energy storage and spatial task allocation
  Omega, Vol. 142
- Scheduling jobs with shared additional operations on parallel identical machines
  Computers & Operations Research, Vol. 170
- Scheduling with Communication Delays via LP Hierarchies and Clustering
- Parallel machine scheduling with job synchronization to enable efficient material flows in hub terminals
  Omega, Vol. 89
- EATSDCD: A green energy-aware scheduling algorithm for parallel task-based application using clustering, duplication and DVFS technique in cloud datacenters
  17 May 2019 | Journal of Intelligent & Fuzzy Systems, Vol. 36, No. 6
- Adapting MCP and HLFET Algorithms to Multiple Simultaneous Scheduling
  3 July 2017 | International Journal of Parallel Programming, Vol. 46, No. 3
- Comparing Three Clustering-based Scheduling Methods for Energy-Aware Rapid Design of MP2SoCs
  14 August 2017 | Journal of Signal Processing Systems, Vol. 90, No. 4
- Solving the P/Prec, p j ,C ij /C max Using an Evolutionary Algorithm
  19 September 2017
- DyDupSA - Dynamic Task Duplication Based Scheduling Algorithm for Multiprocessor System
- PCP-B2 : Partial critical path budget balanced scheduling algorithms for scientific workflow applications
  Future Generation Computer Systems, Vol. 60
- Turnaround Time Minimization-Based Static Scheduling Model Using Task Duplication for Fine-Grained Parallel Applications onto Hybrid Cloud Environment
  19 August 2015 | IETE Journal of Research, Vol. 62, No. 3
- Cost-aware DAG scheduling algorithms for minimizing execution cost on cloud resources
  25 January 2016 | The Journal of Supercomputing, Vol. 72, No. 3
- A Randomized Scheduling Algorithm for Multiprocessor Environments Using Local Search
  27 March 2016 | Parallel Processing Letters, Vol. 26, No. 01
- A Novel ACO-Based Static Task Scheduling Approach for Multiprocessor Environments
  1 January 2016 | International Journal of Computational Intelligence Systems, Vol. 9, No. 5
- A new hardware/software partitioning technique
- Benchmarking the clustering algorithms for multiprocessor environments using dynamic priority of modules
  Applied Mathematical Modelling, Vol. 36, No. 12
- Optimizing latency and throughput of application workflows on clusters
  Parallel Computing, Vol. 37, No. 10-11
- Scheduling Tasks and Communications on a Hierarchical System with Message Contention
- ACO-MTS: A new approach for multiprocessor task scheduling based on ant colony optimization
- Area failures and reliable distributed applications
- A Novel Bicriteria Scheduling Heuristics Providing a Guaranteed Global System Failure Rate
  IEEE Transactions on Dependable and Secure Computing, Vol. 6, No. 4
- Compaction of Schedules and a Two-Stage Approach for Duplication-Based DAG Scheduling
  IEEE Transactions on Parallel and Distributed Systems, Vol. 20, No. 6
- Resource allocation algorithm for light communication grid-based workflows within an SLA context
  International Journal of Parallel, Emergent and Distributed Systems, Vol. 24, No. 1
- Dynamic Load Balancing and Job Replication in a Global-Scale Grid Environment: A Comparison
  IEEE Transactions on Parallel and Distributed Systems, Vol. 20, No. 2
- Scheduling with Communication Delays
  5 June 2009
- Optimizing Message Passing Programs Based on Task Section Duplication
- Task scheduling algorithm using minimized duplications in homogeneous systems
  Journal of Parallel and Distributed Computing, Vol. 68, No. 8
- Mapping Heavy Communication Grid-Based Workflows Onto Grid Resources Within an SLA Context Using Metaheuristics
  1 August 2008 | The International Journal of High Performance Computing Applications, Vol. 22, No. 3
- Task scheduling in multiprocessing systems using duplication
  Journal of Systems Architecture, Vol. 54, No. 5
- An efficient fault-tolerant scheduling algorithm for precedence constrained tasks in heterogeneous distributed systems
- Communication Delays and Multiprocessor Tasks
- Two Post-Scheduling Optimization Algorithms for Distributed Real-Time Tasks Based on Scheduled Cluster Tree
- Iterative list scheduling for heterogeneous computing
  Journal of Parallel and Distributed Computing, Vol. 65, No. 5
- Joint application mapping/interconnect synthesis techniques for embedded chip-scale multiprocessors
  IEEE Transactions on Parallel and Distributed Systems, Vol. 16, No. 2
- Operations research methods for resource management and scheduling in a computational grid: a survey
- Toward an analytical solution to task allocation, processor assignment, and performance evaluation of network processors
  Journal of Parallel and Distributed Computing, Vol. 65, No. 1
- Efficient Task Scheduling with Duplication for Bounded Number of Processors
- Improving scheduling of tasks in a heterogeneous environment
  IEEE Transactions on Parallel and Distributed Systems, Vol. 15, No. 2
- An efficient scheduling algorithm for dependent tasks
- General Non-Approximability Results in Presence of Hierarchical Communications
- A Cluster-based Strategy for Scheduling Task on Heterogeneous Processors
- On approximation of the bulk synchronous task scheduling problem
  IEEE Transactions on Parallel and Distributed Systems, Vol. 14, No. 11
- A task duplication scheme for resolving deadlocks in clustered DAGs
  Parallel Computing, Vol. 29, No. 6
- An improved duplication strategy for scheduling precedence constrained graphs in multiprocessor systems
  IEEE Transactions on Parallel and Distributed Systems, Vol. 14, No. 6
- Towards Optimal Static Task Scheduling for Realistic Machine Models: Theory and Practice
  1 May 2003 | The International Journal of High Performance Computing Applications, Vol. 17, No. 2
- Hybrid task scheduling: integrating static and dynamic heuristics
- A greedy clustering and scheduling algorithm
- Task clustering and scheduling to multiprocessors with duplication
- Minimizing the volume in scheduling an out-tree with communication delays and duplication
  Parallel Computing, Vol. 28, No. 11
- An optimal scheduling algorithm based on task duplication
  IEEE Transactions on Computers, Vol. 51, No. 4
- Optimal Task Scheduling of a Complete K-Ary Tree with Communication Delays
  6 June 2002
- Cluster-based static scheduling: theory and practice
- A task duplication based scheduling algorithm with optimality condition in heterogeneous systems
- ON MESSAGE PACKAGING IN TASK SCHEDULING FOR DISTRIBUTED MEMORY PARALLEL MACHINES
  20 November 2011 | International Journal of Foundations of Computer Science, Vol. 12, No. 03
- A Duplication Based Compile Time Scheduling Method for Task Parallelism
  18 May 2001
- Communication Delays and Multiprocessor Tasks
- An optimal scheduling algorithm based on task duplication
- Using duplication for the multiprocessor scheduling problem with hierarchical communications
  30 April 2012 | Parallel Processing Letters, Vol. 10, No. 01
- Management of Resources in Parallel Systems
- Task allocation on a network of processors
  IEEE Transactions on Computers, Vol. 49, No. 12
- A scalable task duplication based scheduling algorithm for heterogeneous systems
- A task duplication based scheduling algorithm for heterogeneous systems
- Benchmarking and Comparison of the Task Graph Scheduling Algorithms
  Journal of Parallel and Distributed Computing, Vol. 59, No. 3
- Static scheduling algorithms for allocating directed task graphs to multiprocessors
  1 December 1999 | ACM Computing Surveys, Vol. 31, No. 4
- Optimal Scheduling for UET/UET-UCT Generalizedn-Dimensional Grid Task Graphs
  Journal of Parallel and Distributed Computing, Vol. 57, No. 2
- On parallelizing the multiprocessor scheduling problem
  IEEE Transactions on Parallel and Distributed Systems, Vol. 10, No. 4
- Scheduling inverse trees under the communication model of the LogP-machine
  Theoretical Computer Science, Vol. 215, No. 1-2
- Using duplication for the multiprocessor scheduling problem with hierarchical communications
  6 August 1999
- Post-Scheduling Optimization of Parallel Programs
  6 August 1999
- Approximation algorithms for scheduling trees with general communication delays
  Parallel Computing, Vol. 25, No. 1
- Scheduling tasks with communication delays on a two-levels virtual distributed system
- Optimal scheduling for UET-UCT grids into fixed number of processors
- Automatic Methods for Hiding Latency in Parallel and Distributed Computation
  SIAM Journal on Computing, Vol. 29, No. 2
- A Robust Compile Time Method for Scheduling Task Parallelism on Distributed Memory Machines
  The Journal of Supercomputing, Vol. 12, No. 4
- The Multiprocessor Scheduling of Precedence-Constrained Task Systems in the Presence of Interprocessor Communication Delays
  Sanjoy K. Baruah,
  1 February 1998 | Operations Research, Vol. 46, No. 1
- A Review of Machine Scheduling: Complexity, Algorithms and Approximability
- An efficient strategy for task duplication in multiport message-passing systems
  30 June 2006
- Optimal scheduling algorithm for distributed-memory machines
  IEEE Transactions on Parallel and Distributed Systems, Vol. 9, No. 1
- On exploiting task duplication in parallel program scheduling
  IEEE Transactions on Parallel and Distributed Systems, Vol. 9, No. 9
- Mapping of parallel tasks to multiprocessors with duplication
- Benchmarking the task graph scheduling algorithms
- A Task Duplication Based Scalable Scheduling Algorithm for Distributed Memory Systems
  Journal of Parallel and Distributed Computing, Vol. 46, No. 1
- Scheduling Problems in a Practical Allocation Model
  Journal of Combinatorial Optimization, Vol. 1, No. 2
- Using duplication for scheduling unitary tasks on m processors with unit communication delays
  Theoretical Computer Science, Vol. 178, No. 1-2
- Comparative study of static scheduling with task duplication for distributed systems
  8 June 2005
- Some models for scheduling parallel programs with communication delays
  Discrete Applied Mathematics, Vol. 72, No. 1-2
- Decisive path scheduling: a new list scheduling method
- Optimal scheduling for UET-UCT generalized n-dimensional grid task graphs
- DFRN: a new approach for duplication based scheduling for distributed memory multiprocessor systems
- Scheduling multiprocessor tasks — An overview
  European Journal of Operational Research, Vol. 94, No. 2
- Scheduling tasks and communications on a virtual distributed system
  European Journal of Operational Research, Vol. 94, No. 2
- Optimal schedules for d-D grid graphs with communication delays
  7 June 2005
- Communication Delays and Multiprocessor Tasks
- Bounds and algorithms for a practical task allocation model (extended abstract)
  11 October 2005
- Analysis, evaluation, and comparison of algorithms for scheduling task graphs on parallel processors
- Scalable scheduling algorithm for distributed memory machines
- New complexity results on scheduling with small communication delays
  Discrete Applied Mathematics, Vol. 60, No. 1-3
- Three, four, five, six, or the complexity of scheduling with communication delays
  Operations Research Letters, Vol. 16, No. 3
- A Task Duplication Based Optimal Scheduling Algorithm for Variable Execution Time Tasks
- DSC: scheduling parallel tasks on an unbounded number of processors
  IEEE Transactions on Parallel and Distributed Systems, Vol. 5, No. 9
- SDBS: a task duplication based optimal scheduling algorithm

Volume 39, Issue 4

July-August 1991

Pages 528-687

Article Information

Metrics

Information

Published Online:August 01, 1991

Cite as

J. Y. Colin, P. Chrétienne, (1991) C.P.M. Scheduling with Small Communication Delays and Task Duplication. Operations Research 39(4):680-684.

https://doi.org/10.1287/opre.39.4.680

Keywords

PDF download

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

Available Issues

C.P.M. Scheduling with Small Communication Delays and Task Duplication

Abstract

Volume 39, Issue 4

Article Information

Metrics

Information

Cite as

Keywords

Sign Up for INFORMS Publications Updates and News