Раскраска смешанного графа как построение расписания обслуживания многопроцессорных требований с одинаковыми длительностями

  • Юрий Назарович Сотсков Объединенный институт проблем информатики НАН Беларуси, ул. Сурганова, 6, 220012, г. Минск, Беларусь https://orcid.org/0000-0002-9971-6169
DOI: https://doi.org/10.33581/2520-6508-2021-2-67-81

Аннотация

Задача обслуживания частично упорядоченных единичных требований последовательными приборами формулируется как раскраска смешанного графа, т. е. как назначение целых чисел (цветов) {1, 2, …, t} вершинам (требованиям) V {ν1, ν2, …, νn} смешанного графа G = (V, A, E), при котором вершины νp и νq, инцидентные ребру [νp, νq] ∈ E имеют различные цвета. А при наличии дуги (νi, νj) ∈ A цвет вершины ν i не превосходит цвет вершины ν j. Доказано, что оптимальная раскраска смешанного графа G = (V, A, E) эквивалентна задаче GcMPT|pi = 1|Cmax поиска оптимального расписания обслуживания частично упорядоченных требований с единичными (одинаковыми) длительностями. В отличие от классических задач построения расписаний в рассматриваемой задаче GcMPT|pi = 1|Cmax необходимо несколько различных приборов для обслуживания отдельного требования. Помимо отношений предшествования, заданных на множестве требований V {ν1, ν2, …, νn} должно выполняться некоторое подмножество требований одновременно. На основании доказанных в статье теорем утверждается, что множество аналитических результатов, полученных ранее для задач GcMPT|pi = 1|Cmax, имеют аналоги для оптимальных раскрасок смешанных графов G = (V, A, E), и наоборот.

Биография автора

Юрий Назарович Сотсков, Объединенный институт проблем информатики НАН Беларуси, ул. Сурганова, 6, 220012, г. Минск, Беларусь

доктор физико-математических наук, профессор; главный научный сотрудник лаборатории математической кибернетики.

Литература

  1. Wan L, Mei J, Du J. Two-agent scheduling of unit processing time jobs to minimize total weighted completion time and total weighted number of tardy jobs. European Journal of Operational Research. 2021;290(1):26–35. DOI: 10.1016/j.ejor.2020.07.064.
  2. Sotskov YN, Tanaev VS. [A chromatic polynomial of a mixed graph]. Izvestiya Akademii nauk BSSR. Seriya fiziko-matematicheskikh nauk. 1976;6:20–23. Russian.
  3. Karp RM. Reducibility among combinatorial problems. In: Miller RE, Thatcher JW, Bohlinger JD, editors. Complexity of computer computations. Boston: Springer; 1972. p. 85–103. DOI: 10.1007/978-1-4684-2001-2_9.
  4. Sotskov YN, Dolgui A, Werner F. Mixed graph coloring for unit-time job-shop scheduling. International Journal of Mathematical Algorithms. 2001;2:289–323.
  5. Sotskov YN, Tanaev VS, Werner F. Scheduling problems and mixed graph colorings. Optimization. 2002;51(3):597–624. DOI: 10.1080/0233193021000004994.
  6. Al-Anzi FS, Sotskov YN, Allahverdi A, Andreev GV. Using mixed graph coloring to minimize total completion time in job shop scheduling. Applied Mathematics and Computation. 2006;182(2):1137–1148. DOI: 10.1016/j.amc.2006.04.063.
  7. Kouider A, Ait Haddadène H, Ourari S, Oulamara A. Mixed graph colouring for unit-time scheduling. International Journal of Production Research. 2017;55(6):1720–1729. DOI: 10.1080/00207543.2016.1224950.
  8. Kouider A, Ait Haddadène H, Oulamara A. On minimization of memory usage in branch-and-bound algorithm for the mixed graph coloring: application to the unit-time job shop scheduling. Computer & Operations Research. 2019;4967:1001–1008.
  9. Lenstra JK, Rinnooy Kan AHG. Computational complexity of discrete optimization problems. Annals of Discrete Mathematics. 1979;4:121–140. DOI: 10.1016/S0167-5060(08)70821-5.
  10. Sotskov YN. Complexity of optimal scheduling problems with three jobs. Cybernetics. 1990;26(5):686–692. DOI: 10.1007/ BF01068549.
  11. Sotskov YN. The complexity of shop-scheduling problems with two or three jobs. European Journal of Operational Research. 1991;53(3):326–336. DOI: 10.1016/0377-2217(91)90066-5.
  12. Sotskov YN, Shakhlevich NV. NP-hardness of shop-scheduling problems with three jobs. Discrete Applied Mathematics. 1995; 59(3):237–266. DOI: 10.1016/0166-218X(95)80004-N.
  13. Kravchenko SA, Sotskov YN. Optimal makespan schedule for three jobs on two machines. Mathematical Methods of Operations Research. 1996;43(2):233–238. DOI: 10.1007/BF01680374.
  14. Gonzalez T. Unit execution time shop problems. Mathematics of Operations Research. 1982;7(1):57–66. DOI: 10.1287/ moor.7.1.57.
  15. Brucker P, Kravchenko SA, Sotskov YN. On the complexity of two machine job-shop scheduling with regular objective functions. OR Spektrum. 1997;19:5–10. DOI: 10.1007/BF01539799.
  16. Shakhlevich NV, Sotskov YN. Scheduling two jobs with fixed and nonfixed routes. Computing. 1994;52(1):17–30. DOI: 10.1007/BF02243393.
  17. Shakhlevich NV, Sotskov YN, Werner F. Shop-scheduling problems with fixed and non-fixed machine orders of the jobs. Annals of Operations Research. 1999;92:281–304. DOI: 10.1023/A:1018943016617.
  18. Damaschke P. Parameterized mixed graph coloring. Journal of Combinatorial Optimization. 2019;38:326–374. DOI: 10.1007/ s10878-019-00388-z.
  19. Hansen P, Kuplinsky J, de Werra D. Mixed graph colorings. Mathematical Methods of Operations Research. 1997;45:145–160. DOI: 10.1007/BF01194253.
  20. Kruger K, Sotskov YN, Werner F. Heuristics for generalized shop scheduling problems based on decomposition. International Journal of Production Research. 1998;36(11):3013–3033. DOI: 10.1080/002075498192265.
  21. Sotskov YN. Software for production scheduling based on the mixed (multi)graph approach. Computing & Control Engineering Journal. 1996;7(5):240–246. DOI: 10.1049/CCE:19960509.
  22. Sotskov YN. Mixed multigraph approach to scheduling jobs on machines of different types. Optimization. 1997;42(3):245–280. DOI: 10.1080/02331939708844361.
  23. de Werra D. Restricted coloring models for timetabling. Discrete Mathematics. 1997;165–166:161–170. DOI: 10.1016/S0012 365X(96)00208-7.
  24. de Werra D. On a multiconstrained model for chromatic scheduling. Discrete Applied Mathematics. 1999;94(1–3):171–180. DOI: 10.1016/S0166-218X(99)00019-0.
  25. Sotskov YN. Mixed graph colorings: a historical review. Mathematics. 2020;8(3):385. DOI: 10.3390/math8030385.
  26. Harary F. Graph theory. Massachusetts: Addison-Wesley; 1969. 274 p.
  27. Thulasiraman K, Swamy MNS. Graphs: theory and algorithms. Canada: John Wiley & Sons, Inc.; 1992. 480 p. DOI: 10.1002/ 9781118033104.
  28. Tanaev VS, Sotskov YN, Strusevich VA. Scheduling theory. Multi-stage systems. Dordrecht: Kluwer Academic Publishers; 1994. 406 p. DOI: 10.1007/978-94-011-1192-8.
  29. Brucker P. Scheduling algorithms. Berlin: Springer; 1995. 326 p. DOI: 10.1007/978-3-662-03088-2.
  30. Graham RL, Lawler EL, Lenstra JK, Rinnooy Kan AHG. Optimization and approximation in deterministic sequencing and scheduling: a survey. Annals of Discrete Mathematics. 1979;5:287–326. DOI: 10.1016/S0167-5060(08)70356-X.
  31. Sotskov YN, Tanaev VS. Scheduling theory and practice: Minsk group results. Intelligent Systems Engineering. 1994;3(1):1–8. DOI: 10.1049/ISE.1994.0001.
  32. Sussmann B. Scheduling problems with interval disjunctions. Mathematical Methods of Operations Research. 1972;16:165–178.
  33. Brucker P, Krämer A. Shop scheduling problems with multiprocessor tasks on dedicated processors. Annals of Operations Research. 1995;57(1):13–27. DOI: 10.1007/BF02099688.
  34. Brucker P, Krämer A. Polynomial algorithms for resource-constrained and multiprocessor task scheduling problems. European Journal of Operational Research. 1996;90(2):214–226. DOI: 10.1016/0377-2217(95)00350-9.
  35. Hoogeveen JA, van de Velde SL, Veltman B. Complexity of scheduling multiprocessor tasks with prespecified processor allocations. Discrete Applied Mathematics. 1994;55(3):259–272. DOI: 10.1016/0166-218X(94)90012-4.
  36. Hoogeveen JA, Lenstra JK, Veltman B. Preemptive scheduling in a two-stage multiprocessor flow shop is NP-hard. European Journal of Operational Research. 1996;89(1):172–175. DOI: 10.1016/S0377-2217(96)90070-3.
Опубликован
2021-08-05
Ключевые слова: оптимизация, расписание с единичными длительностями, быстродействие, смешанный граф, вершинная раскраска
Поддерживающие организации Это исследование выполнено при частичной финансовой поддержке Белорусского республиканского фонда фундаментальных исследований (проект № Ф21-010).
Как цитировать
Сотсков, Ю. Н. (2021). Раскраска смешанного графа как построение расписания обслуживания многопроцессорных требований с одинаковыми длительностями. Журнал Белорусского государственного университета. Математика. Информатика, 2, 67-81. https://doi.org/10.33581/2520-6508-2021-2-67-81
Выпуск
№ 2 (2021): Журнал Белорусского государственного университета. Математика. Информатика
Раздел
Дискретная математика и математическая кибернетика

Copyright (c) 2021 Журнал Белорусского государственного университета. Математика. Информатика

Лицензия Creative Commons

Это произведение доступно по лицензии Creative Commons «Attribution-NonCommercial» («Атрибуция — Некоммерческое использование») 4.0 Всемирная.

Авторы, публикующиеся в данном журнале, соглашаются со следующим:

  1. Авторы сохраняют за собой авторские права на работу и предоставляют журналу право первой публикации работы на условиях лицензии Creative Commons Attribution-NonCommercial. 4.0 International (CC BY-NC 4.0).
  2. Авторы сохраняют право заключать отдельные контрактные договоренности, касающиеся неэксклюзивного распространения версии работы в опубликованном здесь виде (например, размещение ее в институтском хранилище, публикацию в книге) со ссылкой на ее оригинальную публикацию в этом журнале.
  3. Авторы имеют право размещать их работу в интернете (например, в институтском хранилище или на персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу. (См. The Effect of Open Access).