RESEARCH OF INTERDEPENDENCE OF COST AND PROJECT DURATION IN NETWORK TASKS
УДК 519.86
Ключевые слова: сетевой график, критический путь, задача сетевого планирования, задача о назначениях, оптимизация, длительность выполнения проекта, стоимость проекта.
Для цитирования: Буснюк, Н. Н. Исследование взаимозависимости стоимости и длительности проекта в сетевых задачах / Н. Н. Буснюк // Труды БГТУ. Сер. 3, Физико-математические науки и информатика. - Минск : БГТУ, 2020. - № 1 (230). - С. 88-91.
Аннотация
В зависимости от количества и качества имеющихся у организации трудовых ресурсов и сложности проекта все задачи сетевого планирования можно разбить на виды, к каждому из которых затем разрабатывать специальные эффективные методы решения.
Проект, которому соответствует сетевой граф, характеризуется двумя качественными показателями (критериями) – длительностью выполнения проекта и стоимостью проекта. Первый показатель равен длине критического пути (если веса дуг представляют продолжительности работ), второй характеризуется суммой весов всех дуг графа (если длительность выполнения работы прямо пропорциональна затратам на ее выполнение). Для случая, когда количество работников совпадает с количеством работ, второй показатель будет оптимален (минимален) при расстановке работников в соответствии с решением задачи о назначениях – нахождением совершенного паросочетания минимального веса в полном двудольном графе. Такое оптимальное решение находится точно за полиномиальное время. Возникает вопрос, насколько таким способом найденное решение близко к решению задачи по первому критерию.
В статье доказана теорема о том, что расстановка рабочих на работы в соответствии с оптимальным (минимальным) решением задачи о назначениях дает сколь угодно плохое решение задачи сетевого планирования, а также приведены примеры сетей для некоторых частных случаев дискретной задачи сетевого планирования.
Список литературы
- Буснюк Н. Н. Разновидности задачи сетевого планирования, некоторые методы их решения и алгоритмические оценки // Труды БГТУ. Сер. 3, Физ.-мат. науки и информатика. 2019. № 2. С. 101–104.
- Плескунов М. А. Задачи сетевого планирования. Екатеринбург: Урал. ун-т, 2014. 92 с.
- Буснюк Н. Н., Черняк А. А. Математическое моделирование. Минск: Беларусь, 2014. 216 с.
- Буснюк Н. Н., Новиков В. А. Метод оптимального решения задачи о назначениях в сетевом планировании // Труды БГТУ. 2016. № 6: Физ.-мат. науки и информатика. С. 170–172.
- Буснюк Н. Н., Новиков В. А. Метод решения задачи сетевого планирования при ограниченных трудовых ресурсах // Труды БГТУ. Сер. 3, Физ.-мат. науки и информатика. 2017. № 2. С. 126–128.
