Batch processing with interval graph compatibilities between tasks

DOI10.1016/J.DAM.2006.03.039MaRDI QIDQ2476244zbMATH OpenOpenAlexFDO

Authors Gerd Finke, Vincent Jost, Maurice Queyranne, András Sebö

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

zbMATH Keywords

batch-schedulingbounded coloringinterval graphsMax-coloringperfect graphstask compatibilities

Mathematics Subject Classification ID

Deterministic scheduling theory in operations research (90B35)

Recommendations

• Scheduling on a batch processing machine with split compatibility graphs
• Scheduling on a batch machine with job compatibilities
• Scheduling a batch processing machine with bipartite compatibility graphs
• Online algorithms for scheduling on batch processing machines with interval graph compatibilities between jobs
• Dynamic scheduling on a single batch processing machine with split compatibility graphs

Cites work

• Bounded vertex colorings of graphs
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Complexity results for single-machine problems with positive finish-start time-lags
• Dynamic scheduling on a single batch processing machine with split compatibility graphs
• Geometric algorithms and combinatorial optimization
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Restrictions of graph partition problems. I
• Scheduling a batch processing machine with bipartite compatibility graphs
• Scheduling a batching machine
• Scheduling Interval-Ordered Tasks
• Scheduling on a batch machine with job compatibilities
• Scheduling Semiconductor Burn-In Operations to Minimize Total Flowtime
• Scheduling with batching: A review
• The mutual exclusion scheduling problem for permutation and comparability graphs.

Cited in

(41)

• Scheduling hybrid flowshop with parallel batching machines and compatibilities
• The vertex coloring problem and its generalizations
• Weighted coloring on planar, bipartite and split graphs: Complexity and approximation
• Scheduling with undirected graphs: motivations and reviews
• Models and heuristic algorithms for a weighted vertex coloring problem
• Dynamic scheduling on a single batch processing machine with split compatibility graphs
• Scheduling a batch processing machine with bipartite compatibility graphs
• An optimal online algorithm for the parallel-batch scheduling with job processing time compatibilities
• Scheduling of unit-length jobs with cubic incompatibility graphs on three uniform machines
• Order consolidation for batch processing
• Improved approximation algorithms for the max edge-coloring problem
• A PTAS for the horizontal rectangle stabbing problem
• Clique partitioning with value-monotone submodular cost
• Single-machine batch scheduling with job processing time compatibility
• Online algorithms for scheduling on batch processing machines with interval graph compatibilities between jobs
• A weakly robust PTAS for minimum clique partition in unit disk graphs
• A note on the Cornaz-Jost transformation to solve the graph coloring problem
• Bounded max-colorings of graphs
• A one-to-one correspondence between colorings and stable sets
• Minimizing total completion time on a batching machine with job processing time compatibilities
• 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
• Parallel machine scheduling with a simultaneity constraint and unit-length jobs to minimize the makespan
• The lockmaster's problem
• Capacitated max-batching with interval graph compatibilities
• On the Maximum Edge Coloring Problem
• Structural and extremal properties of the hot rolling batches precedence graph
• Stabbing rectangles by line segments -- how decomposition reduces the shallow-cell complexity
• On the max-weight edge coloring problem
• A PTAS for the horizontal rectangle stabbing problem
• On the max coloring problem
• A best possible online algorithm for parallel-batch scheduling with kind release times and job compatibilities
• Clique clustering yields a PTAS for max-coloring interval graphs
• Online flexible busy time scheduling on heterogeneous machines
• Scheduling an unbounded batching machine with job processing time compatibilities
• Capacitated max-batching with interval graph compatibilities
• Partitioning a weighted partial order
• Flowshop scheduling problem with a batching machine and task compatibilities
• On maximizing the profit of a satellite launcher: selecting and scheduling tasks with time windows and setups
• Approximating the max-edge-coloring problem

This page was built for publication: Batch processing with interval graph compatibilities between tasks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2476244)