Доктор технических наук, доцент, ведущий научный сотрудник
117342, Москва, ул. Профсоюзная, 65
Кандидат технических наук
117342, Москва, ул. Профсоюзная, 65
Кандидат технических наук
305040, Курск, ул. 50 лет Октября, 94
В статье рассматривается применение метода сетевого программирования к решению дискретной задачи минимизации стоимости проекта при заданной продолжительности его реализации. Суть метода состоит в том, что целевую функцию и ограничение в задаче календарного планирования можно представить в виде суперпозиции более простых функций. Такое представление удобно изображать в виде сети, на нижнем уровне которой находятся вершины, соответствующие переменным (входы сети), промежуточные вершины соответствуют функциям, входящим в суперпозицию, а конечная вершина (выход) соответствует исходной функции.
Задачи календарного планирования очень распространены на практике и при этом относятся к классу NP-трудных, что делает актуальной разработку алгоритмов их решения. В работе описаны два базовых алгоритма решения задачи для случаев независимых и последовательных работ. Более сложные случаи (сеть типа дерева и агрегируемая сеть) могут быть представлены в виде комбинации этих случаев и решаются на основе последовательного применения базовых алгоритмов. В качестве примера производственного сетевого графика приводится сеть типа «сборка с комплектующими». Для нее предлагается метод, который состоит в определении множества работ, фиксация продолжительности которых приводит к одному из рассмотренных выше случаев (либо сеть-дерево, либо – агрегируемая сеть). Далее рассматриваются все возможные варианты фиксации продолжительностей работ выделенного множества и решение задачи для каждого варианта. Из всех вариантов выбирается лучший.
Предложенные в статье алгоритмы могут быть полезны в управлении проектами, в частности – при решении задач календарного планирования.
The article considers the application of the network programming method to the solution of the discrete problem of minimizing the cost of the project for a given duration of its implementation. The essence of the method is that the target function and the restriction in the scheduling problem can be represented as a superposition of simpler functions. This representation is convenient to depict in the form of a network, at the lower level of which there are vertices corresponding to variables (network inputs), intermediate vertices correspond to the functions included in the superposition, and the final vertex (output) corresponds to the original function.
Calendar planning tasks are very common in practice and at the same time belong to the class of NP-difficult. This makes the development of algorithms for their solution actual. The paper describes two basic algorithms for solving the problem for the cases of independent and sequential works. More complex cases (tree-type network and an aggregated network) can be represented as a combination of these cases and solved based on sequential application of basic algorithms. As an example of a production network is given a network of the type "Assembly with a components". For it the method which consists in definition of a set of works which fixing of duration leads to one of the cases considered above (tree-type network or aggregated network) is offered. Next all possible options for fixing the duration of the work of the selected set and the solution of the problem for each option are considered. The best of all the options is chosen.
The algorithms proposed in paper may be useful in the of the project management, particularly in solving scheduling tasks.
The authors declare that there are no conflicts of interest present.