Open Shop Scheduling with Simultaneity Constraints

This chapter considers open shop scheduling with simultaneity constraints. The constraints require that some operations be processed simultaneously at any time. We show that the constraints are capable of modeling edge coloring in arbitrary graphs, which in turn models many real-life problems. Motivated by applications in scheduling wireless networks, we consider the problem of covering the edges of a graph by a sequence of matchings subject to the constraint that each edge e appears in at least a given fraction r(e) of the matchings. It can be determined in polynomial time whether such a sequence of matchings exists or not; however, makespan minimization of the sequence is computationally intractable in general. We restrict our investigation to a special class of graphs, the so-called OLoP (Overall Local Pooling) graphs shown important in an online distributed wireless network scheduling setting. We also generalize the results to a larger class of graphs that we call GOLoP graphs. In particular, we show that deciding whether a given GOLoP graph has a matching sequence of length at most k can be done in linear time. If the answer is affirmative, we show how to construct, in quadratic time, the matching sequence of length at most k. Finally, we prove that, for GOLoP graphs, the length of a shortest sequence does not exceed a constant times the least common denominator of the fractions r(e). This leads to a pseudopolynomial-time algorithm for minimizing the length of the sequence. We show that the constant equals 1 for OLoP graphs and conjecture that the constant is as small as 2 for general graphs. This conjecture holds for all graphs with at most 10 vertices.