Time slot scheduling of compatible jobs

DOI10.1007/s10951-006-0003-7zbMath1154.90439OpenAlexW1986115514MaRDI QIDQ880586

Dominique de Werra, Marc Demange, Jérôme Monnot, Vangelis Th. Paschos

Publication date: 15 May 2007

Published in: Journal of Scheduling (Search for Journal in Brave)

Full work available at URL: https://basepub.dauphine.fr/handle/123456789/2796

zbMATH Keywords

Edge coloringApproximationsBatch schedulingChromatic schedulingWeighted coloring

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (16)

Saving Colors and Max Coloring: Some Fixed-Parameter Tractability Results ⋮ Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines ⋮ Improved approximation algorithms for the max edge-coloring problem ⋮ Exact weighted vertex coloring via branch-and-price ⋮ Bounded max-colorings of graphs ⋮ A survey on vertex coloring problems ⋮ Clique partitioning of interval graphs with submodular costs on the cliques ⋮ Saving colors and max coloring: some fixed-parameter tractability results ⋮ On the max coloring problem ⋮ On the probabilistic minimum coloring and minimum \(k\)-coloring ⋮ Approximating the max-edge-coloring problem ⋮ On the Max Coloring Problem ⋮ Weighted coloring on planar, bipartite and split graphs: Complexity and approximation ⋮ Models and heuristic algorithms for a weighted vertex coloring problem ⋮ Scheduling incompatible tasks on two machines ⋮ Clique partitioning with value-monotone submodular cost

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of decomposing matrices arising in satellite communication
• Approximating maximum independent sets by excluding subgraphs
• Approximation algorithms for combinatorial problems
• On the sum coloring problem on interval graphs
• Chromatic scheduling and frequency assignment
• Scheduling with incompatible jobs
• Generalized coloring for tree-like graphs
• On chromatic sums and distributed resource allocation
• Colouring weighted bipartite graphs with a co-site constraint
• Master-slave strategy and polynomial approximation
• Open shop scheduling with some additional constraints
• Scheduling with batching: A review
• Time-slot assignment for TDMA-systems
• On Approximate Solutions for Combinatorial Optimization Problems
• The NP-Completeness of Edge-Coloring
• Complexity Results for Multiprocessor Scheduling under Resource Constraints
• Graph colorings with local constraints -- a survey
• Graph Classes: A Survey
• NP completeness of the edge precoloring extension problem on bipartite graphs
• Scheduling batches with simultaneous job processing for two-machine shop problems

This page was built for publication: Time slot scheduling of compatible jobs