УДК 519.85
MSC: 90C10, 90C57
DOI: 10.21538/0134-4889-2023-29-3-156-167
Работа выполнена в рамках государственного задания Омского научного центра СО РАН (номер госрегистрации проекта 121022000112-2).
Полный текст статьи (Full text)
Статья переведена: ISSN 0081-5438
Proceedings of the Steklov Institute of Mathematics, 2023, Vol. 323, Suppl. 1, pp. S243–S254. (Abstract)
В работе рассматривается выпуклая оболочка множества расписаний обслуживания идентичных требований параллельными приборами. На множестве требований заданы условия предшествования в обслуживании требований. Все требования поступают в очередь на обслуживание одновременно и имеют одинаковые длительности обслуживания. Прерывания в обслуживании требований запрещены. Время дискретно. В статье изучаются полиэдральные свойства некоторых построенных ранее классов правильных неравенств. Проводится сравнение отсечений по “глубине”, выделяются наиболее сильные подклассы отсечений. Также исследовано взаимное расположение многогранника расписаний и порождаемых неравенствами гиперплоскостей.
Ключевые слова: расписания, многогранник, правильное неравенство, сравнение неравенств
СПИСОК ЛИТЕРАТУРЫ
1. Симанчёв Р.Ю., Соловьева П.В., Уразова И.В. Аффинная оболочка многогранника расписаний обслуживания идентичных требований параллельными приборами // Дискрет. анализ и исcледование операций. 2021. Т. 28, № 1. С. 48–67. doi: 10.33048/daio.2021.28.697
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” /eds. A. Strekalovsky et. al. 2021. P. 257–270 (Communications in Computer and Information Science; vol. 1476). doi: 10.1007/978-3-030-86433-0_18
3. Симанчев Р. Ю., Уразова И. В. Целочисленная модель задачи минимизации общего времени обслуживания параллельными приборами единичных требований с предшествованиями // Автоматика и телемеханика. 2010. № 10. С. 100–106.
4. Grotschel M., Wakabayashi Y. A cutting plane algorithm for a clustering problem // Math. Prog. (Ser. B). 1989. № 45. P. 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. P. 488–505. doi: 10.1016/j.ejor.2023.01.039
6. Balas E. On the facial structure of sheduling polyhedra // Mathematical Programming Essays in Honor of George B. Dantzig. Part I / ed. R. W. Cottle. 1985. P. 179–218 (Math. Prog. Study, vol. 24). 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. P. 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. № 16. P. 1–20.
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 / eds. M. AkgЈul et. al. Berlin: Springer, 1992. P. 63–84 (NATO ASI Series F: Computer and System Science; vol. 82). doi: 10.1007/978-3-642-77489-8_4
10. Симанчев Р.Ю., Уразова И.В. Многогранник расписаний обслуживания идентичных требований параллельными приборами // Дискрет. анализ и исследование операций. 2011. Т. 18, № 11. С. 85–97.
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.
12. Танаев В.С., Гордон В.С., Шафранский В.В. Теория расписаний. Одностадийные системы. М.: Наука, 1987. 384 p.
13. Колоколов А.А. Регулярные разбиения и отсечения в целочисленном программировании // Сибирский журн. исследования операций. Новосибирск, 1994. Т. 1, № 2. С. 18–39.
14. Christofides N. Graph theory. An algorithmic approach. NY: Acad. Press., 1975. 400 p.
15. Brucker P., Knust S. Complexity results for scheduling problems [e-resource]. URL: www//mathematik.uni-osnabrueck.de/research/OR/class
16. Симанчев Р.Ю., Уразова И.В. Класс t-дольных неравенств для многогранника расписаний обслуживания требований параллельными приборами // Proc. of the Workshop on Data, Modeling and Security (DMS-2017) / eds. Sergey V. Belim, Nadezda F. Bogachenko. Omsk, 2017. 5 p. URL: http://ceur-ws.org/Vol-1965/paper8.pdf
Поступила 11.05.2023
После доработки 13.06.2023
Принята к публикации 19.06.2023
Симанчев Руслан Юрьевич
д-р физ.-мат. наук, старший науч. сотрудник
зав. кафедрой
Омский государственный университет им. Ф.М. Достоевского;
Омский науч. центр СО РАН
г.Омск
e-mail: SimanchevRiu@omsu.ru
Уразова Инна Владимировна
канд. физ.-мат. наук, доцент
Омский государственный университет им. Ф.М. Достоевского
e-mail: UrazovaIV@omsu.ru
Ссылка на статью: Р.Ю. Симанчев, И.В. Уразова. Сравнение и полиэдральные свойства правильных неравенств для многогранника расписаний обслуживания идентичных требований // Тр. Ин-та математики и механики УрО РАН. 2023. Т. 29, № 3. С. 156-167
English
R.Yu. Simanchev, I.V. Urazova. Comparison and polyhedral properties of valid inequalities for a polytope of schedules for servicing identical requests
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
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.
[References -> on the "English" button bottom right]
