Preview

Известия Юго-Западного государственного университета

Расширенный поиск

ПРИМЕНЕНИЕ МЕТОДА СЕТЕВОГО ПРОГРАММИРОВАНИЯ В ЗАДАЧАХ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ

https://doi.org/10.21869/2223-1560-2018-22-5-119-126

Аннотация

В статье рассматривается применение метода сетевого программирования к решению дискретной задачи минимизации стоимости проекта при заданной продолжительности его реализации. Суть метода состоит в том, что целевую функцию и ограничение в задаче календарного планирования можно представить в виде суперпозиции более простых функций. Такое представление удобно изображать в виде сети, на нижнем уровне которой находятся вершины, соответствующие переменным (входы сети), промежуточные вершины соответствуют функциям, входящим в суперпозицию, а конечная вершина (выход) соответствует исходной функции.

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

Предложенные в статье алгоритмы могут быть полезны в управлении проектами, в частности – при решении задач календарного планирования.

Об авторах

И. В. Буркова
Институт РАН проблем управления им. В.А. Трапезникова
Россия

Доктор технических наук, доцент, ведущий научный сотрудник

117342, Москва, ул. Профсоюзная, 65



Б. К. Уандыков
Институт РАН проблем управления им. В.А. Трапезникова
Россия

Кандидат технических наук

117342, Москва, ул. Профсоюзная, 65



Ю. А. Халин
ФГБОУ ВО «Юго-Западный государственный университет»
Россия

Кандидат технических наук

305040, Курск, ул. 50 лет Октября, 94



Список литературы

1. Сетевые модели и задачи управления /В.Н. Бурков, Б.Д. Ланда, С.Е. Ловецкий [и др.]. М.: Советское радио, 1967. 144с.

2. Математические основы управления проектами / С.А. Баркалов, И.В. Буркова, В.И. Воропаев [и др.]; под ред. В.Н. Буркова. М.: Высшая школа, 2005. 423 с.

3. AndresC., HatamiS. Evolutionary heuristics and an algorithm for the two-stage assembly scheduling problem to minimize makespan with setup times // International Journal of Production Research. 2011. 44.Pp. 4713-4735.

4. Allaoui H., Artiba A.Johnson’s algorithm: a kay to solve optimally or approximately flow shop scheduling problems with unavailability periods // International Journal of Production Economics. 2009. 121.Pp. 81-87.

5. Chenkong V., Haimes Y.Y. The tree stage assembly permutation flowshop scheduling problem. Proceedings of the 5th International Conference on Industrial Engineering and Industrial Management, Cartagena.September 7-9, 2011.

6. Demeulemeester E.L., Herroelen W., Project scheduling: a research handbook. Kluwer Academic Publisher, 1976.P. 710.

7. Garey M.R. The complexity of flow-shop and jobshop scheduling // Mathematics of Operations Research 1976. №1 (2).Pp. 117-129.

8. Sun Y., Zhang C.Y., Gao L., Wang X.J. Multy-objactive optimization algorithms for flow shop scheduling problem: a review and prospects // International Journal of Advanced Manufacturing Technology. 2011. 55.Pp. 723-739.

9. Лисицин Л.А., Халин Ю.А., Лисицин А.Л. Системы поддержки принятия управленческих решений в условиях неполной информации // Известия Юго-Западного государственного университета. 2012. № 4-2 (43). С. 95-99.

10. Халин Ю.А., Сизов А.С., Игнатенко А.Н. Нечётко-множественная модель многокритериальной оценки конкурентоспособности предприятия // Известия Юго-Западного государственного университета. 2011. № 5-1 (38). С. 53-57.

11. Кузьбожев Э.Н., Можейко А.Г., Халин Ю.А. Управление инновационными процессами на основе интеллектуальных информационных технологий // Известия Юго-Западного государственного университета. 2011. № 6-2 (39). С. 83-86.

12. Буркова И.В. Метод сетевого программирования в задачах нелинейной оптимизации // Автоматика и телемеханика. 2009. № 10. С. 15-21.


Рецензия

Для цитирования:


Буркова И.В., Уандыков Б.К., Халин Ю.А. ПРИМЕНЕНИЕ МЕТОДА СЕТЕВОГО ПРОГРАММИРОВАНИЯ В ЗАДАЧАХ КАЛЕНДАРНОГО ПЛАНИРОВАНИЯ. Известия Юго-Западного государственного университета. 2018;22(5):119-126. https://doi.org/10.21869/2223-1560-2018-22-5-119-126

For citation:


Burkova I.V., Uandykov B.K., Khalin Yu.A. THE NETWORK PROGRAMMING METHOD APPLICATION IN THE SCHEDULING TASKS. Proceedings of the Southwest State University. 2018;22(5):119-126. (In Russ.) https://doi.org/10.21869/2223-1560-2018-22-5-119-126

Просмотров: 542


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2223-1560 (Print)
ISSN 2686-6757 (Online)