Scheduling with incompatible jobs
Identifieur interne : 001172 ( Istex/Corpus ); précédent : 001171; suivant : 001173Scheduling with incompatible jobs
Auteurs : Hans L. Bodlaender ; Klaus Jansen ; Gerhard J. WoegingerSource :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 1993.
Abstract
Abstract: We consider scheduling problems in a multiprocessor system with incompatible jobs (two incompatible jobs cannot be processed by the same machine). We consider the problem to minimize the maximum job completion time, the makespan. This problem is NP-complete. We present a number of polynomial time approximation algorithms for this problem where the job incompatibilities possess a special structure. As the incompatibilities form a graph on the set of jobs, our algorithms strongly rely on graph theoretic methods. We also solve an open problem by Biró, Hujter and Tuza on coloring precolored bipartite graphs.
Url:
DOI: 10.1007/3-540-56402-0_34
Links to Exploration step
ISTEX:C410D5A7140005B4944F0E030954FA71E173F1ABLe document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Scheduling with incompatible jobs</title><author><name sortKey="Bodlaender, Hans L" sort="Bodlaender, Hans L" uniqKey="Bodlaender H" first="Hans L." last="Bodlaender">Hans L. Bodlaender</name><affiliation><mods:affiliation>Department of Computer Science, Utrecht University, P.O.Box 80.089, 3508, TB Utrecht, The Netherlands</mods:affiliation></affiliation></author><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, W-5500, Trier, Germany</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>Institut für Informationsverarbeitung, TU Graz, Klosterwiesgasse 32, A-8010, Graz, Austria</mods:affiliation></affiliation></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:C410D5A7140005B4944F0E030954FA71E173F1AB</idno><date when="1993" year="1993">1993</date><idno type="doi">10.1007/3-540-56402-0_34</idno><idno type="url">https://api.istex.fr/document/C410D5A7140005B4944F0E030954FA71E173F1AB/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001172</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001172</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Scheduling with incompatible jobs</title><author><name sortKey="Bodlaender, Hans L" sort="Bodlaender, Hans L" uniqKey="Bodlaender H" first="Hans L." last="Bodlaender">Hans L. Bodlaender</name><affiliation><mods:affiliation>Department of Computer Science, Utrecht University, P.O.Box 80.089, 3508, TB Utrecht, The Netherlands</mods:affiliation></affiliation></author><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, W-5500, Trier, Germany</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>Institut für Informationsverarbeitung, TU Graz, Klosterwiesgasse 32, A-8010, Graz, Austria</mods:affiliation></affiliation></author></analytic><monogr></monogr><series><title level="s">Lecture Notes in Computer Science</title><imprint><date>1993</date></imprint><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series><idno type="istex">C410D5A7140005B4944F0E030954FA71E173F1AB</idno><idno type="DOI">10.1007/3-540-56402-0_34</idno><idno type="ChapterID">5</idno><idno type="ChapterID">Chap5</idno></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass><langUsage><language ident="en">en</language></langUsage></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: We consider scheduling problems in a multiprocessor system with incompatible jobs (two incompatible jobs cannot be processed by the same machine). We consider the problem to minimize the maximum job completion time, the makespan. This problem is NP-complete. We present a number of polynomial time approximation algorithms for this problem where the job incompatibilities possess a special structure. As the incompatibilities form a graph on the set of jobs, our algorithms strongly rely on graph theoretic methods. We also solve an open problem by Biró, Hujter and Tuza on coloring precolored bipartite graphs.</div></front></TEI><istex><corpusName>springer</corpusName><author><json:item><name>Hans L. Bodlaender</name><affiliations><json:string>Department of Computer Science, Utrecht University, P.O.Box 80.089, 3508, TB Utrecht, The Netherlands</json:string></affiliations></json:item><json:item><name>Klaus Jansen</name><affiliations><json:string>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, W-5500, Trier, Germany</json:string></affiliations></json:item><json:item><name>Gerhard J. Woeginger</name><affiliations><json:string>Institut für Informationsverarbeitung, TU Graz, Klosterwiesgasse 32, A-8010, Graz, Austria</json:string></affiliations></json:item></author><language><json:string>eng</json:string></language><originalGenre><json:string>ReviewPaper</json:string></originalGenre><abstract>Abstract: We consider scheduling problems in a multiprocessor system with incompatible jobs (two incompatible jobs cannot be processed by the same machine). We consider the problem to minimize the maximum job completion time, the makespan. This problem is NP-complete. We present a number of polynomial time approximation algorithms for this problem where the job incompatibilities possess a special structure. As the incompatibilities form a graph on the set of jobs, our algorithms strongly rely on graph theoretic methods. We also solve an open problem by Biró, Hujter and Tuza on coloring precolored bipartite graphs.</abstract><qualityIndicators><score>6.128</score><pdfVersion>1.3</pdfVersion><pdfPageSize>439.136 x 666 pts</pdfPageSize><refBibsNative>false</refBibsNative><keywordCount>0</keywordCount><abstractCharCount>621</abstractCharCount><pdfWordCount>6643</pdfWordCount><pdfCharCount>27833</pdfCharCount><pdfPageCount>13</pdfPageCount><abstractWordCount>94</abstractWordCount></qualityIndicators><title>Scheduling with incompatible jobs</title><chapterId><json:string>5</json:string><json:string>Chap5</json:string></chapterId><refBibs><json:item><host><author><json:item><name> Lemma2</name></json:item><json:item><name>T = ( V Let</name></json:item></author><title>E) be a tree, let vt,...,vk be k > 3 vertices in V. Then 1-PREXT can be</title></host></json:item><json:item><author><json:item><name>B Bird</name></json:item><json:item><name>M Hujter</name></json:item><json:item><name>Z Tuza</name></json:item></author><host><author></author><title>Disc. Math</title></host><title>Precoloring extension. I. Interval graphs</title></json:item><json:item><host><author><json:item><name>H,L Bodlaender</name></json:item><json:item><name>K Jansen</name></json:item></author><title>Restrictions of graph partition problems. Part I</title><publicationDate>1991</publicationDate></host></json:item><json:item><author><json:item><name>H,L Bodlaender</name></json:item><json:item><name>T Kloks</name></json:item></author><host><pages><last>555</last><first>544</first></pages><author></author><title>Proc. 18th ICALP</title><publicationDate>1991</publicationDate></host><title>Better algorithms for the pathwidth and treewidth of graphs</title><publicationDate>1991</publicationDate></json:item><json:item><author><json:item><name>M,L Fisher</name></json:item></author><host><volume>26</volume><pages><last>17</last><first>1</first></pages><author></author><title>Management.Sci</title><publicationDate>1980</publicationDate></host><title>Worst-case analysis of heuristic algorithms</title><publicationDate>1980</publicationDate></json:item><json:item><author><json:item><name>S Garey</name></json:item><json:item><name>M,R Graham</name></json:item><json:item><name>R,L Johnson</name></json:item><json:item><name>D,S </name></json:item></author><host><volume>26</volume><pages><last>21</last><first>3</first></pages><author></author><title>Operations Research</title><publicationDate>1978</publicationDate></host><title>Performance guarantees for scheduling algorithms</title><publicationDate>1978</publicationDate></json:item><json:item><host><author><json:item><name>M,R Garey</name></json:item><json:item><name>D,S Johnson</name></json:item></author><title>Computers and Intractability: A Guide to the Theory of NP-Completeness</title><publicationDate>1979</publicationDate></host></json:item><json:item><author><json:item><name>R,L Graham</name></json:item></author><host><volume>45</volume><pages><last>1581</last><first>1563</first></pages><issue>9</issue><author></author><title>Bell Syst. Tech. J</title><publicationDate>1966</publicationDate></host><title>Bounds for certain multiprocessing anomalies</title><publicationDate>1966</publicationDate></json:item><json:item><author><json:item><name>R,L Graham</name></json:item></author><host><volume>17</volume><pages><last>269</last><first>263</first></pages><author></author><title>SIAM J. Appl. Math</title><publicationDate>1969</publicationDate></host><title>Bounds on multiprocessing timing anomahes</title><publicationDate>1969</publicationDate></json:item><json:item><author><json:item><name>D,S Hochbaum</name></json:item><json:item><name>D,B Shmoys</name></json:item></author><host><volume>34</volume><pages><last>162</last><first>144</first></pages><author></author><title>J. ACM</title><publicationDate>1987</publicationDate></host><title>Using dual approximation algorithms for scheduling problems: Theoretical and practical results</title><publicationDate>1987</publicationDate></json:item><json:item><author><json:item><name>M Hujter</name></json:item><json:item><name>Z Tuza</name></json:item></author><host><author></author><title>J. Graph Theory</title></host><title>Precoloring extension. II. Graph classes related to bipartite graphs</title></json:item><json:item><host><author><json:item><name>K Jansen</name></json:item><json:item><name>P Schemer</name></json:item></author><title>Generahzed coloring for tree-like graphs</title><publicationDate>1992</publicationDate></host></json:item><json:item><author><json:item><name>C,Y Lee</name></json:item></author><host><volume>30</volume><pages><last>61</last><first>53</first></pages><author></author><title>Disc. Appl. Math</title><publicationDate>1991</publicationDate></host><title>Parallel machines scheduling with nonsimultaneous machine available time</title><publicationDate>1991</publicationDate></json:item><json:item><author><json:item><name>N Linial</name></json:item><json:item><name>U Vazirani</name></json:item></author><host><pages><last>128</last><first>124</first></pages><author></author><title>FOCS</title><publicationDate>1989</publicationDate></host><title>Graph products and chromatic numbers</title><publicationDate>1989</publicationDate></json:item></refBibs><genre><json:string>conference</json:string></genre><serie><editor><json:item><name>Gerhard Goos</name></json:item><json:item><name>Juris Hartmanis</name></json:item></editor><issn><json:string>0302-9743</json:string></issn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Lecture Notes in Computer Science</title><copyrightDate>1993</copyrightDate></serie><host><editor><json:item><name>Ernst W. Mayr</name></json:item></editor><subject><json:item><value>Computer Science</value></json:item><json:item><value>Computer Science</value></json:item><json:item><value>Algorithm Analysis and Problem Complexity</value></json:item><json:item><value>Combinatorics</value></json:item><json:item><value>Computation by Abstract Devices</value></json:item><json:item><value>Logics and Meanings of Programs</value></json:item><json:item><value>Mathematical Logic and Formal Languages</value></json:item><json:item><value>Data Structures</value></json:item></subject><isbn><json:string>978-3-540-56402-7</json:string></isbn><language><json:string>unknown</json:string></language><eissn><json:string>1611-3349</json:string></eissn><title>Graph-Theoretic Concepts in Computer Science</title><bookId><json:string>3540564020</json:string></bookId><volume>657</volume><pages><last>49</last><first>37</first></pages><issn><json:string>0302-9743</json:string></issn><genre><json:string>book-series</json:string></genre><eisbn><json:string>978-3-540-47554-5</json:string></eisbn><copyrightDate>1993</copyrightDate><doi><json:string>10.1007/3-540-56402-0</json:string></doi></host><publicationDate>2005</publicationDate><copyrightDate>1993</copyrightDate><doi><json:string>10.1007/3-540-56402-0_34</json:string></doi><id>C410D5A7140005B4944F0E030954FA71E173F1AB</id><score>0.3831391</score><fulltext><json:item><extension>pdf</extension><original>true</original><mimetype>application/pdf</mimetype><uri>https://api.istex.fr/document/C410D5A7140005B4944F0E030954FA71E173F1AB/fulltext/pdf</uri></json:item><json:item><extension>zip</extension><original>false</original><mimetype>application/zip</mimetype><uri>https://api.istex.fr/document/C410D5A7140005B4944F0E030954FA71E173F1AB/fulltext/zip</uri></json:item><istex:fulltextTEI uri="https://api.istex.fr/document/C410D5A7140005B4944F0E030954FA71E173F1AB/fulltext/tei"><teiHeader><fileDesc><titleStmt><title level="a" type="main" xml:lang="en">Scheduling with incompatible jobs</title><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt><respStmt><resp>Références bibliographiques récupérées via GROBID</resp><name resp="ISTEX-API">ISTEX-API (INIST-CNRS)</name></respStmt></titleStmt><publicationStmt><authority>ISTEX</authority><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><availability><p>Springer-Verlag, 1993</p></availability><date>1993</date></publicationStmt><sourceDesc><biblStruct type="inbook"><analytic><title level="a" type="main" xml:lang="en">Scheduling with incompatible jobs</title><author xml:id="author-1"><persName><forename type="first">Hans</forename><surname>Bodlaender</surname></persName><affiliation>Department of Computer Science, Utrecht University, P.O.Box 80.089, 3508, TB Utrecht, The Netherlands</affiliation></author><author xml:id="author-2"><persName><forename type="first">Klaus</forename><surname>Jansen</surname></persName><affiliation>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, W-5500, Trier, Germany</affiliation></author><author xml:id="author-3"><persName><forename type="first">Gerhard</forename><surname>Woeginger</surname></persName><affiliation>Institut für Informationsverarbeitung, TU Graz, Klosterwiesgasse 32, A-8010, Graz, Austria</affiliation></author></analytic><monogr><title level="m">Graph-Theoretic Concepts in Computer Science</title><title level="m" type="sub">18th International Workshop, WG '92 Wiesbaden-Naurod, Germany, June 18–20, 1992 Proceedings</title><idno type="pISBN">978-3-540-56402-7</idno><idno type="eISBN">978-3-540-47554-5</idno><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="DOI">10.1007/3-540-56402-0</idno><idno type="book-ID">3540564020</idno><idno type="book-title-ID">33741</idno><idno type="book-volume-number">657</idno><idno type="book-chapter-count">29</idno><editor><persName><forename type="first">Ernst</forename><forename type="first">W.</forename><surname>Mayr</surname></persName></editor><imprint><publisher>Springer Berlin Heidelberg</publisher><pubPlace>Berlin, Heidelberg</pubPlace><date type="published" when="2005-06-04"></date><biblScope unit="volume">657</biblScope><biblScope unit="page" from="37">37</biblScope><biblScope unit="page" to="49">49</biblScope></imprint></monogr><series><title level="s">Lecture Notes in Computer Science</title><editor><persName><forename type="first">Gerhard</forename><surname>Goos</surname></persName></editor><editor><persName><forename type="first">Juris</forename><surname>Hartmanis</surname></persName></editor><biblScope><date>1993</date></biblScope><idno type="pISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="series-Id">558</idno></series><idno type="istex">C410D5A7140005B4944F0E030954FA71E173F1AB</idno><idno type="DOI">10.1007/3-540-56402-0_34</idno><idno type="ChapterID">5</idno><idno type="ChapterID">Chap5</idno></biblStruct></sourceDesc></fileDesc><profileDesc><creation><date>1993</date></creation><langUsage><language ident="en">en</language></langUsage><abstract xml:lang="en"><p>Abstract: We consider scheduling problems in a multiprocessor system with incompatible jobs (two incompatible jobs cannot be processed by the same machine). We consider the problem to minimize the maximum job completion time, the makespan. This problem is NP-complete. We present a number of polynomial time approximation algorithms for this problem where the job incompatibilities possess a special structure. As the incompatibilities form a graph on the set of jobs, our algorithms strongly rely on graph theoretic methods. We also solve an open problem by Biró, Hujter and Tuza on coloring precolored bipartite graphs.</p></abstract><textClass><keywords scheme="Book-Subject-Collection"><list><label>SUCO11645</label><item><term>Computer Science</term></item></list></keywords></textClass><textClass><keywords scheme="Book-Subject-Group"><list><label>I</label><label>I16021</label><label>M17009</label><label>I16013</label><label>I1603X</label><label>I16048</label><label>I15017</label><item><term>Computer Science</term></item><item><term>Algorithm Analysis and Problem Complexity</term></item><item><term>Combinatorics</term></item><item><term>Computation by Abstract Devices</term></item><item><term>Logics and Meanings of Programs</term></item><item><term>Mathematical Logic and Formal Languages</term></item><item><term>Data Structures</term></item></list></keywords></textClass></profileDesc><revisionDesc><change when="2005-06-04">Published</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2016-11-22">References added</change><change xml:id="refBibs-istex" who="#ISTEX-API" when="2017-01-20">References added</change></revisionDesc></teiHeader></istex:fulltextTEI><json:item><extension>txt</extension><original>false</original><mimetype>text/plain</mimetype><uri>https://api.istex.fr/document/C410D5A7140005B4944F0E030954FA71E173F1AB/fulltext/txt</uri></json:item></fulltext><metadata><istex:metadataXml wicri:clean="Springer, Publisher found" wicri:toSee="no header"><istex:xmlDeclaration>version="1.0" encoding="UTF-8"</istex:xmlDeclaration><istex:docType PUBLIC="-//Springer-Verlag//DTD A++ V2.4//EN" URI="http://devel.springer.de/A++/V2.4/DTD/A++V2.4.dtd" name="istex:docType"></istex:docType><istex:document><Publisher><PublisherInfo><PublisherName>Springer Berlin Heidelberg</PublisherName><PublisherLocation>Berlin, Heidelberg</PublisherLocation></PublisherInfo><Series><SeriesInfo TocLevels="0"><SeriesID>558</SeriesID><SeriesPrintISSN>0302-9743</SeriesPrintISSN><SeriesElectronicISSN>1611-3349</SeriesElectronicISSN><SeriesTitle Language="En">Lecture Notes in Computer Science</SeriesTitle><SeriesAbbreviatedTitle>Lect Notes Comput Sci</SeriesAbbreviatedTitle></SeriesInfo><SeriesHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><FamilyName>Goos</FamilyName></EditorName></Editor><Editor><EditorName DisplayOrder="Western"><GivenName>Juris</GivenName><FamilyName>Hartmanis</FamilyName></EditorName></Editor></EditorGroup></SeriesHeader><Book Language="En"><BookInfo MediaType="eBook" Language="En" BookProductType="Proceedings" TocLevels="0" NumberingStyle="Unnumbered"><BookID>3540564020</BookID><BookTitle>Graph-Theoretic Concepts in Computer Science</BookTitle><BookSubTitle>18th International Workshop, WG '92 Wiesbaden-Naurod, Germany, June 18–20, 1992 Proceedings</BookSubTitle><BookVolumeNumber>657</BookVolumeNumber><BookDOI>10.1007/3-540-56402-0</BookDOI><BookTitleID>33741</BookTitleID><BookPrintISBN>978-3-540-56402-7</BookPrintISBN><BookElectronicISBN>978-3-540-47554-5</BookElectronicISBN><BookChapterCount>29</BookChapterCount><BookCopyright><CopyrightHolderName>Springer-Verlag</CopyrightHolderName><CopyrightYear>1993</CopyrightYear></BookCopyright><BookSubjectGroup><BookSubject Code="I" Type="Primary">Computer Science</BookSubject><BookSubject Code="I16021" Priority="1" Type="Secondary">Algorithm Analysis and Problem Complexity</BookSubject><BookSubject Code="M17009" Priority="2" Type="Secondary">Combinatorics</BookSubject><BookSubject Code="I16013" Priority="3" Type="Secondary">Computation by Abstract Devices</BookSubject><BookSubject Code="I1603X" Priority="4" Type="Secondary">Logics and Meanings of Programs</BookSubject><BookSubject Code="I16048" Priority="5" Type="Secondary">Mathematical Logic and Formal Languages</BookSubject><BookSubject Code="I15017" Priority="6" Type="Secondary">Data Structures</BookSubject><SubjectCollection Code="SUCO11645">Computer Science</SubjectCollection></BookSubjectGroup></BookInfo><BookHeader><EditorGroup><Editor><EditorName DisplayOrder="Western"><GivenName>Ernst</GivenName><GivenName>W.</GivenName><FamilyName>Mayr</FamilyName></EditorName></Editor></EditorGroup></BookHeader><Chapter ID="Chap5" Language="En"><ChapterInfo ChapterType="ReviewPaper" NumberingStyle="Unnumbered" TocLevels="0" ContainsESM="No"><ChapterID>5</ChapterID><ChapterDOI>10.1007/3-540-56402-0_34</ChapterDOI><ChapterSequenceNumber>5</ChapterSequenceNumber><ChapterTitle Language="En">Scheduling with incompatible jobs</ChapterTitle><ChapterFirstPage>37</ChapterFirstPage><ChapterLastPage>49</ChapterLastPage><ChapterCopyright><CopyrightHolderName>Springer-Verlag</CopyrightHolderName><CopyrightYear>1993</CopyrightYear></ChapterCopyright><ChapterHistory><OnlineDate><Year>2005</Year><Month>6</Month><Day>4</Day></OnlineDate></ChapterHistory><ChapterGrants Type="Regular"><MetadataGrant Grant="OpenAccess"></MetadataGrant><AbstractGrant Grant="OpenAccess"></AbstractGrant><BodyPDFGrant Grant="Restricted"></BodyPDFGrant><BodyHTMLGrant Grant="Restricted"></BodyHTMLGrant><BibliographyGrant Grant="Restricted"></BibliographyGrant><ESMGrant Grant="Restricted"></ESMGrant></ChapterGrants><ChapterContext><SeriesID>558</SeriesID><BookID>3540564020</BookID><BookTitle>Graph-Theoretic Concepts in Computer Science</BookTitle></ChapterContext></ChapterInfo><ChapterHeader><AuthorGroup><Author AffiliationIDS="Aff1"><AuthorName DisplayOrder="Western"><GivenName>Hans</GivenName><GivenName>L.</GivenName><FamilyName>Bodlaender</FamilyName></AuthorName></Author><Author AffiliationIDS="Aff2"><AuthorName DisplayOrder="Western"><GivenName>Klaus</GivenName><FamilyName>Jansen</FamilyName></AuthorName></Author><Author AffiliationIDS="Aff3"><AuthorName DisplayOrder="Western"><GivenName>Gerhard</GivenName><GivenName>J.</GivenName><FamilyName>Woeginger</FamilyName></AuthorName></Author><Affiliation ID="Aff1"><OrgDivision>Department of Computer Science</OrgDivision><OrgName>Utrecht University</OrgName><OrgAddress><Postbox>P.O.Box 80.089</Postbox><Postcode>3508</Postcode><City>TB Utrecht</City><Country>The Netherlands</Country></OrgAddress></Affiliation><Affiliation ID="Aff2"><OrgDivision>Fachbereich IV, Mathematik und Informatik</OrgDivision><OrgName>Universität Trier</OrgName><OrgAddress><Postbox>Postfach 3825</Postbox><Postcode>W-5500</Postcode><City>Trier</City><Country>Germany</Country></OrgAddress></Affiliation><Affiliation ID="Aff3"><OrgDivision>Institut für Informationsverarbeitung</OrgDivision><OrgName>TU Graz</OrgName><OrgAddress><Street>Klosterwiesgasse 32</Street><Postcode>A-8010</Postcode><City>Graz</City><Country>Austria</Country></OrgAddress></Affiliation></AuthorGroup><Abstract ID="Abs1" Language="En"><Heading>Abstract</Heading><Para>We consider scheduling problems in a multiprocessor system with incompatible jobs (two incompatible jobs cannot be processed by the same machine). We consider the problem to minimize the maximum job completion time, the makespan. This problem is NP-complete.</Para><Para>We present a number of polynomial time approximation algorithms for this problem where the job incompatibilities possess a special structure. As the incompatibilities form a graph on the set of jobs, our algorithms strongly rely on graph theoretic methods. We also solve an open problem by Biró, Hujter and Tuza on coloring precolored bipartite graphs.</Para></Abstract></ChapterHeader><NoBody></NoBody></Chapter></Book></Series></Publisher></istex:document></istex:metadataXml><mods version="3.6"><titleInfo lang="en"><title>Scheduling with incompatible jobs</title></titleInfo><titleInfo type="alternative" contentType="CDATA" lang="en"><title>Scheduling with incompatible jobs</title></titleInfo><name type="personal"><namePart type="given">Hans</namePart><namePart type="given">L.</namePart><namePart type="family">Bodlaender</namePart><affiliation>Department of Computer Science, Utrecht University, P.O.Box 80.089, 3508, TB Utrecht, The Netherlands</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Klaus</namePart><namePart type="family">Jansen</namePart><affiliation>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, W-5500, Trier, Germany</affiliation><role><roleTerm type="text">author</roleTerm></role></name><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="given">J.</namePart><namePart type="family">Woeginger</namePart><affiliation>Institut für Informationsverarbeitung, TU Graz, Klosterwiesgasse 32, A-8010, Graz, Austria</affiliation><role><roleTerm type="text">author</roleTerm></role></name><typeOfResource>text</typeOfResource><genre type="conference" displayLabel="ReviewPaper"></genre><originInfo><publisher>Springer Berlin Heidelberg</publisher><place><placeTerm type="text">Berlin, Heidelberg</placeTerm></place><dateIssued encoding="w3cdtf">2005-06-04</dateIssued><copyrightDate encoding="w3cdtf">1993</copyrightDate></originInfo><language><languageTerm type="code" authority="rfc3066">en</languageTerm><languageTerm type="code" authority="iso639-2b">eng</languageTerm></language><physicalDescription><internetMediaType>text/html</internetMediaType></physicalDescription><abstract lang="en">Abstract: We consider scheduling problems in a multiprocessor system with incompatible jobs (two incompatible jobs cannot be processed by the same machine). We consider the problem to minimize the maximum job completion time, the makespan. This problem is NP-complete. We present a number of polynomial time approximation algorithms for this problem where the job incompatibilities possess a special structure. As the incompatibilities form a graph on the set of jobs, our algorithms strongly rely on graph theoretic methods. We also solve an open problem by Biró, Hujter and Tuza on coloring precolored bipartite graphs.</abstract><relatedItem type="host"><titleInfo><title>Graph-Theoretic Concepts in Computer Science</title><subTitle>18th International Workshop, WG '92 Wiesbaden-Naurod, Germany, June 18–20, 1992 Proceedings</subTitle></titleInfo><name type="personal"><namePart type="given">Ernst</namePart><namePart type="given">W.</namePart><namePart type="family">Mayr</namePart><role><roleTerm type="text">editor</roleTerm></role></name><genre type="book-series" displayLabel="Proceedings"></genre><originInfo><copyrightDate encoding="w3cdtf">1993</copyrightDate><issuance>monographic</issuance></originInfo><subject><genre>Book-Subject-Collection</genre><topic authority="SpringerSubjectCodes" authorityURI="SUCO11645">Computer Science</topic></subject><subject><genre>Book-Subject-Group</genre><topic authority="SpringerSubjectCodes" authorityURI="I">Computer Science</topic><topic authority="SpringerSubjectCodes" authorityURI="I16021">Algorithm Analysis and Problem Complexity</topic><topic authority="SpringerSubjectCodes" authorityURI="M17009">Combinatorics</topic><topic authority="SpringerSubjectCodes" authorityURI="I16013">Computation by Abstract Devices</topic><topic authority="SpringerSubjectCodes" authorityURI="I1603X">Logics and Meanings of Programs</topic><topic authority="SpringerSubjectCodes" authorityURI="I16048">Mathematical Logic and Formal Languages</topic><topic authority="SpringerSubjectCodes" authorityURI="I15017">Data Structures</topic></subject><identifier type="DOI">10.1007/3-540-56402-0</identifier><identifier type="ISBN">978-3-540-56402-7</identifier><identifier type="eISBN">978-3-540-47554-5</identifier><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="BookTitleID">33741</identifier><identifier type="BookID">3540564020</identifier><identifier type="BookChapterCount">29</identifier><identifier type="BookVolumeNumber">657</identifier><part><date>1993</date><detail type="volume"><number>657</number><caption>vol.</caption></detail><extent unit="pages"><start>37</start><end>49</end></extent></part><recordInfo><recordOrigin>Springer-Verlag, 1993</recordOrigin></recordInfo></relatedItem><relatedItem type="series"><titleInfo><title>Lecture Notes in Computer Science</title></titleInfo><name type="personal"><namePart type="given">Gerhard</namePart><namePart type="family">Goos</namePart><role><roleTerm type="text">editor</roleTerm></role></name><name type="personal"><namePart type="given">Juris</namePart><namePart type="family">Hartmanis</namePart><role><roleTerm type="text">editor</roleTerm></role></name><originInfo><copyrightDate encoding="w3cdtf">1993</copyrightDate><issuance>serial</issuance></originInfo><identifier type="ISSN">0302-9743</identifier><identifier type="eISSN">1611-3349</identifier><identifier type="SeriesID">558</identifier><recordInfo><recordOrigin>Springer-Verlag, 1993</recordOrigin></recordInfo></relatedItem><identifier type="istex">C410D5A7140005B4944F0E030954FA71E173F1AB</identifier><identifier type="DOI">10.1007/3-540-56402-0_34</identifier><identifier type="ChapterID">5</identifier><identifier type="ChapterID">Chap5</identifier><accessCondition type="use and reproduction" contentType="copyright">Springer-Verlag, 1993</accessCondition><recordInfo><recordContentSource>SPRINGER</recordContentSource><recordOrigin>Springer-Verlag, 1993</recordOrigin></recordInfo></mods></metadata></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 001172 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Istex/Corpus/biblio.hfd -nk 001172 | 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:C410D5A7140005B4944F0E030954FA71E173F1AB
|texte= Scheduling with incompatible jobs
}}
| This area was generated with Dilib version V0.6.31. |  |