Show simple item record

dc.contributor.authorDemange, Marc
dc.contributor.authorde Werra, Dominique
dc.contributor.authorMonnot, Jérôme
HAL ID: 178759
ORCID: 0000-0002-7452-6553
dc.contributor.authorPaschos, Vangelis
dc.date.accessioned2010-01-04T10:48:03Z
dc.date.available2010-01-04T10:48:03Z
dc.date.issued2007
dc.identifier.urihttps://basepub.dauphine.fr/handle/123456789/2796
dc.language.isoenen
dc.subjectBatch schedulingen
dc.subjectEdge coloringen
dc.subjectApproximationsen
dc.subjectChromatic schedulingen
dc.subjectWeighted coloringen
dc.subject.ddc003en
dc.titleTime slot scheduling of compatible jobsen
dc.typeArticle accepté pour publication ou publié
dc.contributor.editoruniversityotherESSEC;France
dc.contributor.editoruniversityotherEcole Polytechnique Fédérale de Lausanne, Lausanne;Suisse
dc.description.abstractenA version of weighted coloring of a graph is introduced which is motivated by some types of scheduling problems: each node v of a graph G corresponds to some operation to be processed (with a processing time w(v)), edges represent nonsimultaneity requirements (incompatibilities). We have to assign each operation to one time slot in such a way that in each time slot, all operations assigned to this slot are compatible; the length of a time slot will be the maximum of the processing times of its operations. The number k of time slots to be used has to be determined as well. So, we have to find a k-coloring $${\cal S}$$= $$({S_{1},\ldots ,S_{k}})$$ of G such that w(S 1) + ⋅s +w(S k ) is minimized where w(S i ) = max {w(v) :v∊V}. Properties of optimal solutions are discussed, and complexity and approximability results are presented. Heuristic methods are given for establishing some of these results. The associated decision problems are shown to be NP-complete for bipartite graphs, for line-graphs of bipartite graphs, and for split graphs.en
dc.relation.isversionofjnlnameJournal of Scheduling
dc.relation.isversionofjnlvol10en
dc.relation.isversionofjnlissue2en
dc.relation.isversionofjnldate2007
dc.relation.isversionofjnlpages111-127en
dc.relation.isversionofdoihttp://dx.doi.org/10.1007/s10951-006-0003-7en
dc.description.sponsorshipprivateouien
dc.relation.isversionofjnlpublisherSpringer
dc.subject.ddclabelRecherche opérationnelleen


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record