Geodesic
Comparison and Polyhedral Properties of Valid Inequalities for a Polytope of Schedules for Servicing Identical Requests
Trudy Instituta matematiki i mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 29 (2023) no. 3, pp. 156-167 Cet article a éte moissonné depuis la source Math-Net.Ru

Voir la notice du chapitre de livre

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 relative position of the schedule polytope and hyperplanes generated by inequalities is also studied.
Keywords: schedules, polytope, valid inequality, comparison of inequalities. 
@article{TIMM_2023_29_3_a9,
     author = {R. Yu. Simanchev and I. V. Urazova},
     title = {Comparison and {Polyhedral} {Properties} of {Valid} {Inequalities} for a {Polytope} of {Schedules} for {Servicing} {Identical} {Requests}},
     journal = {Trudy Instituta matematiki i mehaniki},
     pages = {156--167},
     year = {2023},
     volume = {29},
     number = {3},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/TIMM_2023_29_3_a9/}
}
TY  - JOUR
AU  - R. Yu. Simanchev
AU  - I. V. Urazova
TI  - Comparison and Polyhedral Properties of Valid Inequalities for a Polytope of Schedules for Servicing Identical Requests
JO  - Trudy Instituta matematiki i mehaniki
PY  - 2023
SP  - 156
EP  - 167
VL  - 29
IS  - 3
UR  - http://geodesic.mathdoc.fr/item/TIMM_2023_29_3_a9/
LA  - ru
ID  - TIMM_2023_29_3_a9
ER  - 
%0 Journal Article
%A R. Yu. Simanchev
%A I. V. Urazova
%T Comparison and Polyhedral Properties of Valid Inequalities for a Polytope of Schedules for Servicing Identical Requests
%J Trudy Instituta matematiki i mehaniki
%D 2023
%P 156-167
%V 29
%N 3
%U http://geodesic.mathdoc.fr/item/TIMM_2023_29_3_a9/
%G ru
%F TIMM_2023_29_3_a9
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 mehaniki, Trudy Instituta Matematiki i Mekhaniki UrO RAN, Tome 29 (2023) no. 3, pp. 156-167. http://geodesic.mathdoc.fr/item/TIMM_2023_29_3_a9/

[1] Simanchev R.Yu., Soloveva P.V., Urazova I.V., “Affinnaya obolochka mnogogrannika raspisanii obsluzhivaniya identichnykh trebovanii parallelnymi priborami”, Diskret. analiz i iscledovanie operatsii, 28:1 (2021), 48–67 | DOI | MR | Zbl

[2] Simanchev R.Yu., Urazova I.V., “The polytope of schedules of processing of identical requirements: the properties of the relaxation polyhedron”, 20th Internat. Conf. “MOTOR 2021”, Communications in Computer and Information Science, 1476, eds. A. Strekalovsky et. al, 2021, 257–270 | DOI | MR

[3] Simanchev R. Yu., Urazova I. V., “Tselochislennaya model zadachi minimizatsii obschego vremeni obsluzhivaniya parallelnymi priborami edinichnykh trebovanii s predshestvovaniyami”, Avtomatika i telemekhanika, 2010, no. 10, 100–106 | MR | Zbl

[4] Grotschel M., Wakabayashi Y., “A cutting plane algorithm for a clustering problem”, Math. Prog. (Ser. B), 1989, no. 45, 59–96 | DOI | MR | Zbl

[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., 309:2 (2023), 488–505 | DOI | MR

[6] Balas E., “On the facial structure of sheduling polyhedra”, Mathematical Programming Essays in Honor of George B. Dantzig, Part I, Math. Prog. Study, 24, ed. R. W. Cottle, 1985, 179–218 | DOI | MR | Zbl

[7] Mokotoff E., “An exact algorithm for the identical parallel machine scheduling problem”, Europ. J. Oper. Res., 152:3 (2004), 758–769 | DOI | MR | Zbl

[8] Queyranne M., Wang Y., “Single-machine scheduling polyhedra with precedence constraints”, Mathematics Oper. Res., 1991, no. 16, 1–20 | DOI | MR | Zbl

[9] Nemhauser G.L., Savelsbergh M.W., “A cutting plane algorithm of single machine scheduling problem with release times”, Combinatorial Optimization: New Frontiers in the Theory and Practice, NATO ASI Series F: Computer and System Science, 82, eds. M. Akgül et. al, Springer, Berlin, 1992, 63–84 | DOI | MR

[10] Simanchev R.Yu., Urazova I.V., “Mnogogrannik raspisanii obsluzhivaniya identichnykh trebovanii parallelnymi priborami”, Diskret. analiz i issledovanie operatsii, 18:11 (2011), 85–97 | MR | Zbl

[11] Garey M.R., Johnson D.S., Computers and Intractability: A guide to the theory of $NP$-completeness, W.H. Freeman and co., NY, 1979, 340 pp. | MR | Zbl

[12] Tanaev V.S., Gordon V.S., Shafranskii V.V., Teoriya raspisanii. Odnostadiinye sistemy, Nauka, M., 1987, 384 pp.

[13] Kolokolov A.A., “Regulyarnye razbieniya i otsecheniya v tselochislennom programmirovanii”, Sibirskii zhurn. issledovaniya operatsii, 1:2 (1994), 18–39, Novosibirsk | MR | Zbl

[14] Christofides N., Graph theory. An algorithmic approach, Acad. Press, NY, 1975, 400 pp. | MR | Zbl

[15] Brucker P., Knust S., Complexity results for scheduling problems [e-resource]. URL: http://www.mathematik.uni-osnabrueck.de/research/OR/class | MR

[16] Simanchev R.Yu., Urazova I.V., “Klass $t$-dolnykh neravenstv dlya mnogogrannika raspisanii obsluzhivaniya trebovanii parallelnymi priborami”, Proc. of the Workshop on Data, Modeling and Security (DMS-2017), eds. Sergey V. Belim, Nadezda F. Bogachenko, Omsk, 2017, 5 pp. URL: http://ceur-ws.org/Vol-1965/paper8.pdf | Zbl