Movatterモバイル変換

[0]ホーム
URL:

Skip to main content

Advertisement

Springer Nature Link
Log in

Open Shop Scheduling with Simultaneity Constraints

  • Chapter
  • First Online:

Part of the book series:International Series in Operations Research & Management Science ((ISOR,volume 325))

  • 480Accesses

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 edgee appears in at least a given fractionr(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 mostk 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 mostk. 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 fractionsr(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.

This is a preview of subscription content,log in via an institution to check access.

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 14871
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 18589
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info
Hardcover Book
JPY 18589
Price includes VAT (Japan)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

References

  1. B. Birand, M. Chudnovsky, B. Ries, P. Seymour, G. Zussman, Y. Zwols, Analyzing the performance of greedy maximal scheduling via local pooling and graph theory, inINFOCOM, 2010 Proceedings IEEE (IEEE, 2010), pp. 1–9

    Google Scholar 

  2. A. Brzezinski, G. Zussman, E. Modiano, Enabling distributed throughput maximization in wireless mesh networks - a partitioning approach, inProc. ACM MOBICOM’06, Sept. 2006

    Google Scholar 

  3. E.G. Coffman Jr., M.R. Garey, D.S. Johnson, A.S. LaPaugh, Scheduling file transfers. SIAM J. Comput.14, 744–780 (1985)

    Google Scholar 

  4. D. de Werra, Extensions of coloring models for scheduling purposes. Eur. J. Oper. Res.92, 474–492 (1996)

    Google Scholar 

  5. D. de Werra, J. Erschler, Open shop with some additional constraints. Graphs Combin.12, 81–93 (1996)

    Google Scholar 

  6. D. de Werra, N.V.R. Mahadev, U. Peled, Edge chromatic scheduling with simultaneity constraints. SIAM J. Disc. Math., 631–641 (1993)

    Google Scholar 

  7. D. Dereniowski, W. Kubiak, B. Ries, Y. Zwols, Optimal edge-coloring with edge rate constraints. Networks63, 165–182 (2013)

    Google Scholar 

  8. A. Dimakis, J. Walrand, Sufficient conditions for stability of longest queue first scheduling: second order properties using fluid limits. Adv. Appl. Probab.38(2), 505–521 (2006)

    Google Scholar 

  9. J. Edmonds, Maximum matching and a polyhedron with 0, 1-vertices. J. Res. Natl. Bur. Stand.69(1-2), 125–130 (1965)

    Google Scholar 

  10. L. Eggan, M. Plantholt, The chromatic index of nearly bipartite multigraphs. J. Combin. Theory B40(1), 71–80 (1986)

    Google Scholar 

  11. F. Eisenbrand, Fast integer programming in fixed dimension, in eds. by G. Di Battista, U. ZwickProceedings of the 11th Annual European Symposium on Algorithms, volume 2832 ofLNCS (Springer, 2003), pp. 196–207

    Google Scholar 

  12. S. Even, A. Itai, A. Shamir, On the complexity of timetable and multicommodity flow problems. SIAM J. Comput.5, 691–703 (1976)

    Google Scholar 

  13. R. Gandhi, M.M. Halldórsson, G. Kortsarz, H. Shachnai, Improved results for data migration and open shop scheduling. ACM Trans. Algorithms2, 116–129 (2006)

    Google Scholar 

  14. M.C. Golumbic,Algorithmic Graph Theory and Perfect Graphs (North-Holland Publishing Co., 2004)

    Google Scholar 

  15. J.L. Gross, J. Yellen,Graph Theory and Its Applications (CRC press, 2006)

    Google Scholar 

  16. M. Grötschel, L. Lovász, A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization. Combinatorica1, 169–197 (1981)

    Google Scholar 

  17. B. Hajek, G. Sasaki, Link scheduling in polynomial time. IEEE Trans. Inf. Theory34, 910–917 (1988)

    Google Scholar 

  18. J.-H. Hoepman, Simple distributed weighted matchings. eprint cs.DC/0410047, Oct. 2004

    Google Scholar 

  19. I. Holyer, The NP-completeness of edge-colouring. SIAM J. Comput.10(4), 718–720 (1981)

    Google Scholar 

  20. C. Joo, X. Lin, N.B. Shroff, Performance limits of greedy maximal matching in multi-hop wireless networks, inProc. IEEE CDC’07, Dec. 2007

    Google Scholar 

  21. S. Khuller, Y. Kim, Y.C. Wan, Algorithms for data migration with cloning, inProc. of the 22nd ACM Symposium on Principles od Database Systems, pp. 27–36 (2003)

    Google Scholar 

  22. D. König, Über graphen und ihre anwendung auf determinantentheorie und mengenlehre. Mathematische Annalen77, 453–465 (1916)

    Google Scholar 

  23. F. Kuhn, T. Moscibroda, R. Wattenhofer, What cannot be computed locally! inPODC, pp. 300–309 (2004)

    Google Scholar 

  24. M. Leconte, J. Ni, R. Srikant, Improved bounds on the throughput efficiency of greedy maximal scheduling in wireless networks. IEEE/ACM Trans. Netw.19(3), 709–720 (2011)

    Google Scholar 

  25. A.N. Letchford, G. Reinelt, D.O. Theis, A faster exact separation algorithm for blossom inequalities. Integer Programm. Combin. Optim. 19–52 (2004)

    Google Scholar 

  26. X. Lin, N.B. Shroff, The impact of imperfect scheduling on cross-layer rate control in wireless networks. IEEE/ACM Trans. Netw.14(2), 302–315 (2006)

    Google Scholar 

  27. M.W. Padberg, M.R. Rao, Odd minimum cut-sets and b-matchings. Math. Oper. Res.7(1), 67–80 (1982)

    Google Scholar 

  28. M.J. Plantholt, An order-based upper bound on the chromatic index of a multigraph. J. Combin. Inf. Syst. Sci.16, 271–280 (1991)

    Google Scholar 

  29. M.J. Plantholt, S.K. Tipnis, The chromatic index of multigraphs of order at most 10. Discrete Mathematics177, 185–193 (1997)

    Google Scholar 

  30. P.D. Seymour, On multi-colourings of cubic graphs, and conjectures of Fulkerson and Tutte. Proc. Lond. Math. Soc.(3)38, 423–460. Citeseer, 1979

    Google Scholar 

  31. L. Tassiulas, A. Ephremides, Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks. IEEE Trans. Automat. Contr.37(12), 1936–1948 (1992)

    Google Scholar 

  32. D.B. West,Introduction to Graph Theory (Prentice Hall Upper Saddle River, NJ, 2001)

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Memorial University of Newfoundland, St. John’s, NL, Canada

    Wieslaw Kubiak

Authors
  1. Wieslaw Kubiak

Rights and permissions

Copyright information

© 2022 The Author(s), under exclusive license to Springer Nature Switzerland AG

About this chapter

Check for updates. Verify currency and authenticity via CrossMark

Cite this chapter

Kubiak, W. (2022). Open Shop Scheduling with Simultaneity Constraints. In: A Book of Open Shop Scheduling. International Series in Operations Research & Management Science, vol 325. Springer, Cham. https://doi.org/10.1007/978-3-030-91025-9_6

Download citation

Publish with us

Access this chapter

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 14871
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 18589
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info
Hardcover Book
JPY 18589
Price includes VAT (Japan)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide -see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

[8]ページ先頭
©2009-2025 Movatter.jp