Batch processing with interval graph compatibilities between tasks
From MaRDI portal
Publication:2476244
DOI10.1016/j.dam.2006.03.039zbMath1172.90399OpenAlexW2154135432MaRDI QIDQ2476244
Maurice Queyranne, Vincent Jost, András Sebő, Gerd Finke
Publication date: 18 March 2008
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.dam.2006.03.039
Related Items (32)
The lockmaster's problem ⋮ A PTAS for the horizontal rectangle stabbing problem ⋮ Online algorithms for scheduling on batch processing machines with interval graph compatibilities between jobs ⋮ An optimal online algorithm for the parallel-batch scheduling with job processing time compatibilities ⋮ On the max-weight edge coloring problem ⋮ Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines ⋮ Capacitated max-batching with interval graph compatibilities ⋮ A weakly robust PTAS for minimum clique partition in unit disk graphs ⋮ Improved approximation algorithms for the max edge-coloring problem ⋮ A note on the Cornaz-Jost transformation to solve the graph coloring problem ⋮ Bounded max-colorings of graphs ⋮ Partitioning a weighted partial order ⋮ A survey on vertex coloring problems ⋮ Clique partitioning of interval graphs with submodular costs on the cliques ⋮ Clique Clustering Yields a PTAS for max-Coloring Interval Graphs ⋮ Flowshop scheduling problem with a batching machine and task compatibilities ⋮ On the max coloring problem ⋮ On maximizing the profit of a satellite launcher: selecting and scheduling tasks with time windows and setups ⋮ Unnamed Item ⋮ Approximating the max-edge-coloring problem ⋮ Unnamed Item ⋮ On the Maximum Edge Coloring Problem ⋮ Clique clustering yields a PTAS for max-coloring interval graphs ⋮ Scheduling hybrid flowshop with parallel batching machines and compatibilities ⋮ A one-to-one correspondence between colorings and stable sets ⋮ PARALLEL MACHINE SCHEDULING WITH A SIMULTANEITY CONSTRAINT AND UNIT-LENGTH JOBS TO MINIMIZE THE MAKESPAN ⋮ The vertex coloring problem and its generalizations ⋮ Weighted coloring on planar, bipartite and split graphs: Complexity and approximation ⋮ Scheduling an unbounded batching machine with job processing time compatibilities ⋮ Models and heuristic algorithms for a weighted vertex coloring problem ⋮ Clique partitioning with value-monotone submodular cost ⋮ Single-machine batch scheduling with job processing time compatibility
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Restrictions of graph partition problems. I
- Bounded vertex colorings of graphs
- Geometric algorithms and combinatorial optimization
- Scheduling a batching machine
- Dynamic scheduling on a single batch processing machine with split compatibility graphs
- The mutual exclusion scheduling problem for permutation and comparability graphs.
- Scheduling a batch processing machine with bipartite compatibility graphs
- Combinatorial optimization. Polyhedra and efficiency (3 volumes)
- Complexity results for single-machine problems with positive finish-start time-lags
- Scheduling with batching: A review
- Scheduling Interval-Ordered Tasks
- Scheduling Semiconductor Burn-In Operations to Minimize Total Flowtime
This page was built for publication: Batch processing with interval graph compatibilities between tasks
