Исследование взаимозависимости стоимости и длительности проекта в сетевых задачах

Abstract

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