Аннотация.

Исходные данные к расписанию заданы в виде двудольного графа, где вершинам двух долей графа соотнесены специализированные процессоры и задания соответственно, ребрам – предписанные операции единичной длительности по обработке заданий процессорами. Расписание рассматривается как отображение множества ребер графа в множество положительных целых чисел – «цветов» ребер (множество дискретных временны́ х промежутков единичной длительности, назначенных для выполнения той или иной операции). В качестве теоретико-графовой модели расписания для мультипроцессорной системы без простоев процессоров и прерываний заданий рассматривается реберная интервальная раскраска двудольного графа. Определены необходимые для анализа конструкции графа, с их использованием установлен ряд свойств интервальной раскраски. На основе понятия кусочно-непрерывного пути разработан эвристический алгоритм интервальной раскраски, эффективный для случаев, представляющих интерес как для теории, так и для прикладных задач оптимизации расписаний. Обсуждаются результаты применения программного обеспечения, разработанного на основе эвристического алгоритма, и перспективы работы.

Ключевые слова:

расписание, граф, алгоритм, раскраска, сложность

Стр. 78-84.

Полная версия статьи в формате pdf. 

Литература

1. Свами М., Тхуласираман К. Графы, сети и алгоритмы /Пер. с англ. -- М.: Мир, 1984. 455 с. (Swamy, M.N.S., and K. Thulasiraman. Graphs, Networks and Algorithms. — N.Y.: Wiley, 1980. 612 p.)
2. Асратян А. С., Камалян Р. Р. Интервальные раскраски ребер мультиграфа // Прикладная математика, вып. 5. Ереван: Изд-во Ереванского ун-та. 1987. C. 25-34.
3. Танаев В.С., Сотсков Ю.Н., Струсевич В.А. Теория расписаний. Многостадийные системы. М.: Наука, 1989. – 328 с.
4. Магомедов А.М. К вопросу об интервальной Δ - раскраске двудольных графов // Автоматика и телемеханика. 2015. № 1. C. 101–109.
5. Магомедов А.М., Магомедов Т.А. Реберно-вершинные инцидентные паросочетания в задачах расписаний //Прикладная дискретная математика. 2015. №1 (27). С. 92-95.
6. Магомедов А.М., Магомедов Т.А. Последовательное разбиение ребер двудольного графа на паросочетания //Дискретная математика. 2016. Т. 28. Вып. 1. C. 78-86.
7. Магомедов А.М. Цепочечные структуры в задачах о расписаниях // Прикладная дискретная математика. 2016. №3 (33). С. 67-77.
8. Севастьянов С.В. Об интервальной раскрашиваемости ребер двудольного графа // Методы дискретного анализа. 1990. Т. 50. С. 61-72.
9. Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Книжный дом «Либроком», 2009. – 392 с.
10. Гэри M., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир, 1982. 416 с. (Garey, M. R., and D.S. Johnson. Computers and Intractability. W.H. Freeman, 1979. 347 p.)
11. Petersen, Julius (1891), Die Theorie der regulären graphs, Acta Mathematica 15: p. 193–220.
12. Камалян Р.Р. Интервальные раскраски полных двудольных графов и деревьев // Препринт ВЦ АН Армянской ССР, Ереван. 1989. 11 с.
13. Tucker, Alan. Chapter 2: Covering Circuits and Graph Colorings // Applied Combinatorics. — 5th. — Hoboken: John Wiley & sons, 2006. — P. 49.
14. Lawler, E.L. Combinatorial Optimization: Networks and Matroids. – New York: Holt, Rinehart and Winston, 1976.
15. Giaro, K. Compact task scheduling on dedicated processors with no waiting period (in Polish) // PhD thesis, Technical University of Gdansk, IETI Faculty, Gdansk. 1999.
16. Магомедов А.М. Реберная раскраска двудольных графов // Свидетельство № 2016660830 о государственной регистрации программы для ЭВМ от 22.09.2016.
17. Магомедов А.М. Генерация графов и их раскраска методом жадного алгоритма // Свидетельство № 2017611516 о государственной регистрации программы для ЭВМ от 6.02.2017.