Том 28, номер 1, 2021 г., Стр. 48-67

УДК 519.1+519.8
Симанчёв Р. Ю., Соловьёва П. В., Уразова И. В.
Аффинная оболочка многогранника расписаний обслуживания идентичных требований параллельными приборами

Аннотация:
Рассмотрены некоторые полиэдральные свойства множества расписаний обслуживания идентичных требований с предшествованиями параллельными приборами. Прерывания в обслуживании требований запрещены. Предложена формализация множества расписаний как семейства подмножеств конечного множества, определён многогранник расписаний. Найдены аффинная оболочка и размерность этого многогранника, условия опорности неравенств, определяющих его полиэдральную релаксацию.
Табл. 1, ил. 2, библиогр. 20.

Ключевые слова: расписание, многогранник, аффинная оболочка, опорное неравенство.

DOI: 10.33048/daio.2021.28.697

Симанчёв Руслан Юрьевич ^1,2
Соловьёва Полина Вячеславовна ¹
Уразова Инна Владимировна ¹
1. Омский гос. университет им. Ф. М. Достоевского,
пр. Мира, 55а, 644077 Омск, Россия
2. Омский научный центр СО РАН,
пр. Карла Маркса, 15, 644024 Омск, Россия
е-mail: osiman@rambler.ru, polinochka.chervonnykh@mail.ru, urazovainn@mail.ru

Статья поступила 14 июля 2020 г.
После доработки — 27 сентября 2020 г.
Принята к публикации 28 сентября 2020 г.

Литература

[1] Симанчёв Р. Ю., Уразова И. В. Целочисленная модель задачи минимизации общего времени обслуживания параллельными приборами единичных требований с предшествованиями // Автоматика и телемеханика. 2010. № 10. С. 100–106.

[2] Симанчёв Р. Ю., Уразова И. В., Кочетов Ю. А. Метод ветвей и отсечений для задачи разбиения на клики // Дискрет. анализ и исслед. операций. 2019. Т. 26, № 3. С. 60–87.

[3] Applegate D. L., Bixby R. E., Chvátal V., CookW. J., Espinoza D. G., Goycoolea M., Helsgaun K. Certification of an optimal TSP tour through 85 900 cities // Oper. Res. Lett. 2009. Vol. 37. P. 11–15.

[4] Bouma W. H., Goldengorin B. A polytime algorithm based on a primal LP model for the scheduling problem 1|$pmtn$; $p_j = 2$; $r_j |\sum w_j C_j$ // Recent advances in applied mathematics. Proc. Amer. Conf. Appl. Math. (AMERICANMATH’10) (Cambridge, MA, USA, Jan. 27–29, 2010). Stevens Point: WSEAS Press, 2010. P. 415–420.

[5] Crowder H., Jonson E. L., Padberg M. W. Solving large-scale zero-one linear programming problems // Oper. Res. 1983. Vol. 31. P. 803–834.

[6] Grötschel M., Holland O. Solution of large-scale symmetric travelling salesman problems // Math. Program. 1991. Vol. 51. P. 141–202.

[7] Grötschel M., Wakabayashi Y. A cutting plane algorithm for a clustering problem // Math. Program. 1989. Vol. 45. P. 59–96.

[8] Balas E. On the facial structure of scheduling polyhedra // Mathematical programming essays in honor of George B. Dantzig. Pt. I. Amsterdam: North-Holland, 1985. P. 179–218. (Math. Program. Studies; Vol. 24).

[9] Mokotoff E. An exact algorithm for the identical parallel machine scheduling problem // Eur. J. Oper. Res. 2004. Vol. 152. P. 758–769.

[10] Queyranne M. Structure of simple scheduling polyhedron // Math. Program. 1993. Vol. 58. P. 263–285.

[11] Queyranne M., Wang Y. Single-machine scheduling polyhedra with precedence constraints // Math. Oper. Res. 1991. Vol. 16. P. 1–20.

[12] Nemhauser G. L., Savelsbergh M. W. P. A cutting plane algorithm of single machine scheduling problem with release times // Combinatorial optimization: New frontiers in theory and practice. Heidelberg: Springer, 1992. P. 63–84. (NATO ASI Ser.; Vol. 82).

[13] Schulz A. S. Polytopes and scheduling: PhD thesis. Technische Univ. Berlin, Berlin, 1996.

[14] Queyranne M., Schulz A. S. Polyhedral approaches to machine scheduling. Berlin: Technische Univ. Berlin, 1994.

[15] Симанчёв Р. Ю., Уразова И. В. Многогранник расписаний обслуживания идентичных требований параллельными приборами // Дискрет. анализ и исслед. операций. 2011. Т. 18, № 11. С. 85–97.

[16] Симанчёв Р. Ю., Шерешик Н. Ю. Целочисленные модели обслуживания требований одним прибором с прерываниями // Дискрет. анализ и исслед. операций. 2014. Т. 21, № 4. С. 89–101.

[17] Шерешик Н. Ю. Релаксации многогранника оптимальных расписаний обслуживания требований одним прибором с прерываниями // Дискрет. анализ и исслед. операций. 2015. Т. 22, № 6. С. 78–90.

[18] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.

[19] Кристофидес Н. Теория графов. Алгоритмический подход. М: Мир, 1978. 420 c.

[20] Brucker P., Knust S. Complexity results for scheduling problems. Osnabrück: Univ. Osnabrück, 2009. Available at www2.informatik.uni-osnabrueck.de/knust/class (accessed Oct. 23, 2020).