Displaying similar documents to “Scheduling an interval ordered precedence graph with communication delays and a limited number of processors”

Une méthode tabou pour l'ordonnancement multiprocesseur avec délais de communication

Dalila Tayachi, Philippe Chrétienne, Khaled Mellouli (2010)

RAIRO - Operations Research

Similarity:

This paper deals with the problem of scheduling tasks on identical processors in the presence of communication delays. A new approach of modelisation by a decision graph and a resolution by a tabu search method is proposed. Initial solutions are constructed by list algorithms, and then improved by a tabu algorithm operating in two phases. The experiments carried on arbitrary graphs show the efficiency of our method and that it outperformed the principle existent heuristics. ...

Parallel machine scheduling with uncertain communication delays

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

RAIRO - Operations Research - Recherche Opérationnelle

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 model...

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.

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 in the presence of processor networks : complexity and approximation

Vincent Boudet, Johanne Cohen, Rodolphe Giroudeau, Jean-Claude König (2012)

RAIRO - Operations Research

Similarity:

In this paper, we study the problem of makespan minimization for the multiprocessor scheduling problem in the presence of communication delays. The communication delay between two tasks and depends on the distance between the two processors on which these two tasks are executed. Lahlou shows that a simple polynomial-time algorithm exists when the length of the schedule is at most two (the problem becomes 𝒩𝒫-complete when the length...

Scheduling in the presence of processor networks : complexity and approximation

Vincent Boudet, Johanne Cohen, Rodolphe Giroudeau, Jean-Claude König (2012)

RAIRO - Operations Research

Similarity:

In this paper, we study the problem of makespan minimization for the multiprocessor scheduling problem in the presence of communication delays. The communication delay between two tasks and depends on the distance between the two processors on which these two tasks are executed. Lahlou shows that a simple polynomial-time algorithm exists when the length of the schedule is at most two (the problem becomes 𝒩𝒫-complete when the length...

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...

Construction of Very Hard Functions for Multiparty Communication Complexity

Ján Maňuch (2010)

RAIRO - Theoretical Informatics and Applications

Similarity:

We consider the multiparty communication model defined in [4] using the formalism from [8]. First, we correct an inaccuracy in the proof of the fundamental result of [6] providing a lower bound on the nondeterministic communication complexity of a function. Then we construct several very hard functions, , functions such that those as well as their complements have the worst possible nondeterministic communication complexity. The problem to find a particular very hard function...