Batch processing with interval graph compatibilities between tasks |
| |
Authors: | Gerd Finke Maurice Queyranne |
| |
Institution: | Laboratoire Leibniz-IMAG, Grenoble, France |
| |
Abstract: | 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 relation—the 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 min-max formula and polynomial time algorithms. |
| |
Keywords: | Batch-scheduling Task compatibilities Interval graphs Perfect graphs Bounded coloring Max-coloring |
本文献已被 ScienceDirect 等数据库收录! |