|
Comparison and Polyhedral Properties of Valid Inequalities for a Polytope of Schedules for Servicing Identical Requests
R. Yu. Simanchevab, I. V. Urazovaa a Omsk State University
b Omsk Scientific Center, Siberian Branch of the Russian Academy of Sciences
Abstract:
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.
Received: 11.05.2023 Revised: 13.06.2023 Accepted: 19.06.2023
Citation:
R. Yu. Simanchev, I. V. Urazova, “Comparison and Polyhedral Properties of Valid Inequalities for a Polytope of Schedules for Servicing Identical Requests”, Trudy Inst. Mat. i Mekh. UrO RAN, 29, no. 3, 2023, 156–167; Proc. Steklov Inst. Math. (Suppl.), 323, suppl. 1 (2023), S243–S254
Linking options:
https://www.mathnet.ru/eng/timm2024 https://www.mathnet.ru/eng/timm/v29/i3/p156
|
|