On scheduling problems restricted to interval orders
Identifieur interne : 002C22 ( Main/Exploration ); précédent : 002C21; suivant : 002C23On scheduling problems restricted to interval orders
Auteurs : Klaus Jansen [Allemagne]Source :
- Lecture Notes in Computer Science [ 0302-9743 ] ; 1993.
Abstract
Abstract: In this paper we analyse a scheduling problem where each processor can execute only a subset of all unit-time jobs. We show that this problem is NP-complete even for interval orders. If each job has a specified type and processors can only execute jobs with one type, the problem can be solved in polynomial time. The same holds if the deadline is constant. At last we give a heuristic for the scheduling problem restricted to an interval order with logarithmic approximation bound.
Url:
DOI: 10.1007/3-540-56402-0_33
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001120
- to stream Istex, to step Curation: 001009
- to stream Istex, to step Checkpoint: 001326
- to stream Main, to step Merge: 003173
- to stream Main, to step Curation: 002C22
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">On scheduling problems restricted to interval orders</title><author><name sortKey="Jansen, Klaus" sort="Jansen, Klaus" uniqKey="Jansen K" first="Klaus" last="Jansen">Klaus Jansen</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:47F37255EB68111B87CC2AE071D9F88C94C865FD</idno><date when="1993" year="1993">1993</date><idno type="doi">10.1007/3-540-56402-0_33</idno><idno type="url">https://api.istex.fr/document/47F37255EB68111B87CC2AE071D9F88C94C865FD/fulltext/pdf</idno><idno type="wicri:Area/Istex/Corpus">001120</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001120</idno><idno type="wicri:Area/Istex/Curation">001009</idno><idno type="wicri:Area/Istex/Checkpoint">001326</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001326</idno><idno type="wicri:doubleKey">0302-9743:1993:Jansen K:on:scheduling:problems</idno><idno type="wicri:Area/Main/Merge">003173</idno><idno type="wicri:Area/Main/Curation">002C22</idno><idno type="wicri:Area/Main/Exploration">002C22</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">On scheduling problems restricted to interval orders</title><author><name sortKey="Jansen, Klaus" sort="Jansen, Klaus" uniqKey="Jansen K" first="Klaus" last="Jansen">Klaus Jansen</name><affiliation wicri:level="1"><country xml:lang="fr">Allemagne</country><wicri:regionArea>Fachbereich IV, Mathematik und Informatik, Universität Trier, Postfach 3825, W-5500, Trier</wicri:regionArea><wicri:noRegion>Trier</wicri:noRegion><wicri:noRegion>Trier</wicri:noRegion></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">47F37255EB68111B87CC2AE071D9F88C94C865FD</idno><idno type="DOI">10.1007/3-540-56402-0_33</idno><idno type="ChapterID">4</idno><idno type="ChapterID">Chap4</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: In this paper we analyse a scheduling problem where each processor can execute only a subset of all unit-time jobs. We show that this problem is NP-complete even for interval orders. If each job has a specified type and processors can only execute jobs with one type, the problem can be solved in polynomial time. The same holds if the deadline is constant. At last we give a heuristic for the scheduling problem restricted to an interval order with logarithmic approximation bound.</div></front></TEI><affiliations><list><country><li>Allemagne</li></country></list><tree><country name="Allemagne"><noRegion><name sortKey="Jansen, Klaus" sort="Jansen, Klaus" uniqKey="Jansen K" first="Klaus" last="Jansen">Klaus Jansen</name></noRegion></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Rhénanie/explor/UnivTrevesV1/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 002C22 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 002C22 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Rhénanie
|area= UnivTrevesV1
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:47F37255EB68111B87CC2AE071D9F88C94C865FD
|texte= On scheduling problems restricted to interval orders
}}
| This area was generated with Dilib version V0.6.31. |  |