55056

Автор(ы): 

Автор(ов): 

3

Параметры публикации

Тип публикации: 

Статья в журнале/сборнике

Название: 

Применение метода сетевого программирования в задачах календарного планирования

ISBN/ISSN: 

2223-1560

Наименование источника: 

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

Обозначение и номер тома: 

№5 (80)

Город: 

  • Курск

Издательство: 

  • Юго-Западный государственный университет

Год издания: 

2018

Страницы: 

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

Библиографическая ссылка: 

Буркова И.В., Уандыков Б.К., Халин Ю.А. Применение метода сетевого программирования в задачах календарного планирования // Известия Юго-Западного Государственного университета. 2018. №5 (80). С. 119-126.