dc.contributor.author Demange, Marc dc.contributor.author de Werra, Dominique dc.contributor.author Monnot, Jérôme HAL ID: 178759 ORCID: 0000-0002-7452-6553 dc.contributor.author Paschos, Vangelis dc.date.accessioned 2010-01-04T10:48:03Z dc.date.available 2010-01-04T10:48:03Z dc.date.issued 2007 dc.identifier.uri https://basepub.dauphine.fr/handle/123456789/2796 dc.language.iso en en dc.subject Batch scheduling en dc.subject Edge coloring en dc.subject Approximations en dc.subject Chromatic scheduling en dc.subject Weighted coloring en dc.subject.ddc 003 en dc.title Time slot scheduling of compatible jobs en dc.type Article accepté pour publication ou publié dc.contributor.editoruniversityother ESSEC;France dc.contributor.editoruniversityother Ecole Polytechnique Fédérale de Lausanne, Lausanne;Suisse dc.description.abstracten A 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.isversionofjnlname Journal of Scheduling dc.relation.isversionofjnlvol 10 en dc.relation.isversionofjnlissue 2 en dc.relation.isversionofjnldate 2007 dc.relation.isversionofjnlpages 111-127 en dc.relation.isversionofdoi http://dx.doi.org/10.1007/s10951-006-0003-7 en dc.description.sponsorshipprivate oui en dc.relation.isversionofjnlpublisher Springer dc.subject.ddclabel Recherche opérationnelle en
﻿