InforLorV4, PascalFrancis, Corpus, bibRecord, 000118

SCHEDULING IN THE PRESENCE OF PROCESSOR NETWORKS: COMPLEXITY AND APPROXIMATION

Identifieur interne : 000118 ( PascalFrancis/Corpus ); précédent : 000117; suivant : 000119

SCHEDULING IN THE PRESENCE OF PROCESSOR NETWORKS: COMPLEXITY AND APPROXIMATION

Auteurs : Vincent Boudht ; Johanne Cohhn ; Rodolphe Giroudeau ; Jean-Clalide Könic

Source :

RAIRO. Recherche opérationnelle [ 0399-0559 ] ; 2012.

RBID : Pascal:12-0251183

Descripteurs français

Pascal (Inist)
- Temps total achèvement, Minimisation, Temps polynomial, Problème NP complet, Topologie circuit, Système réparti, Anneau, Graphe précédence, Contrainte précédence, Graphe biparti, Multiprocesseur, Algorithme approximation, Délai transmission, Modélisation, ., Ordonnancement processeur.

English descriptors

KwdEn :
- Approximation algorithm, Bipartite graph, Distributed system, Makespan, Minimization, Modeling, Multiprocessor, NP complete problem, Network topology, Polynomial time, Precedence constraint, Precedence graph, Processor scheduling, Ring, Transmission time.

Abstract

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 i and j 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 NP-complete when the length of the schedule is at most three). We prove that there is no polynomial-time algorithm with a performance guarantee of less than 4/3 (unless P = NP) to minimize the makespan when the network topology is a chain or ring and the precedence graph is a bipartite graph of depth one. We also develop two polynomial-time approximation algorithms with constant ratio dedicated to cases where the processor network admits a limited or unlimited number of processors.

Notice en format standard (ISO 2709)

Pour connaître la documentation sur le format Inist Standard.

A01	`01`	`1`		`@0 0399-0559`
A02	`01`			`@0 RSROD3`
A03		`1`		`@0 RAIRO, Rech. opér.`
A05				`@2 46`
A06				`@2 1`
A08	`01`	`1`	`ENG`	`@1 SCHEDULING IN THE PRESENCE OF PROCESSOR NETWORKS: COMPLEXITY AND APPROXIMATION`
A11	`01`	`1`		`@1 BOUDHT (Vincent)`
A11	`02`	`1`		`@1 COHHN (Johanne)`
A11	`03`	`1`		`@1 GIROUDEAU (Rodolphe)`
A11	`04`	`1`		`@1 KÖNIC (Jean-Clalide)`
A14	`01`			`@1 LIRMM, 161 rue Ada, 34392 Mtoutpellier Cedex 5 @2 UMR 5055 @3 FRA @Z 1 aut. @Z 3 aut. @Z 4 aut.`
A14	`02`			`@1 LORIA @2 54506 Vandoeuvre-lès-Nancy @3 FRA @Z 2 aut.`
A20				`@1 1-22`
A21				`@1 2012`
A23	`01`			`@0 ENG`
A24	`01`			`@0 fre`
A43	`01`			`@1 INIST @2 9323C @5 354000505216660010`
A44				`@0 0000 @1 © 2012 INIST-CNRS. All rights reserved.`
A45				`@0 23 ref.`
A47	`01`	`1`		`@0 12-0251183`
A60				`@1 P`
A61				`@0 A`
A64	`01`	`1`		`@0 RAIRO. Recherche opérationnelle`
A66	`01`			`@0 FRA`
C01	`01`		`ENG`	@0 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 i and j 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 NP-complete when the length of the schedule is at most three). We prove that there is no polynomial-time algorithm with a performance guarantee of less than 4/3 (unless P = NP) to minimize the makespan when the network topology is a chain or ring and the precedence graph is a bipartite graph of depth one. We also develop two polynomial-time approximation algorithms with constant ratio dedicated to cases where the processor network admits a limited or unlimited number of processors.
C02	`01`	`X`		`@0 001D01A13`
C02	`02`	`X`		`@0 001D02B04`
C02	`03`	`X`		`@0 001D01A12`
C02	`04`	`X`		`@0 001D02A05`
C03	`01`	`X`	`FRE`	`@0 Temps total achèvement @5 06`
C03	`01`	`X`	`ENG`	`@0 Makespan @5 06`
C03	`01`	`X`	`SPA`	`@0 Tiempo total acabamiento @5 06`
C03	`02`	`X`	`FRE`	`@0 Minimisation @5 07`
C03	`02`	`X`	`ENG`	`@0 Minimization @5 07`
C03	`02`	`X`	`SPA`	`@0 Minimización @5 07`
C03	`03`	`X`	`FRE`	`@0 Temps polynomial @5 08`
C03	`03`	`X`	`ENG`	`@0 Polynomial time @5 08`
C03	`03`	`X`	`SPA`	`@0 Tiempo polinomial @5 08`
C03	`04`	`X`	`FRE`	`@0 Problème NP complet @5 09`
C03	`04`	`X`	`ENG`	`@0 NP complete problem @5 09`
C03	`04`	`X`	`SPA`	`@0 Problema NP completo @5 09`
C03	`05`	`3`	`FRE`	`@0 Topologie circuit @5 10`
C03	`05`	`3`	`ENG`	`@0 Network topology @5 10`
C03	`06`	`X`	`FRE`	`@0 Système réparti @5 11`
C03	`06`	`X`	`ENG`	`@0 Distributed system @5 11`
C03	`06`	`X`	`SPA`	`@0 Sistema repartido @5 11`
C03	`07`	`X`	`FRE`	`@0 Anneau @5 12`
C03	`07`	`X`	`ENG`	`@0 Ring @5 12`
C03	`07`	`X`	`SPA`	`@0 Anillo @5 12`
C03	`08`	`X`	`FRE`	`@0 Graphe précédence @5 13`
C03	`08`	`X`	`ENG`	`@0 Precedence graph @5 13`
C03	`08`	`X`	`SPA`	`@0 Grafo precedencia @5 13`
C03	`09`	`X`	`FRE`	`@0 Contrainte précédence @5 14`
C03	`09`	`X`	`ENG`	`@0 Precedence constraint @5 14`
C03	`09`	`X`	`SPA`	`@0 Constreñimiento precedencia @5 14`
C03	`10`	`X`	`FRE`	`@0 Graphe biparti @5 15`
C03	`10`	`X`	`ENG`	`@0 Bipartite graph @5 15`
C03	`10`	`X`	`SPA`	`@0 Grafo bipartido @5 15`
C03	`11`	`X`	`FRE`	`@0 Multiprocesseur @5 16`
C03	`11`	`X`	`ENG`	`@0 Multiprocessor @5 16`
C03	`11`	`X`	`SPA`	`@0 Multiprocesador @5 16`
C03	`12`	`X`	`FRE`	`@0 Algorithme approximation @5 17`
C03	`12`	`X`	`ENG`	`@0 Approximation algorithm @5 17`
C03	`12`	`X`	`SPA`	`@0 Algoritmo aproximación @5 17`
C03	`13`	`X`	`FRE`	`@0 Délai transmission @5 18`
C03	`13`	`X`	`ENG`	`@0 Transmission time @5 18`
C03	`13`	`X`	`SPA`	`@0 Plazo transmisión @5 18`
C03	`14`	`X`	`FRE`	`@0 Modélisation @5 23`
C03	`14`	`X`	`ENG`	`@0 Modeling @5 23`
C03	`14`	`X`	`SPA`	`@0 Modelización @5 23`
C03	`15`	`X`	`FRE`	`@0 . @4 INC @5 82`
C03	`16`	`X`	`FRE`	`@0 Ordonnancement processeur @4 CD @5 96`
C03	`16`	`X`	`ENG`	`@0 Processor scheduling @4 CD @5 96`
C03	`16`	`X`	`SPA`	`@0 Planificación del procesador @4 CD @5 96`
N21				`@1 191`
N44	`01`			`@1 OTO`
N82				`@1 OTO`

Format Inist (serveur)

NO :	PASCAL 12-0251183 INIST
ET :	SCHEDULING IN THE PRESENCE OF PROCESSOR NETWORKS: COMPLEXITY AND APPROXIMATION
AU :	BOUDHT (Vincent); COHHN (Johanne); GIROUDEAU (Rodolphe); KÖNIC (Jean-Clalide)
AF :	LIRMM, 161 rue Ada, 34392 Mtoutpellier Cedex 5/UMR 5055/France (1 aut., 3 aut., 4 aut.); LORIA/54506 Vandoeuvre-lès-Nancy/France (2 aut.)
DT :	Publication en série; Niveau analytique
SO :	RAIRO. Recherche opérationnelle; ISSN 0399-0559; Coden RSROD3; France; Da. 2012; Vol. 46; No. 1; Pp. 1-22; Abs. français; Bibl. 23 ref.
LA :	Anglais
EA :	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 i and j 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 NP-complete when the length of the schedule is at most three). We prove that there is no polynomial-time algorithm with a performance guarantee of less than 4/3 (unless P = NP) to minimize the makespan when the network topology is a chain or ring and the precedence graph is a bipartite graph of depth one. We also develop two polynomial-time approximation algorithms with constant ratio dedicated to cases where the processor network admits a limited or unlimited number of processors.
CC :	001D01A13; 001D02B04; 001D01A12; 001D02A05
FD :	Temps total achèvement; Minimisation; Temps polynomial; Problème NP complet; Topologie circuit; Système réparti; Anneau; Graphe précédence; Contrainte précédence; Graphe biparti; Multiprocesseur; Algorithme approximation; Délai transmission; Modélisation; .; Ordonnancement processeur
ED :	Makespan; Minimization; Polynomial time; NP complete problem; Network topology; Distributed system; Ring; Precedence graph; Precedence constraint; Bipartite graph; Multiprocessor; Approximation algorithm; Transmission time; Modeling; Processor scheduling
SD :	Tiempo total acabamiento; Minimización; Tiempo polinomial; Problema NP completo; Sistema repartido; Anillo; Grafo precedencia; Constreñimiento precedencia; Grafo bipartido; Multiprocesador; Algoritmo aproximación; Plazo transmisión; Modelización; Planificación del procesador
LO :	INIST-9323C.354000505216660010
ID :	12-0251183

Links to Exploration step

Pascal:12-0251183

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">SCHEDULING IN THE PRESENCE OF PROCESSOR NETWORKS: COMPLEXITY AND APPROXIMATION</title>
<author><name sortKey="Boudht, Vincent" sort="Boudht, Vincent" uniqKey="Boudht V" first="Vincent" last="Boudht">Vincent Boudht</name>
<affiliation><inist:fA14 i1="01"><s1>LIRMM, 161 rue Ada, 34392 Mtoutpellier Cedex 5</s1>
<s2>UMR 5055</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Cohhn, Johanne" sort="Cohhn, Johanne" uniqKey="Cohhn J" first="Johanne" last="Cohhn">Johanne Cohhn</name>
<affiliation><inist:fA14 i1="02"><s1>LORIA</s1>
<s2>54506 Vandoeuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Giroudeau, Rodolphe" sort="Giroudeau, Rodolphe" uniqKey="Giroudeau R" first="Rodolphe" last="Giroudeau">Rodolphe Giroudeau</name>
<affiliation><inist:fA14 i1="01"><s1>LIRMM, 161 rue Ada, 34392 Mtoutpellier Cedex 5</s1>
<s2>UMR 5055</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Konic, Jean Clalide" sort="Konic, Jean Clalide" uniqKey="Konic J" first="Jean-Clalide" last="Könic">Jean-Clalide Könic</name>
<affiliation><inist:fA14 i1="01"><s1>LIRMM, 161 rue Ada, 34392 Mtoutpellier Cedex 5</s1>
<s2>UMR 5055</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">12-0251183</idno>
<date when="2012">2012</date>
<idno type="stanalyst">PASCAL 12-0251183 INIST</idno>
<idno type="RBID">Pascal:12-0251183</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">000118</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">SCHEDULING IN THE PRESENCE OF PROCESSOR NETWORKS: COMPLEXITY AND APPROXIMATION</title>
<author><name sortKey="Boudht, Vincent" sort="Boudht, Vincent" uniqKey="Boudht V" first="Vincent" last="Boudht">Vincent Boudht</name>
<affiliation><inist:fA14 i1="01"><s1>LIRMM, 161 rue Ada, 34392 Mtoutpellier Cedex 5</s1>
<s2>UMR 5055</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Cohhn, Johanne" sort="Cohhn, Johanne" uniqKey="Cohhn J" first="Johanne" last="Cohhn">Johanne Cohhn</name>
<affiliation><inist:fA14 i1="02"><s1>LORIA</s1>
<s2>54506 Vandoeuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Giroudeau, Rodolphe" sort="Giroudeau, Rodolphe" uniqKey="Giroudeau R" first="Rodolphe" last="Giroudeau">Rodolphe Giroudeau</name>
<affiliation><inist:fA14 i1="01"><s1>LIRMM, 161 rue Ada, 34392 Mtoutpellier Cedex 5</s1>
<s2>UMR 5055</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Konic, Jean Clalide" sort="Konic, Jean Clalide" uniqKey="Konic J" first="Jean-Clalide" last="Könic">Jean-Clalide Könic</name>
<affiliation><inist:fA14 i1="01"><s1>LIRMM, 161 rue Ada, 34392 Mtoutpellier Cedex 5</s1>
<s2>UMR 5055</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
</analytic>
<series><title level="j" type="main">RAIRO. Recherche opérationnelle</title>
<title level="j" type="abbreviated">RAIRO, Rech. opér.</title>
<idno type="ISSN">0399-0559</idno>
<imprint><date when="2012">2012</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">RAIRO. Recherche opérationnelle</title>
<title level="j" type="abbreviated">RAIRO, Rech. opér.</title>
<idno type="ISSN">0399-0559</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Approximation algorithm</term>
<term>Bipartite graph</term>
<term>Distributed system</term>
<term>Makespan</term>
<term>Minimization</term>
<term>Modeling</term>
<term>Multiprocessor</term>
<term>NP complete problem</term>
<term>Network topology</term>
<term>Polynomial time</term>
<term>Precedence constraint</term>
<term>Precedence graph</term>
<term>Processor scheduling</term>
<term>Ring</term>
<term>Transmission time</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Temps total achèvement</term>
<term>Minimisation</term>
<term>Temps polynomial</term>
<term>Problème NP complet</term>
<term>Topologie circuit</term>
<term>Système réparti</term>
<term>Anneau</term>
<term>Graphe précédence</term>
<term>Contrainte précédence</term>
<term>Graphe biparti</term>
<term>Multiprocesseur</term>
<term>Algorithme approximation</term>
<term>Délai transmission</term>
<term>Modélisation</term>
<term>.</term>
<term>Ordonnancement processeur</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">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 i and j 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 NP-complete when the length of the schedule is at most three). We prove that there is no polynomial-time algorithm with a performance guarantee of less than 4/3 (unless P = NP) to minimize the makespan when the network topology is a chain or ring and the precedence graph is a bipartite graph of depth one. We also develop two polynomial-time approximation algorithms with constant ratio dedicated to cases where the processor network admits a limited or unlimited number of processors.</div>
</front>
</TEI>
<inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0399-0559</s0>
</fA01>
<fA02 i1="01"><s0>RSROD3</s0>
</fA02>
<fA03 i2="1"><s0>RAIRO, Rech. opér.</s0>
</fA03>
<fA05><s2>46</s2>
</fA05>
<fA06><s2>1</s2>
</fA06>
<fA08 i1="01" i2="1" l="ENG"><s1>SCHEDULING IN THE PRESENCE OF PROCESSOR NETWORKS: COMPLEXITY AND APPROXIMATION</s1>
</fA08>
<fA11 i1="01" i2="1"><s1>BOUDHT (Vincent)</s1>
</fA11>
<fA11 i1="02" i2="1"><s1>COHHN (Johanne)</s1>
</fA11>
<fA11 i1="03" i2="1"><s1>GIROUDEAU (Rodolphe)</s1>
</fA11>
<fA11 i1="04" i2="1"><s1>KÖNIC (Jean-Clalide)</s1>
</fA11>
<fA14 i1="01"><s1>LIRMM, 161 rue Ada, 34392 Mtoutpellier Cedex 5</s1>
<s2>UMR 5055</s2>
<s3>FRA</s3>
<sZ>1 aut.</sZ>
<sZ>3 aut.</sZ>
<sZ>4 aut.</sZ>
</fA14>
<fA14 i1="02"><s1>LORIA</s1>
<s2>54506 Vandoeuvre-lès-Nancy</s2>
<s3>FRA</s3>
<sZ>2 aut.</sZ>
</fA14>
<fA20><s1>1-22</s1>
</fA20>
<fA21><s1>2012</s1>
</fA21>
<fA23 i1="01"><s0>ENG</s0>
</fA23>
<fA24 i1="01"><s0>fre</s0>
</fA24>
<fA43 i1="01"><s1>INIST</s1>
<s2>9323C</s2>
<s5>354000505216660010</s5>
</fA43>
<fA44><s0>0000</s0>
<s1>© 2012 INIST-CNRS. All rights reserved.</s1>
</fA44>
<fA45><s0>23 ref.</s0>
</fA45>
<fA47 i1="01" i2="1"><s0>12-0251183</s0>
</fA47>
<fA60><s1>P</s1>
</fA60>
<fA61><s0>A</s0>
</fA61>
<fA64 i1="01" i2="1"><s0>RAIRO. Recherche opérationnelle</s0>
</fA64>
<fA66 i1="01"><s0>FRA</s0>
</fA66>
<fC01 i1="01" l="ENG"><s0>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 i and j 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 NP-complete when the length of the schedule is at most three). We prove that there is no polynomial-time algorithm with a performance guarantee of less than 4/3 (unless P = NP) to minimize the makespan when the network topology is a chain or ring and the precedence graph is a bipartite graph of depth one. We also develop two polynomial-time approximation algorithms with constant ratio dedicated to cases where the processor network admits a limited or unlimited number of processors.</s0>
</fC01>
<fC02 i1="01" i2="X"><s0>001D01A13</s0>
</fC02>
<fC02 i1="02" i2="X"><s0>001D02B04</s0>
</fC02>
<fC02 i1="03" i2="X"><s0>001D01A12</s0>
</fC02>
<fC02 i1="04" i2="X"><s0>001D02A05</s0>
</fC02>
<fC03 i1="01" i2="X" l="FRE"><s0>Temps total achèvement</s0>
<s5>06</s5>
</fC03>
<fC03 i1="01" i2="X" l="ENG"><s0>Makespan</s0>
<s5>06</s5>
</fC03>
<fC03 i1="01" i2="X" l="SPA"><s0>Tiempo total acabamiento</s0>
<s5>06</s5>
</fC03>
<fC03 i1="02" i2="X" l="FRE"><s0>Minimisation</s0>
<s5>07</s5>
</fC03>
<fC03 i1="02" i2="X" l="ENG"><s0>Minimization</s0>
<s5>07</s5>
</fC03>
<fC03 i1="02" i2="X" l="SPA"><s0>Minimización</s0>
<s5>07</s5>
</fC03>
<fC03 i1="03" i2="X" l="FRE"><s0>Temps polynomial</s0>
<s5>08</s5>
</fC03>
<fC03 i1="03" i2="X" l="ENG"><s0>Polynomial time</s0>
<s5>08</s5>
</fC03>
<fC03 i1="03" i2="X" l="SPA"><s0>Tiempo polinomial</s0>
<s5>08</s5>
</fC03>
<fC03 i1="04" i2="X" l="FRE"><s0>Problème NP complet</s0>
<s5>09</s5>
</fC03>
<fC03 i1="04" i2="X" l="ENG"><s0>NP complete problem</s0>
<s5>09</s5>
</fC03>
<fC03 i1="04" i2="X" l="SPA"><s0>Problema NP completo</s0>
<s5>09</s5>
</fC03>
<fC03 i1="05" i2="3" l="FRE"><s0>Topologie circuit</s0>
<s5>10</s5>
</fC03>
<fC03 i1="05" i2="3" l="ENG"><s0>Network topology</s0>
<s5>10</s5>
</fC03>
<fC03 i1="06" i2="X" l="FRE"><s0>Système réparti</s0>
<s5>11</s5>
</fC03>
<fC03 i1="06" i2="X" l="ENG"><s0>Distributed system</s0>
<s5>11</s5>
</fC03>
<fC03 i1="06" i2="X" l="SPA"><s0>Sistema repartido</s0>
<s5>11</s5>
</fC03>
<fC03 i1="07" i2="X" l="FRE"><s0>Anneau</s0>
<s5>12</s5>
</fC03>
<fC03 i1="07" i2="X" l="ENG"><s0>Ring</s0>
<s5>12</s5>
</fC03>
<fC03 i1="07" i2="X" l="SPA"><s0>Anillo</s0>
<s5>12</s5>
</fC03>
<fC03 i1="08" i2="X" l="FRE"><s0>Graphe précédence</s0>
<s5>13</s5>
</fC03>
<fC03 i1="08" i2="X" l="ENG"><s0>Precedence graph</s0>
<s5>13</s5>
</fC03>
<fC03 i1="08" i2="X" l="SPA"><s0>Grafo precedencia</s0>
<s5>13</s5>
</fC03>
<fC03 i1="09" i2="X" l="FRE"><s0>Contrainte précédence</s0>
<s5>14</s5>
</fC03>
<fC03 i1="09" i2="X" l="ENG"><s0>Precedence constraint</s0>
<s5>14</s5>
</fC03>
<fC03 i1="09" i2="X" l="SPA"><s0>Constreñimiento precedencia</s0>
<s5>14</s5>
</fC03>
<fC03 i1="10" i2="X" l="FRE"><s0>Graphe biparti</s0>
<s5>15</s5>
</fC03>
<fC03 i1="10" i2="X" l="ENG"><s0>Bipartite graph</s0>
<s5>15</s5>
</fC03>
<fC03 i1="10" i2="X" l="SPA"><s0>Grafo bipartido</s0>
<s5>15</s5>
</fC03>
<fC03 i1="11" i2="X" l="FRE"><s0>Multiprocesseur</s0>
<s5>16</s5>
</fC03>
<fC03 i1="11" i2="X" l="ENG"><s0>Multiprocessor</s0>
<s5>16</s5>
</fC03>
<fC03 i1="11" i2="X" l="SPA"><s0>Multiprocesador</s0>
<s5>16</s5>
</fC03>
<fC03 i1="12" i2="X" l="FRE"><s0>Algorithme approximation</s0>
<s5>17</s5>
</fC03>
<fC03 i1="12" i2="X" l="ENG"><s0>Approximation algorithm</s0>
<s5>17</s5>
</fC03>
<fC03 i1="12" i2="X" l="SPA"><s0>Algoritmo aproximación</s0>
<s5>17</s5>
</fC03>
<fC03 i1="13" i2="X" l="FRE"><s0>Délai transmission</s0>
<s5>18</s5>
</fC03>
<fC03 i1="13" i2="X" l="ENG"><s0>Transmission time</s0>
<s5>18</s5>
</fC03>
<fC03 i1="13" i2="X" l="SPA"><s0>Plazo transmisión</s0>
<s5>18</s5>
</fC03>
<fC03 i1="14" i2="X" l="FRE"><s0>Modélisation</s0>
<s5>23</s5>
</fC03>
<fC03 i1="14" i2="X" l="ENG"><s0>Modeling</s0>
<s5>23</s5>
</fC03>
<fC03 i1="14" i2="X" l="SPA"><s0>Modelización</s0>
<s5>23</s5>
</fC03>
<fC03 i1="15" i2="X" l="FRE"><s0>.</s0>
<s4>INC</s4>
<s5>82</s5>
</fC03>
<fC03 i1="16" i2="X" l="FRE"><s0>Ordonnancement processeur</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fC03 i1="16" i2="X" l="ENG"><s0>Processor scheduling</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fC03 i1="16" i2="X" l="SPA"><s0>Planificación del procesador</s0>
<s4>CD</s4>
<s5>96</s5>
</fC03>
<fN21><s1>191</s1>
</fN21>
<fN44 i1="01"><s1>OTO</s1>
</fN44>
<fN82><s1>OTO</s1>
</fN82>
</pA>
</standard>
<server><NO>PASCAL 12-0251183 INIST</NO>
<ET>SCHEDULING IN THE PRESENCE OF PROCESSOR NETWORKS: COMPLEXITY AND APPROXIMATION</ET>
<AU>BOUDHT (Vincent); COHHN (Johanne); GIROUDEAU (Rodolphe); KÖNIC (Jean-Clalide)</AU>
<AF>LIRMM, 161 rue Ada, 34392 Mtoutpellier Cedex 5/UMR 5055/France (1 aut., 3 aut., 4 aut.); LORIA/54506 Vandoeuvre-lès-Nancy/France (2 aut.)</AF>
<DT>Publication en série; Niveau analytique</DT>
<SO>RAIRO. Recherche opérationnelle; ISSN 0399-0559; Coden RSROD3; France; Da. 2012; Vol. 46; No. 1; Pp. 1-22; Abs. français; Bibl. 23 ref.</SO>
<LA>Anglais</LA>
<EA>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 i and j 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 NP-complete when the length of the schedule is at most three). We prove that there is no polynomial-time algorithm with a performance guarantee of less than 4/3 (unless P = NP) to minimize the makespan when the network topology is a chain or ring and the precedence graph is a bipartite graph of depth one. We also develop two polynomial-time approximation algorithms with constant ratio dedicated to cases where the processor network admits a limited or unlimited number of processors.</EA>
<CC>001D01A13; 001D02B04; 001D01A12; 001D02A05</CC>
<FD>Temps total achèvement; Minimisation; Temps polynomial; Problème NP complet; Topologie circuit; Système réparti; Anneau; Graphe précédence; Contrainte précédence; Graphe biparti; Multiprocesseur; Algorithme approximation; Délai transmission; Modélisation; .; Ordonnancement processeur</FD>
<ED>Makespan; Minimization; Polynomial time; NP complete problem; Network topology; Distributed system; Ring; Precedence graph; Precedence constraint; Bipartite graph; Multiprocessor; Approximation algorithm; Transmission time; Modeling; Processor scheduling</ED>
<SD>Tiempo total acabamiento; Minimización; Tiempo polinomial; Problema NP completo; Sistema repartido; Anillo; Grafo precedencia; Constreñimiento precedencia; Grafo bipartido; Multiprocesador; Algoritmo aproximación; Plazo transmisión; Modelización; Planificación del procesador</SD>
<LO>INIST-9323C.354000505216660010</LO>
<ID>12-0251183</ID>
</server>
</inist>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/PascalFrancis/Corpus

HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000118 | SxmlIndent | more

HfdSelect -h $EXPLOR_AREA/Data/PascalFrancis/Corpus/biblio.hfd -nk 000118 | SxmlIndent | more

Pour mettre un lien sur cette page dans le réseau Wicri

{{Explor lien
   |wiki=    Wicri/Lorraine
   |area=    InforLorV4
   |flux=    PascalFrancis
   |étape=   Corpus
   |type=    RBID
   |clé=     Pascal:12-0251183
   |texte=   SCHEDULING IN THE PRESENCE OF PROCESSOR NETWORKS: COMPLEXITY AND APPROXIMATION
}}

This area was generated with Dilib version V0.6.33.
Data generation: Mon Jun 10 21:56:28 2019. Site generation: Fri Feb 25 15:29:27 2022

	Serveur d'exploration sur la recherche en informatique en Lorraine
	Attention, ce site est en cours de développement ! Attention, site généré par des moyens informatiques à partir de corpus bruts. Les informations ne sont donc pas validées.

Serveur d'exploration sur la recherche en informatique en Lorraine

SCHEDULING IN THE PRESENCE OF PROCESSOR NETWORKS: COMPLEXITY AND APPROXIMATION

SCHEDULING IN THE PRESENCE OF PROCESSOR NETWORKS: COMPLEXITY AND APPROXIMATION

Source :

Descripteurs français

English descriptors

Abstract

Notice en format standard (ISO 2709)

Format Inist (serveur)

Links to Exploration step

Le document en format XML

Pour manipuler ce document sous Unix (Dilib)

Pour mettre un lien sur cette page dans le réseau Wicri