Batch processing with interval graph compatibilities between tasks
We analyze batch-scheduling problems that arise in connection with certain industrial applications. The models concern processing on a single max-batch machine with the additional feature that the tasks of the same batch have to be compatible. Compatibility is a symmetric binary relationthe compatible pairs are described with an undirected compatibility graph, which is often an interval graph according to some natural practical conditions that we present. We consider several models with varying batch capacities, processing times or compatibility graphs. We summarize known results, and present a minmax formula and polynomial time algorithms.
interval graphs batch-scheduling task compatibilities perfect graphs bounded coloring max-coloring