Group for Research in Decision Analysis

Interval edge-coloring: A reduction of the standard problem to the cyclic problem

Sivan Altinakar Polytechnique Montréal, Canada

In a graph, a k-edge-coloring associates an integer color number in {1,...,k} to each edge, such that no vertex has two adjacent edges of the same color. This formulation is useful for modeling scheduling problems, for example when in a production chain, a given set of objects must each be processed in unit-length times on a subset of machines (without any specific order). In this case, a node corresponds to either an object or a machine, an edge between two such nodes to the constraint that this object must be processed on that machine, and the color of an edge to the timeframe during which this happens. In the real world, there are many additional constraints to this simple problem, for example when a machine must have no idle time between its first and last assignment, and when there are no places where an object can wait between its first and last processing. In our edge-coloring model, this means that for each node, the set of colors of the edges adjacent to it must form, depending on the problem, either a standard integer interval (a set of consecutive integers) or a cyclic integer interval (1 is consecutive to k). The aim of this talk is to present a reduction from the standard to the cyclic k-interval edge-coloring problem (when k greater or equal to 12), as well as ways to model some other cyclic scheduling problems as a cyclic interval edge-coloring problem, using some of the tools developed for the reduction.