Рус Eng За 365 дней одобрено статей: 2127,   статей на доработке: 286 отклонено статей: 924 
Библиотека
Статьи и журналы | Тарифы | Оплата | Ваш профиль

Вагина М.Ю., Нигматулин Р.М. Некоторые оценки времени выполнения конкурирующих работ при пакетном планировании

Опубликовано в журнале "Программные системы и вычислительные методы" в № 3 за 2017 год на страницах 54-60.

Аннотация: Предметом исследования являются теоретико-графовые модели решения задачи минимизации времени выполнения конкурирующих работ при пакетном планировании. Большой интерес к таким задачам объясняется многочисленными приложениями, которые встречаются в теории расписаний, в планировании производства и маршрутов перевозок, в распределительных вычислениях и др. В общем случае не существует эффективного алгоритма решения этих задач. Особое внимание в данной статье уделяется применению раскраски графа конфликтов, позволяющей строить оценки минимального времени выполнения всех работ. Основными методами исследования являлись методы теории графов и вычислительный эксперимент. Особое внимание уделялось применению раскраски графов. На основе раскраски графа конфликтов построены двусторонние оценки минимального времени выполнения конкурирующих работ при пакетном планировании. Все найденные оценки достижимы. Они представляют собой линейные комбинации временных промежутков выполнения пакетов работ. Коэффициенты линейной комбинации выражаются через различные характеристики графа конфликтов, его подграфов (например, хроматическое число, плотность графа).

Ключевые слова: хроматическое число графа, минимальная раскраска, граф конфликтов, теоретико-графовая модель, пакетное планирование, конкурирующие работы, полный подграф, время завершения работ, минимальное время, расписание выполнения работ

Информация о гранте: Работа подготовлена при финансовой поддержке ФГБОУ ВО «ШГПУ» по договору на выполнение НИР от 27.04.2017 г. № 16-518 по теме: «Построение и исследование математических моделей некоторых оптимизационных задач, сводящихся к раскраске графов».

DOI: 10.7256/2307-9118.2013.01.7

Эта статья недоступна для пользователей, которые не вошли в цифровую библиотеку издательства под своим логином и паролем. Перейдите по ссылке, чтобы зарегистрироваться или осуществить вход.

Если вы один из авторов этой статьи, вы можете открыть бесплатный доступ к этой статье для своих читателей. Вы должны зайти под своим логином и паролем, чтобы воспользоваться услугой. Перейдите по ссылке, чтобы зарегистрироваться или осуществить вход.

Библиография:
Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графов. М.: Наука, 1990. 384 с.
Кристофидес Н. Теория графов. Алгоритмический подход. М.: Мир, 1978. 432 с.
Нигматулин Р.М., Вагина М.Ю. Построение оценок времени в обобщенной задаче оптимального распределения оборудования // Математическое и компьютерное моделирование: сборник материалов IV Международной научной конференции.-Омск: Изд-во Ом. гос. ун-та. 2016. С. 60-62.
Робертс Ф.С. Дискретные математические модели с приложениями к социальным, биологическим и экологическим задачам. М.: Наука, 1986. 496 с.
Al-Anzi F.S., Sotskov Y.N., Allahverdi A., Andreev G. V. Using mixed graph coloring to minimize total completion time in job shop scheduling // Applied Mathematics and Computation. 2006. vol. 182. pp. 1137-1148.
Byskov J.M. Enumerating maximal independent sets with applications to graph colouring // Operations Research Letters. Vol. 32 (6). 2004. pp. 547-556.
Furini F., Malaguti E. Exact weighted vertex coloring via branch-and-price // Discrete Optimization. 2012. vol. 9. pp. 130-136.
Jin Y., Hamiez JP., Hao JK. Algorithms for the minimum sum coloring problem: a review // Artificial Intelligence Review. 2017. vol. 47, no. 3. pp. 367-394.
Lewis R., Thompson J. On the application of graph colouring techniques in round-robin sports scheduling // Computers and Operations Research. 2011. vol. 38. no. 1, pp. 190-204.
Lewis R. A Guide to Graph Colouring: Algorithms and Applications. N.-Y.: Springer, 2015. 253 p.
Marx D. Graph colouring problems and their applications in scheduling // Periodica Polytechnica, Electrical Engineering. 2004. vol. 48. no. 1-2. pp. 11-16.
Thomassen С., Erds P., Alavi Y., Malde P., Schwenk A. Tight bounds on the chromatic sum of a connected graph // Graph Theory. 1989. vol. 13. no. 3, pp. 353-357.

Правильная ссылка на статью:
просто выделите текст ссылки и скопируйте в буфер обмена