Some algorithms for constructing the following shedules are developed: 1) one-processor schedule with a partial precedence, 2) a multiprocessor schedule without idle time and conditions of partial precedence.
Download file
Counter downloads: 312
- Title Chain structures in schedules tasks
- Headline Chain structures in schedules tasks
- Publesher
Tomsk State University - Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 3(33)
- Date:
- DOI 10.17223/20710410/33/5
Keywords
расписание, граф, алгоритм, раскраска, сложность, schedule, graph, algorithm, colors, complexityAuthors
References
Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984. 455 с.
Асратян А. С., Камалян Р. Р. Интервальные раскраски ребер мультиграфа // Прикладная математика. Вып. 5. Ереван: Изд-во Ереванского ун-та, 1987. C. 25-34.
Танаев В. С., Сотсков Ю. Н., Струсевич В. А. Теория расписаний. Многостадийные системы. М.: Наука, 1989. 328 с.
Магомедов А. М. К вопросу об интервальной Д-раскраске двудольных графов // Автоматика и телемеханика. 2015. №1. С. 101-109.
Магомедов А. М., Магомедов Т. А. Реберно-вершинные инцидентные паросочетания в задачах расписаний // Прикладная дискретная математика. 2015. №1(27). С. 92-95.
Магомедов А. М., Магомедов Т. А. Последовательное разбиение ребер двудольного графа на паросочетания // Дискретная математика. 2016. Т. 28. Вып. 1. С. 78-86.
Емеличев В. А, Мельников О. И., Сарванов В. И., Тышкевич Р. И. Последовательное разбиение ребер двудольного графа на паросочетания. М.: Книжный дом «Либроком», 2009. 392 с.
Севастьянов С. В. Об интервальной раскрашиваемости ребер двудольного графа // Методы дискретного анализа. 1990. Т. 50. С. 61-72.
Камалян Р.Р. Интервальные раскраски полных двудольных графов и деревьев / Препринт ВЦ АН АрмССР. Ереван, 1989. 11c.
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.
Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М.: Мир, 1979. 536 с.
Petersen J. Die Theorie der regularen Graphs // Acta Math. 1891. No. 15. P. 193-220.
Tucker A. Ch. 2. Covering Circuits and Graph Colorings // Appl. Combinat. 5th Ed. Hoboken: John Wiley & Sons, 2006. P. 49.
Lawler E. L. Combinatorial Optimization: Networks and Matroids. N. Y.: Holt, Rinehart and Winston, 1976.
Giaro K. Compact task scheduling on dedicated processors with no waiting period. PhD thesis. Technical University of Gdansk, IETI Faculty, Gdansk, 1999. (in Polish)
Chain structures in schedules tasks | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2016. № 3(33). DOI: 10.17223/20710410/33/5
Download full-text version
Counter downloads: 1054
- ВКонтакте
- РћРТвЂВВВВВВВВнокласснРСвЂВВВВВВВВРєРСвЂВВВВВВВВ
- Telegram