UnivTrevesV1, PascalFrancis, Corpus, bibRecord, 001501

UET-scheduling with chain-type precedence constraints

Identifieur interne : 001501 ( PascalFrancis/Corpus ); précédent : 001500; suivant : 001502

UET-scheduling with chain-type precedence constraints

Auteurs : K. Jansen ; G. J. Woeginger ; ZHONGLIANG YU

Source :

Computers & operations research [ 0305-0548 ] ; 1995.

RBID : Pascal:95-0527905

Descripteurs français

Pascal (Inist)
- Ordonnancement, Système parallèle, Problème NP complet, Algorithme, Approximation, Borne inférieure, Optimisation.

English descriptors

KwdEn :
- Algorithm, Approximation, Lower bound, NP complete problem, Optimization, Parallel system, Scheduling.

Abstract

We consider a special case of the precedence constrained scheduling problem of unit execution time jobs on two parallel machines without preemption: the precedence constraints are chain-type and each job can be processed on only one of the two machines. We show that this problem is NP-complete in general, and we derive an approximation algorithm with constant worst case guarantee.

Notice en format standard (ISO 2709)

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

A01	`01`	`1`		`@0 0305-0548`
A02	`01`			`@0 CMORAP`
A03		`1`		`@0 Comput. oper. res.`
A05				`@2 22`
A06				`@2 9`
A08	`01`	`1`	`ENG`	`@1 UET-scheduling with chain-type precedence constraints`
A11	`01`	`1`		`@1 JANSEN (K.)`
A11	`02`	`1`		`@1 WOEGINGER (G. J.)`
A11	`03`	`1`		`@1 ZHONGLIANG YU`
A14	`01`			`@1 Univ. Trier, Fachbereich IV Mathematik Informatik @2 54286 Trier @3 DEU @Z 1 aut.`
A20				`@1 915-920`
A21				`@1 1995`
A23	`01`			`@0 ENG`
A43	`01`			`@1 INIST @2 16412 @5 354000053986990050`
A44				`@0 0000`
A45				`@0 7 ref.`
A47	`01`	`1`		`@0 95-0527905`
A60				`@1 P`
A61				`@0 A`
A64	`01`	`1`		`@0 Computers & operations research`
A66	`01`			`@0 USA`
C01	`01`		`ENG`	`@0 We consider a special case of the precedence constrained scheduling problem of unit execution time jobs on two parallel machines without preemption: the precedence constraints are chain-type and each job can be processed on only one of the two machines. We show that this problem is NP-complete in general, and we derive an approximation algorithm with constant worst case guarantee.`
C02	`01`	`1`		`@0 001D02B04`
C03	`01`	`X`	`FRE`	`@0 Ordonnancement @5 01`
C03	`01`	`X`	`ENG`	`@0 Scheduling @5 01`
C03	`01`	`X`	`GER`	`@0 Netzplantechnik @5 01`
C03	`01`	`X`	`SPA`	`@0 Ordonamiento @5 01`
C03	`02`	`X`	`FRE`	`@0 Système parallèle @5 02`
C03	`02`	`X`	`ENG`	`@0 Parallel system @5 02`
C03	`02`	`X`	`SPA`	`@0 Sistema paralelo @5 02`
C03	`03`	`X`	`FRE`	`@0 Problème NP complet @5 03`
C03	`03`	`X`	`ENG`	`@0 NP complete problem @5 03`
C03	`03`	`X`	`SPA`	`@0 Problema NP completo @5 03`
C03	`04`	`X`	`FRE`	`@0 Algorithme @5 04`
C03	`04`	`X`	`ENG`	`@0 Algorithm @5 04`
C03	`04`	`X`	`GER`	`@0 Algorithmus @5 04`
C03	`04`	`X`	`SPA`	`@0 Algoritmo @5 04`
C03	`05`	`X`	`FRE`	`@0 Approximation @5 05`
C03	`05`	`X`	`ENG`	`@0 Approximation @5 05`
C03	`05`	`X`	`GER`	`@0 Naeherungsverfahren @5 05`
C03	`05`	`X`	`SPA`	`@0 Aproximación @5 05`
C03	`06`	`X`	`FRE`	`@0 Borne inférieure @5 06`
C03	`06`	`X`	`ENG`	`@0 Lower bound @5 06`
C03	`06`	`X`	`SPA`	`@0 Cota inferior @5 06`
C03	`07`	`X`	`FRE`	`@0 Optimisation @5 07`
C03	`07`	`X`	`ENG`	`@0 Optimization @5 07`
C03	`07`	`X`	`GER`	`@0 Optimierung @5 07`
C03	`07`	`X`	`SPA`	`@0 Optimización @5 07`
N21				`@1 302`

Format Inist (serveur)

NO :	PASCAL 95-0527905 INIST
ET :	UET-scheduling with chain-type precedence constraints
AU :	JANSEN (K.); WOEGINGER (G. J.); ZHONGLIANG YU
AF :	Univ. Trier, Fachbereich IV Mathematik Informatik/54286 Trier/Allemagne (1 aut.)
DT :	Publication en série; Niveau analytique
SO :	Computers & operations research; ISSN 0305-0548; Coden CMORAP; Etats-Unis; Da. 1995; Vol. 22; No. 9; Pp. 915-920; Bibl. 7 ref.
LA :	Anglais
EA :	We consider a special case of the precedence constrained scheduling problem of unit execution time jobs on two parallel machines without preemption: the precedence constraints are chain-type and each job can be processed on only one of the two machines. We show that this problem is NP-complete in general, and we derive an approximation algorithm with constant worst case guarantee.
CC :	001D02B04
FD :	Ordonnancement; Système parallèle; Problème NP complet; Algorithme; Approximation; Borne inférieure; Optimisation
ED :	Scheduling; Parallel system; NP complete problem; Algorithm; Approximation; Lower bound; Optimization
GD :	Netzplantechnik; Algorithmus; Naeherungsverfahren; Optimierung
SD :	Ordonamiento; Sistema paralelo; Problema NP completo; Algoritmo; Aproximación; Cota inferior; Optimización
LO :	INIST-16412.354000053986990050
ID :	95-0527905

Links to Exploration step

Pascal:95-0527905

Le document en format XML

<record><TEI><teiHeader><fileDesc><titleStmt><title xml:lang="en" level="a">UET-scheduling with chain-type precedence constraints</title>
<author><name sortKey="Jansen, K" sort="Jansen, K" uniqKey="Jansen K" first="K." last="Jansen">K. Jansen</name>
<affiliation><inist:fA14 i1="01"><s1>Univ. Trier, Fachbereich IV Mathematik Informatik</s1>
<s2>54286 Trier</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Woeginger, G J" sort="Woeginger, G J" uniqKey="Woeginger G" first="G. J." last="Woeginger">G. J. Woeginger</name>
</author>
<author><name sortKey="Zhongliang Yu" sort="Zhongliang Yu" uniqKey="Zhongliang Yu" last="Zhongliang Yu">ZHONGLIANG YU</name>
</author>
</titleStmt>
<publicationStmt><idno type="wicri:source">INIST</idno>
<idno type="inist">95-0527905</idno>
<date when="1995">1995</date>
<idno type="stanalyst">PASCAL 95-0527905 INIST</idno>
<idno type="RBID">Pascal:95-0527905</idno>
<idno type="wicri:Area/PascalFrancis/Corpus">001501</idno>
</publicationStmt>
<sourceDesc><biblStruct><analytic><title xml:lang="en" level="a">UET-scheduling with chain-type precedence constraints</title>
<author><name sortKey="Jansen, K" sort="Jansen, K" uniqKey="Jansen K" first="K." last="Jansen">K. Jansen</name>
<affiliation><inist:fA14 i1="01"><s1>Univ. Trier, Fachbereich IV Mathematik Informatik</s1>
<s2>54286 Trier</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
</inist:fA14>
</affiliation>
</author>
<author><name sortKey="Woeginger, G J" sort="Woeginger, G J" uniqKey="Woeginger G" first="G. J." last="Woeginger">G. J. Woeginger</name>
</author>
<author><name sortKey="Zhongliang Yu" sort="Zhongliang Yu" uniqKey="Zhongliang Yu" last="Zhongliang Yu">ZHONGLIANG YU</name>
</author>
</analytic>
<series><title level="j" type="main">Computers & operations research</title>
<title level="j" type="abbreviated">Comput. oper. res.</title>
<idno type="ISSN">0305-0548</idno>
<imprint><date when="1995">1995</date>
</imprint>
</series>
</biblStruct>
</sourceDesc>
<seriesStmt><title level="j" type="main">Computers & operations research</title>
<title level="j" type="abbreviated">Comput. oper. res.</title>
<idno type="ISSN">0305-0548</idno>
</seriesStmt>
</fileDesc>
<profileDesc><textClass><keywords scheme="KwdEn" xml:lang="en"><term>Algorithm</term>
<term>Approximation</term>
<term>Lower bound</term>
<term>NP complete problem</term>
<term>Optimization</term>
<term>Parallel system</term>
<term>Scheduling</term>
</keywords>
<keywords scheme="Pascal" xml:lang="fr"><term>Ordonnancement</term>
<term>Système parallèle</term>
<term>Problème NP complet</term>
<term>Algorithme</term>
<term>Approximation</term>
<term>Borne inférieure</term>
<term>Optimisation</term>
</keywords>
</textClass>
</profileDesc>
</teiHeader>
<front><div type="abstract" xml:lang="en">We consider a special case of the precedence constrained scheduling problem of unit execution time jobs on two parallel machines without preemption: the precedence constraints are chain-type and each job can be processed on only one of the two machines. We show that this problem is NP-complete in general, and we derive an approximation algorithm with constant worst case guarantee.</div>
</front>
</TEI>
<inist><standard h6="B"><pA><fA01 i1="01" i2="1"><s0>0305-0548</s0>
</fA01>
<fA02 i1="01"><s0>CMORAP</s0>
</fA02>
<fA03 i2="1"><s0>Comput. oper. res.</s0>
</fA03>
<fA05><s2>22</s2>
</fA05>
<fA06><s2>9</s2>
</fA06>
<fA08 i1="01" i2="1" l="ENG"><s1>UET-scheduling with chain-type precedence constraints</s1>
</fA08>
<fA11 i1="01" i2="1"><s1>JANSEN (K.)</s1>
</fA11>
<fA11 i1="02" i2="1"><s1>WOEGINGER (G. J.)</s1>
</fA11>
<fA11 i1="03" i2="1"><s1>ZHONGLIANG YU</s1>
</fA11>
<fA14 i1="01"><s1>Univ. Trier, Fachbereich IV Mathematik Informatik</s1>
<s2>54286 Trier</s2>
<s3>DEU</s3>
<sZ>1 aut.</sZ>
</fA14>
<fA20><s1>915-920</s1>
</fA20>
<fA21><s1>1995</s1>
</fA21>
<fA23 i1="01"><s0>ENG</s0>
</fA23>
<fA43 i1="01"><s1>INIST</s1>
<s2>16412</s2>
<s5>354000053986990050</s5>
</fA43>
<fA44><s0>0000</s0>
</fA44>
<fA45><s0>7 ref.</s0>
</fA45>
<fA47 i1="01" i2="1"><s0>95-0527905</s0>
</fA47>
<fA60><s1>P</s1>
</fA60>
<fA61><s0>A</s0>
</fA61>
<fA64 i1="01" i2="1"><s0>Computers & operations research</s0>
</fA64>
<fA66 i1="01"><s0>USA</s0>
</fA66>
<fC01 i1="01" l="ENG"><s0>We consider a special case of the precedence constrained scheduling problem of unit execution time jobs on two parallel machines without preemption: the precedence constraints are chain-type and each job can be processed on only one of the two machines. We show that this problem is NP-complete in general, and we derive an approximation algorithm with constant worst case guarantee.</s0>
</fC01>
<fC02 i1="01" i2="1"><s0>001D02B04</s0>
</fC02>
<fC03 i1="01" i2="X" l="FRE"><s0>Ordonnancement</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="ENG"><s0>Scheduling</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="GER"><s0>Netzplantechnik</s0>
<s5>01</s5>
</fC03>
<fC03 i1="01" i2="X" l="SPA"><s0>Ordonamiento</s0>
<s5>01</s5>
</fC03>
<fC03 i1="02" i2="X" l="FRE"><s0>Système parallèle</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="ENG"><s0>Parallel system</s0>
<s5>02</s5>
</fC03>
<fC03 i1="02" i2="X" l="SPA"><s0>Sistema paralelo</s0>
<s5>02</s5>
</fC03>
<fC03 i1="03" i2="X" l="FRE"><s0>Problème NP complet</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="ENG"><s0>NP complete problem</s0>
<s5>03</s5>
</fC03>
<fC03 i1="03" i2="X" l="SPA"><s0>Problema NP completo</s0>
<s5>03</s5>
</fC03>
<fC03 i1="04" i2="X" l="FRE"><s0>Algorithme</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="ENG"><s0>Algorithm</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="GER"><s0>Algorithmus</s0>
<s5>04</s5>
</fC03>
<fC03 i1="04" i2="X" l="SPA"><s0>Algoritmo</s0>
<s5>04</s5>
</fC03>
<fC03 i1="05" i2="X" l="FRE"><s0>Approximation</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="ENG"><s0>Approximation</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="GER"><s0>Naeherungsverfahren</s0>
<s5>05</s5>
</fC03>
<fC03 i1="05" i2="X" l="SPA"><s0>Aproximación</s0>
<s5>05</s5>
</fC03>
<fC03 i1="06" i2="X" l="FRE"><s0>Borne inférieure</s0>
<s5>06</s5>
</fC03>
<fC03 i1="06" i2="X" l="ENG"><s0>Lower bound</s0>
<s5>06</s5>
</fC03>
<fC03 i1="06" i2="X" l="SPA"><s0>Cota inferior</s0>
<s5>06</s5>
</fC03>
<fC03 i1="07" i2="X" l="FRE"><s0>Optimisation</s0>
<s5>07</s5>
</fC03>
<fC03 i1="07" i2="X" l="ENG"><s0>Optimization</s0>
<s5>07</s5>
</fC03>
<fC03 i1="07" i2="X" l="GER"><s0>Optimierung</s0>
<s5>07</s5>
</fC03>
<fC03 i1="07" i2="X" l="SPA"><s0>Optimización</s0>
<s5>07</s5>
</fC03>
<fN21><s1>302</s1>
</fN21>
</pA>
</standard>
<server><NO>PASCAL 95-0527905 INIST</NO>
<ET>UET-scheduling with chain-type precedence constraints</ET>
<AU>JANSEN (K.); WOEGINGER (G. J.); ZHONGLIANG YU</AU>
<AF>Univ. Trier, Fachbereich IV Mathematik Informatik/54286 Trier/Allemagne (1 aut.)</AF>
<DT>Publication en série; Niveau analytique</DT>
<SO>Computers & operations research; ISSN 0305-0548; Coden CMORAP; Etats-Unis; Da. 1995; Vol. 22; No. 9; Pp. 915-920; Bibl. 7 ref.</SO>
<LA>Anglais</LA>
<EA>We consider a special case of the precedence constrained scheduling problem of unit execution time jobs on two parallel machines without preemption: the precedence constraints are chain-type and each job can be processed on only one of the two machines. We show that this problem is NP-complete in general, and we derive an approximation algorithm with constant worst case guarantee.</EA>
<CC>001D02B04</CC>
<FD>Ordonnancement; Système parallèle; Problème NP complet; Algorithme; Approximation; Borne inférieure; Optimisation</FD>
<ED>Scheduling; Parallel system; NP complete problem; Algorithm; Approximation; Lower bound; Optimization</ED>
<GD>Netzplantechnik; Algorithmus; Naeherungsverfahren; Optimierung</GD>
<SD>Ordonamiento; Sistema paralelo; Problema NP completo; Algoritmo; Aproximación; Cota inferior; Optimización</SD>
<LO>INIST-16412.354000053986990050</LO>
<ID>95-0527905</ID>
</server>
</inist>
</record>

Pour manipuler ce document sous Unix (Dilib)

EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/PascalFrancis/Corpus

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

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

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

{{Explor lien
   |wiki=    Wicri/Rhénanie
   |area=    UnivTrevesV1
   |flux=    PascalFrancis
   |étape=   Corpus
   |type=    RBID
   |clé=     Pascal:95-0527905
   |texte=   UET-scheduling with chain-type precedence constraints
}}

This area was generated with Dilib version V0.6.31.
Data generation: Sat Jul 22 16:29:01 2017. Site generation: Wed Feb 28 14:55:37 2024

	Serveur d'exploration sur l'Université de Trèves
	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 l'Université de Trèves

UET-scheduling with chain-type precedence constraints

UET-scheduling with chain-type precedence constraints

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