Displaying 1101 – 1120 of 1566

Showing per page

Parallel approximation to high multiplicity scheduling problems V I A smooth multi-valued quadratic programming

Maria Serna, Fatos Xhafa (2008)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

We consider the parallel approximability of two problems arising from high multiplicity scheduling, namely the unweighted model with variable processing requirements and the weighted model with identical processing requirements. These two problems are known to be modelled by a class of quadratic programs that are efficiently solvable in polynomial time. On the parallel setting, both problems are P-complete and hence cannot be efficiently solved in parallel unless P = NC. To deal with the parallel...

Parallel approximation to high multiplicity scheduling problems VIA smooth multi-valued quadratic programming

Maria Serna, Fatos Xhafa (2007)

RAIRO - Theoretical Informatics and Applications

We consider the parallel approximability of two problems arising from high multiplicity scheduling, namely the unweighted model with variable processing requirements and the weighted model with identical processing requirements. These two problems are known to be modelled by a class of quadratic programs that are efficiently solvable in polynomial time. On the parallel setting, both problems are P-complete and hence cannot be efficiently solved in parallel unless P = NC. To deal with the parallel...

Parallel machine scheduling with uncertain communication delays

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

RAIRO - Operations Research - Recherche Opérationnelle

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

Parallel Machine Scheduling with Uncertain Communication Delays

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

RAIRO - Operations Research

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

Parallélisation d'une Combinaison des Méthodes de Monte-Carlo et Quasi-Monte-Carlo et Application aux Réseaux de Files d'Attente

Bruno Tuffin, Louis-Marie Le Ny (2010)

RAIRO - Operations Research

We propose a parallel algorithm which uses both Monte-Carlo and quasi-Monte-Carlo methods. A detailed analysis of this algorithm, followed by examples, shows that the estimator's efficiency is a linear function of the processor number. As a concrete application example, we evaluate performance measures of a multi-class queueing network in steady state.

Currently displaying 1101 – 1120 of 1566