Scheduling with incompatible jobs
From MaRDI portal
Publication:1343141
DOI10.1016/0166-218X(94)90009-4zbMath0822.68011OpenAlexW2004102446WikidataQ59567997 ScholiaQ59567997MaRDI QIDQ1343141
Gerhard J. Woeginger, Klaus Jansen, Hans L. Bodlaender
Publication date: 1 February 1995
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0166-218x(94)90009-4
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Performance evaluation, queueing, and scheduling in the context of computer systems (68M20)
Related Items (36)
The \(d\)-precoloring problem for \(k\)-degenerate graphs ⋮ Scheduling with conflicts: Online and offline algorithms ⋮ Coloration de graphes : fondements et applications ⋮ Scheduling with complete multipartite incompatibility graph on parallel machines: complexity and algorithms ⋮ Mutual exclusion scheduling ⋮ Models and complexity of multibin packing problems ⋮ An exact algorithm for parallel machine scheduling with conflicts ⋮ Makespan minimization on unrelated parallel machines with a few bags ⋮ Time slot scheduling of compatible jobs ⋮ A stand-alone branch-and-price algorithm for identical parallel machine scheduling with conflicts ⋮ Incremental list coloring of graphs, parameterized by conservation ⋮ Data reduction for graph coloring problems ⋮ THE GRAPH-BIN PACKING PROBLEM ⋮ Multiprofessor scheduling ⋮ Storage Yard Management: Modelling and Solving ⋮ Multi-level bottleneck assignment problems: complexity and sparsity-exploiting formulations ⋮ Scheduling with machine conflicts ⋮ Scheduling on uniform machines with a conflict graph: complexity and resolution ⋮ An improved algorithm for parallel machine scheduling under additional resource constraints ⋮ Flow shop scheduling problem with conflict graphs ⋮ Approximating the multi-level bottleneck assignment problem ⋮ Probabilistic analysis for scheduling with conflicts ⋮ A hypocoloring model for batch scheduling ⋮ On the probabilistic minimum coloring and minimum \(k\)-coloring ⋮ Scheduling identical jobs on uniform machines with a conflict graph ⋮ The maximum saving partition problem ⋮ Hard coloring problems in low degree planar bipartite graphs ⋮ Precoloring extension of co-Meyniel graphs ⋮ Probabilistic graph-coloring in bipartite and split graphs ⋮ Parameterized complexity of vertex colouring ⋮ Data Reduction for Graph Coloring Problems ⋮ Weighted coloring on planar, bipartite and split graphs: Complexity and approximation ⋮ Uniform machine scheduling with machine available constraints ⋮ On minimizing the makespan when some jobs cannot be assigned on the same machine ⋮ A combination of flow shop scheduling and the shortest path problem ⋮ Open shop scheduling problems with conflict graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parallel machines scheduling with nonsimultaneous machine available time
- Precoloring extension. I: Interval graphs
- Worst-Case Analysis of Heuristic Algorithms
- Performance Guarantees for Scheduling Algorithms
- Optimization and Approximation in Deterministic Sequencing and Scheduling: a Survey
- Bounds for Certain Multiprocessing Anomalies
- Bounds on Multiprocessing Timing Anomalies
This page was built for publication: Scheduling with incompatible jobs
