UET-scheduling with chain-type precedence constraints
Identifieur interne : 000A21 ( Istex/Corpus ); précédent : 000A20; suivant : 000A22UET-scheduling with chain-type precedence constraints
Auteurs : Klaus Jansen ; Gerhard J. Woeginger ; Zhongliang YuSource :
- Computers and Operations Research [ 0305-0548 ] ; 1995.
Abstract
We consider a special case of the precedence constrained scheduling problem of n 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.
Url:
DOI: 10.1016/0305-0548(94)00084-L
Links to Exploration step
ISTEX:E637099CC8CFB14017DE4194765EE8CD0FAF24D5Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title>UET-scheduling with chain-type precedence constraints</title><author><name sortKey="Jansen, Klaus" sort="Jansen, Klaus" uniqKey="Jansen K" first="Klaus" last="Jansen">Klaus Jansen</name><affiliation><mods:affiliation>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, D-54286 Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>‡ Klaus Jansen received a diploma degree in Computer Science from the RTWTH Aachen and a Ph.D. degree in computer science—mathematics from the University of Trier, Germany. He is currently Assistant Professor at the University of Trier, Germany. His research interests are in combinatorial optimization, scheduling, high-level synthesis and computational geometry. His publications have appeared in BIT, Commentationes Mathematicae Universitatis Carolinae, Computational Geometry, Computers & Operations Research, Discrete Applied Mathematics, and other Journals.</mods:affiliation></affiliation></author><author><name sortKey="Woeginger, Gerhard J" sort="Woeginger, Gerhard J" uniqKey="Woeginger G" first="Gerhard J." last="Woeginger">Gerhard J. Woeginger</name><affiliation><mods:affiliation>To whom all correspondence should be addressed.</mods:affiliation></affiliation><affiliation><mods:affiliation>TU Graz, Institut für Mathematik B, Kopernikusgasse 24, A-8010 Graz, Austria</mods:affiliation></affiliation><affiliation><mods:affiliation>§ Gerhard J. Woeginger received his Ph.D. from the Technical University of Graz in 1990. He is currently Assistant Professor at the Technical University of Graz, Austria. His research interests include combinatorial optimization, scheduling and on-line proble,s. He has published in journals including OR Letters, SIAM Journal on Computing and SIAM Journal on Discrete Mathematics.</mods:affiliation></affiliation></author><author><name sortKey="Yu, Zhongliang" sort="Yu, Zhongliang" uniqKey="Yu Z" first="Zhongliang" last="Yu">Zhongliang Yu</name><affiliation><mods:affiliation>TU Graz, Institut für Mathematik B, Kopernikusgasse 24, A-8010 Graz, Austria</mods:affiliation></affiliation><affiliation><mods:affiliation>| On leave from the Mathematics Section, Forestry University Nanjing, Nanjing, China.</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:E637099CC8CFB14017DE4194765EE8CD0FAF24D5</idno><date when="1995" year="1995">1995</date><idno type="doi">10.1016/0305-0548(94)00084-L</idno><idno type="url">https://api.istex.fr/document/E637099CC8CFB14017DE4194765EE8CD0FAF24D5/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">000A21</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">000A21</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a">UET-scheduling with chain-type precedence constraints</title><author><name sortKey="Jansen, Klaus" sort="Jansen, Klaus" uniqKey="Jansen K" first="Klaus" last="Jansen">Klaus Jansen</name><affiliation><mods:affiliation>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, D-54286 Trier, Germany</mods:affiliation></affiliation><affiliation><mods:affiliation>‡ Klaus Jansen received a diploma degree in Computer Science from the RTWTH Aachen and a Ph.D. degree in computer science—mathematics from the University of Trier, Germany. He is currently Assistant Professor at the University of Trier, Germany. His research interests are in combinatorial optimization, scheduling, high-level synthesis and computational geometry. His publications have appeared in BIT, Commentationes Mathematicae Universitatis Carolinae, Computational Geometry, Computers & Operations Research, Discrete Applied Mathematics, and other Journals.</mods:affiliation></affiliation></author><author><name sortKey="Woeginger, Gerhard J" sort="Woeginger, Gerhard J" uniqKey="Woeginger G" first="Gerhard J." last="Woeginger">Gerhard J. Woeginger</name><affiliation><mods:affiliation>To whom all correspondence should be addressed.</mods:affiliation></affiliation><affiliation><mods:affiliation>TU Graz, Institut für Mathematik B, Kopernikusgasse 24, A-8010 Graz, Austria</mods:affiliation></affiliation><affiliation><mods:affiliation>§ Gerhard J. Woeginger received his Ph.D. from the Technical University of Graz in 1990. He is currently Assistant Professor at the Technical University of Graz, Austria. His research interests include combinatorial optimization, scheduling and on-line proble,s. He has published in journals including OR Letters, SIAM Journal on Computing and SIAM Journal on Discrete Mathematics.</mods:affiliation></affiliation></author><author><name sortKey="Yu, Zhongliang" sort="Yu, Zhongliang" uniqKey="Yu Z" first="Zhongliang" last="Yu">Zhongliang Yu</name><affiliation><mods:affiliation>TU Graz, Institut für Mathematik B, Kopernikusgasse 24, A-8010 Graz, Austria</mods:affiliation></affiliation><affiliation><mods:affiliation>| On leave from the Mathematics Section, Forestry University Nanjing, Nanjing, China.</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="j">Computers and Operations Research</title><title level="j" type="abbrev">CAOR</title><idno type="ISSN">0305-0548</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1995">1995</date><biblScope unit="volume">22</biblScope><biblScope unit="issue">9</biblScope><biblScope unit="page" from="915">915</biblScope><biblScope unit="page" to="920">920</biblScope></imprint><idno type="ISSN">0305-0548</idno></series><idno type="istex">E637099CC8CFB14017DE4194765EE8CD0FAF24D5</idno><idno type="DOI">10.1016/0305-0548(94)00084-L</idno><idno type="PII">0305-0548(94)00084-L</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0305-0548</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">We consider a special case of the precedence constrained scheduling problem of n 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><istex><corpusName>elsevier</corpusName><author><json:item><name>Klaus Jansen</name><affiliations><json:string>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, D-54286 Trier, Germany</json:string><json:string>‡ Klaus Jansen received a diploma degree in Computer Science from the RTWTH Aachen and a Ph.D. degree in computer science—mathematics from the University of Trier, Germany. He is currently Assistant Professor at the University of Trier, Germany. His research interests are in combinatorial optimization, scheduling, high-level synthesis and computational geometry. His publications have appeared in BIT, Commentationes Mathematicae Universitatis Carolinae, Computational Geometry, Computers & Operations Research, Discrete Applied Mathematics, and other Journals.</json:string></affiliations></json:item><json:item><name>Gerhard J. Woeginger</name><affiliations><json:string>To whom all correspondence should be addressed.</json:string><json:string>TU Graz, Institut für Mathematik B, Kopernikusgasse 24, A-8010 Graz, Austria</json:string><json:string>§ Gerhard J. Woeginger received his Ph.D. from the Technical University of Graz in 1990. He is currently Assistant Professor at the Technical University of Graz, Austria. His research interests include combinatorial optimization, scheduling and on-line proble,s. He has published in journals including OR Letters, SIAM Journal on Computing and SIAM Journal on Discrete Mathematics.</json:string></affiliations></json:item><json:item><name>Zhongliang Yu</name><affiliations><json:string>TU Graz, Institut für Mathematik B, Kopernikusgasse 24, A-8010 Graz, Austria</json:string><json:string>| On leave from the Mathematics Section, Forestry University Nanjing, Nanjing, China.</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><originalGenre><json:string>Full-length article</json:string></originalGenre><abstract>We consider a special case of the precedence constrained scheduling problem of n 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.</abstract><qualityIndicators><score>4.095</score><pdfVersion>1.2</pdfVersion><pdfPageSize>540 x 792 pts</pdfPageSize><refBibsNative>true</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>385</abstractCharCount><pdfWordCount>3363</pdfWordCount><pdfCharCount>17016</pdfCharCount><pdfPageCount>6</pdfPageCount><abstractWordCount>61</abstractWordCount></qualityIndicators><title>UET-scheduling with chain-type precedence constraints</title><pii><json:string>0305-0548(94)00084-L</json:string></pii><refBibs><json:item><host><author></author><title>Computers and Intractability: A Guide to the Theory of NP-Completeness</title></host></json:item><json:item><author><json:item><name>M. Fuji</name></json:item><json:item><name>T. Kasami</name></json:item><json:item><name>K. Ninomiya</name></json:item></author><host><volume>17</volume><pages><last>789</last><first>784</first></pages><author></author><title>SIAM J. Appl. Math.</title></host><title>Optimal sequencing of two equivalent processors</title></json:item><json:item><host><author></author><title>Erratum</title></host></json:item><json:item><author><json:item><name>R.S. Chang</name></json:item><json:item><name>R.C.T. Lee</name></json:item></author><host><volume>5</volume><pages><last>478</last><first>471</first></pages><author></author><title>Comput. Opns Res.</title></host><title>On a scheduling problem where a job can be executed only by a limited number of processors</title></json:item><json:item><author><json:item><name>T.-H. Lai</name></json:item><json:item><name>S. Sahni</name></json:item></author><host><volume>4</volume><pages><last>362</last><first>353</first></pages><author></author><title>J. Algorithms</title></host><title>Nearly on-line scheduling of multiprocessor systems with memories</title></json:item><json:item><author><json:item><name>H. Kellerer</name></json:item><json:item><name>G.J. Woeginger</name></json:item></author><host><volume>19</volume><pages><last>8</last><first>1</first></pages><author></author><title>Comput. Ops Res.</title></host><title>UET-Scheduling with constrained processor allocations</title></json:item><json:item><author><json:item><name>K. Jansen</name></json:item></author><host><volume>20</volume><pages><last>595</last><first>587</first></pages><author></author><title>Comput. Ops Res.</title></host><title>Scheduling with constrained processor allocation for interval orders</title></json:item><json:item><author><json:item><name>J. Blaźewicz</name></json:item><json:item><name>W. Cellary</name></json:item><json:item><name>R. Slowinski</name></json:item><json:item><name>J. Weglarz</name></json:item></author><host><volume>7</volume><author></author><title>Ann. OR</title></host><title>Scheduling under resource constraints</title></json:item></refBibs><genre><json:string>research-article</json:string></genre><host><volume>22</volume><pii><json:string>S0305-0548(00)X0010-X</json:string></pii><pages><last>920</last><first>915</first></pages><issn><json:string>0305-0548</json:string></issn><issue>9</issue><genre><json:string>journal</json:string></genre><language><json:string>unknown</json:string></language><title>Computers and Operations Research</title><publicationDate>1995</publicationDate></host><categories><wos><json:string>science</json:string><json:string>operations research & management science</json:string><json:string>engineering, industrial</json:string><json:string>computer science, interdisciplinary applications</json:string></wos><scienceMetrix><json:string>applied sciences</json:string><json:string>engineering</json:string><json:string>operations research</json:string></scienceMetrix></categories><publicationDate>1995</publicationDate><copyrightDate>1995</copyrightDate><doi><json:string>10.1016/0305-0548(94)00084-L</json:string></doi><id>E637099CC8CFB14017DE4194765EE8CD0FAF24D5</id><score>0.6610835</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/E637099CC8CFB14017DE4194765EE8CD0FAF24D5/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/E637099CC8CFB14017DE4194765EE8CD0FAF24D5/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/E637099CC8CFB14017DE4194765EE8CD0FAF24D5/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a">UET-scheduling with chain-type precedence constraints</title></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>ELSEVIER</publisher><availability><p>ELSEVIER</p></availability><date>1995</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a">UET-scheduling with chain-type precedence constraints</title><author xml:id="author-1"><persName><forename type="first">Klaus</forename><surname>Jansen</surname></persName><affiliation>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, D-54286 Trier, Germany</affiliation><affiliation>‡ Klaus Jansen received a diploma degree in Computer Science from the RTWTH Aachen and a Ph.D. degree in computer science—mathematics from the University of Trier, Germany. He is currently Assistant Professor at the University of Trier, Germany. His research interests are in combinatorial optimization, scheduling, high-level synthesis and computational geometry. His publications have appeared in BIT, Commentationes Mathematicae Universitatis Carolinae, Computational Geometry, Computers & Operations Research, Discrete Applied Mathematics, and other Journals.</affiliation></author><author xml:id="author-2"><persName><forename type="first">Gerhard J.</forename><surname>Woeginger</surname></persName><affiliation>To whom all correspondence should be addressed.</affiliation><affiliation>TU Graz, Institut für Mathematik B, Kopernikusgasse 24, A-8010 Graz, Austria</affiliation><affiliation>§ Gerhard J. Woeginger received his Ph.D. from the Technical University of Graz in 1990. He is currently Assistant Professor at the Technical University of Graz, Austria. His research interests include combinatorial optimization, scheduling and on-line proble,s. He has published in journals including OR Letters, SIAM Journal on Computing and SIAM Journal on Discrete Mathematics.</affiliation></author><author xml:id="author-3"><persName><forename type="first">Zhongliang</forename><surname>Yu</surname></persName><affiliation>TU Graz, Institut für Mathematik B, Kopernikusgasse 24, A-8010 Graz, Austria</affiliation><affiliation>| On leave from the Mathematics Section, Forestry University Nanjing, Nanjing, China.</affiliation></author></analytic><monogr><title level="j">Computers and Operations Research</title><title level="j" type="abbrev">CAOR</title><idno type="pISSN">0305-0548</idno><idno type="PII">S0305-0548(00)X0010-X</idno><imprint><publisher>ELSEVIER</publisher><date type="published" when="1995"></date><biblScope unit="volume">22</biblScope><biblScope unit="issue">9</biblScope><biblScope unit="page" from="915">915</biblScope><biblScope unit="page" to="920">920</biblScope></imprint></monogr><idno type="istex">E637099CC8CFB14017DE4194765EE8CD0FAF24D5</idno><idno type="DOI">10.1016/0305-0548(94)00084-L</idno><idno type="PII">0305-0548(94)00084-L</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>1995</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>We consider a special case of the precedence constrained scheduling problem of n 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.</p></abstract></profileDesc><revisionDesc><change when="1995">Published</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/E637099CC8CFB14017DE4194765EE8CD0FAF24D5/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Elsevier, elements deleted: tail"><istex:xmlDeclaration>version="1.0" encoding="utf-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//ES//DTD journal article DTD version 4.5.2//EN//XML" URI="art452.dtd" name="istex:docType"></istex:docType><istex:document><converted-article version="4.5.2" docsubtype="fla"><item-info><jid>CAOR</jid><aid>9400084L</aid><ce:pii>0305-0548(94)00084-L</ce:pii><ce:doi>10.1016/0305-0548(94)00084-L</ce:doi><ce:copyright type="unknown" year="1995"></ce:copyright></item-info><head><ce:title>UET-scheduling with chain-type precedence constraints</ce:title><ce:author-group><ce:author><ce:given-name>Klaus</ce:given-name><ce:surname>Jansen</ce:surname><ce:cross-ref refid="AFF1"><ce:sup>1</ce:sup></ce:cross-ref><ce:cross-ref refid="FN1"><ce:sup>‡</ce:sup></ce:cross-ref></ce:author><ce:author><ce:given-name>Gerhard J.</ce:given-name><ce:surname>Woeginger</ce:surname><ce:cross-ref refid="COR1"><ce:sup>†</ce:sup></ce:cross-ref><ce:cross-ref refid="AFF2"><ce:sup>2</ce:sup></ce:cross-ref><ce:cross-ref refid="FN2"><ce:sup>§</ce:sup></ce:cross-ref></ce:author><ce:author><ce:given-name>Zhongliang</ce:given-name><ce:surname>Yu</ce:surname><ce:cross-ref refid="AFF2"><ce:sup>2</ce:sup></ce:cross-ref><ce:cross-ref refid="FN3"><ce:sup>|</ce:sup></ce:cross-ref><ce:cross-ref refid="FN4"><ce:sup>¶</ce:sup></ce:cross-ref></ce:author><ce:affiliation id="AFF1"><ce:label>a</ce:label><ce:textfn>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, D-54286 Trier, Germany</ce:textfn></ce:affiliation><ce:affiliation id="AFF2"><ce:label>b</ce:label><ce:textfn>TU Graz, Institut für Mathematik B, Kopernikusgasse 24, A-8010 Graz, Austria</ce:textfn></ce:affiliation><ce:correspondence id="COR1"><ce:label>†</ce:label><ce:text>To whom all correspondence should be addressed.</ce:text></ce:correspondence><ce:footnote id="FN1"><ce:label>‡</ce:label><ce:note-para>Klaus Jansen received a diploma degree in Computer Science from the RTWTH Aachen and a Ph.D. degree in computer science—mathematics from the University of Trier, Germany. He is currently Assistant Professor at the University of Trier, Germany. His research interests are in combinatorial optimization, scheduling, high-level synthesis and computational geometry. His publications have appeared in BIT, Commentationes Mathematicae Universitatis Carolinae, Computational Geometry, Computers & Operations Research, Discrete Applied Mathematics, and other Journals.</ce:note-para></ce:footnote><ce:footnote id="FN2"><ce:label>§</ce:label><ce:note-para>Gerhard J. Woeginger received his Ph.D. from the Technical University of Graz in 1990. He is currently Assistant Professor at the Technical University of Graz, Austria. His research interests include combinatorial optimization, scheduling and on-line proble,s. He has published in journals including OR Letters, SIAM Journal on Computing and SIAM Journal on Discrete Mathematics.</ce:note-para></ce:footnote><ce:footnote id="FN3"><ce:label>|</ce:label><ce:note-para>On leave from the Mathematics Section, Forestry University Nanjing, Nanjing, China.</ce:note-para></ce:footnote><ce:footnote id="FN4"><ce:label>¶</ce:label><ce:note-para>Zhongliang Yu received a diploma degree in Mathematics from the Forestry University Nanjing, China. He is currently working on his Ph.D. thesis at the Technical University of Graz, Austria. His publications have appeared in journals including Computing and Information Processing Letters.</ce:note-para></ce:footnote></ce:author-group><ce:abstract><ce:section-title>Abstract</ce:section-title><ce:abstract-sec><ce:simple-para>We consider a special case of the precedence constrained scheduling problem of <ce:italic>n</ce:italic> 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.</ce:simple-para></ce:abstract-sec></ce:abstract></head></converted-article></istex:document></istex:metadataXml><mods version="3.6"><titleInfo><title>UET-scheduling with chain-type precedence constraints</title></titleInfo><titleInfo type="alternative" contentType="CDATA"><title>UET-scheduling with chain-type precedence constraints</title></titleInfo><name type="personal"><namePart type="given">Klaus</namePart><namePart type="family">Jansen</namePart><affiliation>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, D-54286 Trier, Germany</affiliation><affiliation>‡ Klaus Jansen received a diploma degree in Computer Science from the RTWTH Aachen and a Ph.D. degree in computer science—mathematics from the University of Trier, Germany. He is currently Assistant Professor at the University of Trier, Germany. His research interests are in combinatorial optimization, scheduling, high-level synthesis and computational geometry. His publications have appeared in BIT, Commentationes Mathematicae Universitatis Carolinae, Computational Geometry, Computers & Operations Research, Discrete Applied Mathematics, and other Journals.</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Gerhard J.</namePart><namePart type="family">Woeginger</namePart><affiliation>To whom all correspondence should be addressed.</affiliation><affiliation>TU Graz, Institut für Mathematik B, Kopernikusgasse 24, A-8010 Graz, Austria</affiliation><affiliation>§ Gerhard J. Woeginger received his Ph.D. from the Technical University of Graz in 1990. He is currently Assistant Professor at the Technical University of Graz, Austria. His research interests include combinatorial optimization, scheduling and on-line proble,s. He has published in journals including OR Letters, SIAM Journal on Computing and SIAM Journal on Discrete Mathematics.</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Zhongliang</namePart><namePart type="family">Yu</namePart><affiliation>TU Graz, Institut für Mathematik B, Kopernikusgasse 24, A-8010 Graz, Austria</affiliation><affiliation>| On leave from the Mathematics Section, Forestry University Nanjing, Nanjing, China.</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="research-article" displayLabel="Full-length article"></genre><originInfo><publisher>ELSEVIER</publisher><dateIssued encoding="w3cdtf">1995</dateIssued><copyrightDate encoding="w3cdtf">1995</copyrightDate></originInfo><language><languageTerm type="code" authority="iso639-2b">eng</languageTerm><languageTerm type="code" authority="rfc3066">en</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract lang="en">We consider a special case of the precedence constrained scheduling problem of n 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.</abstract><relatedItem type="host"><titleInfo><title>Computers and Operations Research</title></titleInfo><titleInfo type="abbreviated"><title>CAOR</title></titleInfo><genre type="journal">journal</genre><originInfo><dateIssued encoding="w3cdtf">199511</dateIssued></originInfo><identifier type="ISSN">0305-0548</identifier><identifier type="PII">S0305-0548(00)X0010-X</identifier><part><date>199511</date><detail type="volume"><number>22</number><caption>vol.</caption></detail><detail type="issue"><number>9</number><caption>no.</caption></detail><extent unit="issue pages"><start>871</start><end>986</end></extent><extent unit="pages"><start>915</start><end>920</end></extent></part></relatedItem><identifier type="istex">E637099CC8CFB14017DE4194765EE8CD0FAF24D5</identifier><identifier type="DOI">10.1016/0305-0548(94)00084-L</identifier><identifier type="PII">0305-0548(94)00084-L</identifier><recordInfo><recordContentSource>ELSEVIER</recordContentSource></recordInfo></mods></metadata><serie></serie></istex></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Istex/Corpus
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 000A21 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 000A21 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Istex
|étape= Corpus
|type= RBID
|clé= ISTEX:E637099CC8CFB14017DE4194765EE8CD0FAF24D5
|texte= UET-scheduling with chain-type precedence constraints
}}
| This area was generated with Dilib version V0.6.31. |  |