Open Shop Scheduling with Simultaneity Constraints

Wieslaw Kubiak
Additional contact information
Wieslaw Kubiak: Memorial University of Newfoundland

Chapter Chapter 6 in A Book of Open Shop Scheduling, 2022, pp 137-164 from Springer

Abstract: Abstract 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.

Date: 2022
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:isochp:978-3-030-91025-9_6

Ordering information: This item can be ordered from
http://www.springer.com/9783030910259

DOI: 10.1007/978-3-030-91025-9_6

Access Statistics for this chapter

More chapters in International Series in Operations Research & Management Science from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().