О заполнении растущих деревьев источником, находящемся в корне
Ключевые слова:
методы оптимизации, эффективная заправка, планирование производства, алгоритмы, корневое поддерево, заполнение вершин ориентированного графа
Аннотация
В работе рассмотрена оптимизационная задача о заполнении растущих деревьев источником, находящемся в корне. Построены алгоритмы работы этого источника по заполнению графа минимизирующие время заполнения корневого дерева. Полностью рассмотрен случай, когда количество дуг, исходящих из корня, не превышает 3-х, а мощность источника не превосходит 2. Затем рассмотрены некоторые более общие случаи, когда мощность источника и количество корневых поддеревьев произвольны. Сформулированы и доказаны теоремы о существовании оптимальных параллельных стратегий заполнения дерева для некоторых общих случаев и описаны сами оптимальные стратегии. Предложено улучшение построенного алгоритма заполнения дерева за счёт уменьшения количества переключений мощности источника между корневыми поддеревьями. Для всех результатов приведены иллюстрирующие примеры.
Скачивания
Данные скачивания пока не доступны.
Литература
1. Форд, Л. Р. Потоки в сетях / Л. Р. Форд, Д. Р. Фалкерсон. – М. : Мир, 1966, 276 c.
2. Жилякова, Л. Ю. Теория ресурсных сетей: монография / Л. Ю. Жилякова, О. П. Кузнецов. – М. : РИОР: ИНФРА-М, 2017. – 283 с.
3. Жилякова, Л. Ю. Эргодические циклические ресурсные сети. I. Колебания и равновесные состояния при малых ресурсах / Л. Ю. Жилякова // Управление большими системами. Выпуск 43, М. : ИПУ РАН, 2013. – С. 34–54.
4. Жилякова, Л. Ю. Эргодические циклические ресурсные сети. II. Большие ресурсы / Л. Ю. Жилякова // Управление большими системами. Выпуск 45, М. : ИПУ РАН, 2013. – С. 6–29.
5. Kuznetsov, O. P. Nonsymmetric resource networks. The study of limit states. / O. P. Kuznetsov, L. Yu. Zhilyakova // Management and Production Engineering Review. Volume 2, Number 3, September 2011. – pp. 33–39
6. Жилякова, Л. Ю. Теория ресурсных сетей: монография / Л. Ю. Жилякова, О. П. Кузнецов. – М. : РИОР : ИНФРА-М, 2017. – 283 с. – (Научная мысль). – URL: doi.org/ 10.12737/21451
7. Ерусалимский, Я. М. Графы с вентильной достижимостью. Марковские процессы и потоки в сетях / Я. М. Ерусалимский, В. А. Скороходов // Известия вузов. Северо-Кавказский регион. Естественные науки. – 2003. – No 2. – C. 3–5.
8. Ерусалимский Я. М. Графы с нестандартной достижимостью. Задачи, приложения: монография / Я. М. Ерусалимский, В. А. Скороходов, М. В. Кузьминова, А. Г. Петросян. – Ростов-на-Дону : ЮФУ, 2009. – 195 с.
9. Ерусалимский Я. М. Случайные блуждания по графу-решётке и комбинаторные тождества / Я. М. Ерусалимский // Инженерный вестник Дона. – 2015. – No 2, Ч. 2 – 12 с. – URL: http://ivdon.ru/ru/magazine/archive/n2p2y2015/2964
10. Erusalimskiy, I. On the Dynamic Flows in Networks / I. Erusalimskiy // Universal J. of Communications and Network. – 2014. – v 2. – # 6. – P. 101–105. – URL: DOI: 10.13189
11. Ерусалимский, Я. М. Графы с затуханием на дугах и усилением в вершинах и маршрутизация в информационных сетях / Я. М. Ерусалимский, // Инженерный вестник Дона. – 2015. – No 1. – 12 с. – URL: http:// ivdon.ru/ru/magazine/archive/n1y2015/2782
12. Жилякова, Л. Ю. Графовые динамические модели и их свойства / Л. Ю. Жилякова // Автоматика и телемеханика. – 2015. – No 8. – C. 115–139.
13. Орлов, В. В. О заполнении вершин ориентированного графа / В. В. Орлов // Инженерный вестник Дона. – 2017. – Т. 47, No 4(47). – С. 114. – URL: http://www.ivdon.ru/ru/magazine/archive/n4y2017/4574
14. Ерусалимский, Я. М. Методы оптимизации и инновации / Я. М. Ерусалимский, В. В. Орлов // Управление экономическими системами: электронный научный журнал. – 2018. – No 8 (114). – URL: http://uecs.ru/instrumentalnii-metody-ekonomiki/item/5057-2018-08-22-07-39-25
15. Ерусалимский, Я. М. Потенциальный оператор, функция Грина на ориентированных графах и некоторые их приложения в квантовой механике / Я. М. Ерусалимский, Д. В. Степовой // Известия вузов. Северо-Кавказский регион. Естественные науки. – 2001, спецвыпуск. – С. 67–71.
16. Ерусалимский, Я. М. Дискретная математика: теория, задачи, приложения. – 3-е издание изд. – М. : Вузовская книга, 2000. – 288 c.
17. Байрактаров, Б. Р. Алгоритм «веерной» оптимизации параметров разветвленных трубопроводных сетей / Б. Р. Байракта-ров, В. Ч. Кудаев // Известия Высших учебных заведений. Северо-Кавказский регион. Естественные науки. – 2005. – No 2. – С. 2–5.
18. Байрактаров, Б. Р. Задача распределения потоков в кольцевых трубопроводных сетях / Б. Р. Байрактаров // Известия высших учебных заведений. Северо-Кавказский регион. Серия: Естественные науки. – 2005. – No S1. – С. 1–9.
19. Кудаев, В. Ч. Задачи оптимального проектирования сетей Киргхофа: автореферат диссертации кандидата физико-математических наук: 05.13.16. – Ростов-на-Дону, 1993. – 18 с.
2. Жилякова, Л. Ю. Теория ресурсных сетей: монография / Л. Ю. Жилякова, О. П. Кузнецов. – М. : РИОР: ИНФРА-М, 2017. – 283 с.
3. Жилякова, Л. Ю. Эргодические циклические ресурсные сети. I. Колебания и равновесные состояния при малых ресурсах / Л. Ю. Жилякова // Управление большими системами. Выпуск 43, М. : ИПУ РАН, 2013. – С. 34–54.
4. Жилякова, Л. Ю. Эргодические циклические ресурсные сети. II. Большие ресурсы / Л. Ю. Жилякова // Управление большими системами. Выпуск 45, М. : ИПУ РАН, 2013. – С. 6–29.
5. Kuznetsov, O. P. Nonsymmetric resource networks. The study of limit states. / O. P. Kuznetsov, L. Yu. Zhilyakova // Management and Production Engineering Review. Volume 2, Number 3, September 2011. – pp. 33–39
6. Жилякова, Л. Ю. Теория ресурсных сетей: монография / Л. Ю. Жилякова, О. П. Кузнецов. – М. : РИОР : ИНФРА-М, 2017. – 283 с. – (Научная мысль). – URL: doi.org/ 10.12737/21451
7. Ерусалимский, Я. М. Графы с вентильной достижимостью. Марковские процессы и потоки в сетях / Я. М. Ерусалимский, В. А. Скороходов // Известия вузов. Северо-Кавказский регион. Естественные науки. – 2003. – No 2. – C. 3–5.
8. Ерусалимский Я. М. Графы с нестандартной достижимостью. Задачи, приложения: монография / Я. М. Ерусалимский, В. А. Скороходов, М. В. Кузьминова, А. Г. Петросян. – Ростов-на-Дону : ЮФУ, 2009. – 195 с.
9. Ерусалимский Я. М. Случайные блуждания по графу-решётке и комбинаторные тождества / Я. М. Ерусалимский // Инженерный вестник Дона. – 2015. – No 2, Ч. 2 – 12 с. – URL: http://ivdon.ru/ru/magazine/archive/n2p2y2015/2964
10. Erusalimskiy, I. On the Dynamic Flows in Networks / I. Erusalimskiy // Universal J. of Communications and Network. – 2014. – v 2. – # 6. – P. 101–105. – URL: DOI: 10.13189
11. Ерусалимский, Я. М. Графы с затуханием на дугах и усилением в вершинах и маршрутизация в информационных сетях / Я. М. Ерусалимский, // Инженерный вестник Дона. – 2015. – No 1. – 12 с. – URL: http:// ivdon.ru/ru/magazine/archive/n1y2015/2782
12. Жилякова, Л. Ю. Графовые динамические модели и их свойства / Л. Ю. Жилякова // Автоматика и телемеханика. – 2015. – No 8. – C. 115–139.
13. Орлов, В. В. О заполнении вершин ориентированного графа / В. В. Орлов // Инженерный вестник Дона. – 2017. – Т. 47, No 4(47). – С. 114. – URL: http://www.ivdon.ru/ru/magazine/archive/n4y2017/4574
14. Ерусалимский, Я. М. Методы оптимизации и инновации / Я. М. Ерусалимский, В. В. Орлов // Управление экономическими системами: электронный научный журнал. – 2018. – No 8 (114). – URL: http://uecs.ru/instrumentalnii-metody-ekonomiki/item/5057-2018-08-22-07-39-25
15. Ерусалимский, Я. М. Потенциальный оператор, функция Грина на ориентированных графах и некоторые их приложения в квантовой механике / Я. М. Ерусалимский, Д. В. Степовой // Известия вузов. Северо-Кавказский регион. Естественные науки. – 2001, спецвыпуск. – С. 67–71.
16. Ерусалимский, Я. М. Дискретная математика: теория, задачи, приложения. – 3-е издание изд. – М. : Вузовская книга, 2000. – 288 c.
17. Байрактаров, Б. Р. Алгоритм «веерной» оптимизации параметров разветвленных трубопроводных сетей / Б. Р. Байракта-ров, В. Ч. Кудаев // Известия Высших учебных заведений. Северо-Кавказский регион. Естественные науки. – 2005. – No 2. – С. 2–5.
18. Байрактаров, Б. Р. Задача распределения потоков в кольцевых трубопроводных сетях / Б. Р. Байрактаров // Известия высших учебных заведений. Северо-Кавказский регион. Серия: Естественные науки. – 2005. – No S1. – С. 1–9.
19. Кудаев, В. Ч. Задачи оптимального проектирования сетей Киргхофа: автореферат диссертации кандидата физико-математических наук: 05.13.16. – Ростов-на-Дону, 1993. – 18 с.
Опубликован
2019-07-04
Как цитировать
Орлов, В. В. (2019). О заполнении растущих деревьев источником, находящемся в корне. Вестник ВГУ. Серия: Системный анализ и информационные технологии, (3), 63-70. https://doi.org/10.17308/sait.2019.3/1306
Выпуск
Раздел
Математические методы системного анализа и управления
- Авторы сохраняют за собой авторские права и предоставляют журналу право первой публикации работы, которая по истечении 6 месяцев после публикации автоматически лицензируется на условиях Creative Commons Attribution License , которая позволяет другим распространять данную работу с обязательным сохранением ссылок на авторов оригинальной работы и оригинальную публикацию в этом журнале.
- Авторы имеют право размещать их работу в сети Интернет (например в институтском хранилище или персональном сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению и большему количеству ссылок на данную работу (См. The Effect of Open Access).
