The paper considers the convex hull of a set of schedules for servicing identical requests by parallel devices. Precedence conditions are given on the set of requests. All requests enter the service queue simultaneously and have the same service duration. Interruptions in request servicing are prohibited. Time is discrete. The polyhedral properties of some previously constructed classes of valid inequalities are studied. The “depth” cuts are compared, and the strongest subclasses of cuts are found. The mutual arrangement of the schedule polyhedron and hyperplanes generated by inequalities is also studied.
Keywords: schedules, polytope, valid inequality, comparison of inequalities
Received May 11, 2023
Revised June 13, 2023
Accepted June 19, 2023
Funding Agency: This research was carried out within the state task of the Omsk Scientific Center SB RAS (project registration no. 121022000112-2).
Ruslan Yurievich Simanchev, Dr. Phys.-Math. Sci., Dostoevsky Omsk State University, Omsk, 644077 Russia; Omsk Scientific Center of SB RAS, Omsk, 644025 Russia, e-mail: osiman@rambler.ru
Inna Vladimirovna Urazova, Cand. Sci. (Phys.-Math.), Dostoevsky Omsk State University, Omsk, 644077 Russia, e-mail: urazovainn@mail.ru
REFERENCES
1. Simanchev R. Yu., Solovieva P. V., Urazova I. V. The affine hull of the schedule polytope for servicing identical requests by parallel devices. J. Appl. Industr. Math., 2021, vol. 15, no. 1, pp. 146–157. doi: 10.1134/S1990478921010130
2. Simanchev R.Yu., Urazova I.V. The polytope of schedules of processing of identical requirements: the properties of the relaxation polyhedron. In: 20th Internat. Conf. “MOTOR 2021”, eds. A. Strekalovsky et al., Ser. Communications in Computer and Information Science, Cham, Springer, 2021, pp. 257–270. doi: 10.1007/978-3-030-86433-0_18
3. Simanchev R. Yu., Urazova I. V. An integer-valued model for the problem of minimizing the total servicing time of unit claims with parallel devices with precedences. Autom. Remote Control, 2010, vol. 71, no. 10, pp. 2102–2108. doi: 10.1134/S0005117910100097
4. Grotschel M., Wakabayashi Y. A cutting plane algorithm for a clustering problem. Math. Prog. (Ser. B), 1989, vol. 45, no. 1–3, pp. 59–96. doi: 10.1007/BF01589097
5. Khachai D., Sadykov R., Battaia O., Khachay M. Precedence constrained generalized traveling salesman problem: Polyhedral study, formulations, and branch-and-cut algorithm. European J. Oper. Res., 2023, vol. 309, no. 2, pp. 488-505. doi: 10.1016/j.ejor.2023.01.039
6. Balas E. On the facial structure of sсheduling polyhedra. In: Mathematiacl Programming Essays in Honor of George B. Dantzig, Part I, ed. R. W. Cottle, Ser. Math. Progr. Study, vol. 24, Berlin, Heidelberg, Springer, 1985, pp. 179–218. doi: 10.1007/BFb0121051
7. Mokotoff E. An exact algorithm for the identical parallel machine scheduling problem. Europ. J. Oper. Res., 2004, vol. 152, no. 3, pp. 758–769. doi: 10.1016/S0377-2217(02)00726-9
8. Queyranne M., Wang Y. Single-machine scheduling polyhedra with precedence constraints. Mathematics Oper. Res., 1991, vol. 16, pp. 1–20.
9. Nemhauser G.L., Savelsbergh M.W. A cutting plane algorithm of single machine scheduling problem with release times. In: Combinatorial Optimization: New Frontiers in the Theory and Practice, eds. M. AkgЈul et. al. NATO ASI Series F: Computer and System Science, Berlin, Springer, 1992, vol. 82, pp. 63–84. doi: 10.1007/978-3-642-77489-8_4
10. Simanchev R.Yu., Urazova I.V. The polytope of schedules of identical jobs on parallel processors. Diskretn. Anal. Issled. Oper., 2011, vol. 18, no. 1, pp. 85–97 (in Russian).
11. Garey M.R., Johnson D.S. Computers and intractability: a guide to the theory of NP-completeness, NY, W.H. Freeman and co., 1979, 340 p. ISBN: 0-7167-1045-5. Translated to Russian under the title Vychislitel’nye mashiny i trudnoreshaemye zadachi, Moscow, Mir Publ., 1982, 416 p.
12. Tanaev V.S., Gordon V.S., Shafranskii V.V. Teoriya raspisanii. Odnostadiinye sistemy [Theory of schedules. One-stage systems], Moscow, Nauka Publ., 1984, 384 p.
13. Kolokolov A.A. Regular partitionings and cuttings of in integer programming. Sib. Zhurn. Issled. Oper., 1994, vol. 1, no. 2, pp. 18–39 (in Russian).
14. Christofides N. Graph theory. An algorithmic approach, NY, Acad. Press, 1975, 400 p. ISBN: 978-0121743505. Translated to Russian under the title Teoriya grafov. Algoritmicheskii podkhod, Moscow, Mir Publ, 1978, 432 p.
15. Brucker P., Knust S. Complexity results for scheduling problems [e-resource]. Available on: http://www2.informatik.uni-osnabrueck.de/knust/class .
16. Simanchev R.Yu., Urazova I.V. The class of T-share inequalities for the service schedules of requirements by parallel devices polytope. In: Proceedings of the Workshop on Data, Modeling and Security (DMS 2017), eds. Sergey V. Belim, Nadezda F. Bogachenko, Omsk, Dostoevsky Omsk State University Publ., 2017. 5 p. Available on: http://ceur-ws.org/Vol-1965/paper8.pdf
Cite this article as: R.Yu. Simanchev, I.V. Urazova. Comparison and polyhedral properties of valid inequalities for a polytope of schedules for servicing identical requests. Trudy Instituta Matematiki i Mekhaniki UrO RAN, 2023, vol. 29, no. 3, pp. 156–167; Proceedings of the Steklov Institute of Mathematics (Suppl.), 2023, Vol. 323, Suppl. 1, pp. S243–S254.
