Displaying similar documents to “Parallel machine scheduling with uncertain communication delays”

Parallel Machine Scheduling with Uncertain Communication Delays

Aziz Moukrim, Eric Sanlaville, Frédéric Guinand (2010)

RAIRO - Operations Research

Similarity:

This paper is concerned with scheduling when the data are not fully known before the execution. In that case computing a complete schedule off-line with estimated data may lead to poor performances. Some flexibility must be added to the scheduling process. We propose to start from a partial schedule and to postpone the complete scheduling until execution, thus introducing what we call a stabilization scheme. This is applied to the m machine problem with communication delays: in our...

Scheduling UET Trees with Communication Delays on two Processors

Frederic Guinand, Denis Trystman (2010)

RAIRO - Operations Research

Similarity:

In this paper, we present a new linear time algorithm for scheduling UECT (Unit Execution and Communication Time) trees on two identical processors. The chosen criterion is the makespan. The used strategy is based on clustering of tasks. We show that this algorithm builds optimal schedules. Some extensions are discussed for non UECT tasks.

Scheduling Precedence Task Graphs with Disturbances

Apurv Gupta, Gilles Parmentier, Denis Trystram (2010)

RAIRO - Operations Research

Similarity:

In this paper we consider the problem of scheduling precedence task graphs in parallel processing where there can be disturbances in computation and communication times. Such a phenomenon often occurs in practice, due to our inability to exactly predict the time because of system intrusion like cache miss and packet transmission time in mediums like ethernet etc. We propose a method based on the addition of some extra edges to protect the initial scheduling from performing badly...

Scheduling an interval ordered precedence graph with communication delays and a limited number of processors

Alix Munier Kordon, Fadi Kacem, Benoît Dupont de Dinechin, Lucian Finta (2013)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

We consider the scheduling of an interval order precedence graph of unit execution time tasks with communication delays, release dates and deadlines. Tasks must be executed by a set of processors partitioned into classes; each task requires one processor from a fixed class. The aim of this paper is to study the extension of the Leung–Palem–Pnueli (in short LPP) algorithm to this problem. The main result is to prove that the LPP algorithm can be extended to dedicated processors and monotone...

Scheduling precedence task graphs with disturbances

Apurv Gupta, Gilles Parmentier, Denis Trystram (2003)

RAIRO - Operations Research - Recherche Opérationnelle

Similarity:

In this paper we consider the problem of scheduling precedence task graphs in parallel processing where there can be disturbances in computation and communication times. Such a phenomenon often occurs in practice, due to our inability to exactly predict the time because of system intrusion like cache miss and packet transmission time in mediums like ethernet etc. We propose a method based on the addition of some extra edges to protect the initial scheduling from performing badly due...

Parallel dynamic programming algorithms: Multitransputer systems

Jan Sadecki (2002)

International Journal of Applied Mathematics and Computer Science

Similarity:

The present paper discusses real parallel computations. On the basis of a selected group of dynamic programming algorithms, a number of factors affecting the efficiency of parallel computations such as, e.g., the way of distributing tasks, the interconnection structure between particular elements of the parallel system or the way of organizing of interprocessor communication are analyzed. Computations were implemented in the parallel multitransputer SUPER NODE 1000 system using from...