Моделирование задачи минимизации общих затрат при календарном планировании

Целью данной работы является проведение обзора существующих методов минимизации затрат при календарном планировании за счет сокращения времени выполнения работ.
При сжатии (сокращении длительности) работ происходит сокращение общего времени выполнения проекта. Форсирование работ требует дополнительных расходов на выполнение, что повышает прямые затраты на реализацию проекта. Но, в то же время, за счет сокращения сроков уменьшаются косвенные затраты на выполнение. Таким образом, может быть достигнуто снижение суммарных затрат.
Решение данной задачи можно разделить на следующие подзадачи:
- поиск критических и подкритических путей (необходимость нахождения подкритических путей существует не во всех алгоритмах, о чем будет отдельно сказано при рассмотрении методов)
- выбор работ для сокращения сроков выполнения
- получение величины, на которую будут сокращены продолжительности работ и выполнение сокращения.
Проведение оптимизации одного и того же календарного плана с помощью различных методов позволит сравнивать полученные результаты по различным критериям и сделать выводы об их эффективности в той или иной ситуации. Также сравнение результатов позволяет выявлять сходство методов и общие закономерности в них, на основании которых можно совершенствовать методологию оптимизации.
В работе рассматриваются алгоритмы, описанные в книгах Т.В. Алесинско, С.И. Зуховицкого и Х. Таха.

Сетевое Планирование и Управление (СПУ) - это комплекс графических и расчетных методов, организационных мероприятий, обеспечивающих моделирование, анализ и динамическую перестройку плана выполнения сложных проектов и разработок, например, таких как: строительство и реконструкция каких-либо объектов; выполнение научно-исследовательских и конструкторских работ; подготовка производства к выпуску продукции; перевооружение армии; развертывание системы медицинских или профилактических мероприятий.
Характерной особенностью таких проектов является то, что они состоят из ряда отдельных, элементарных работ. Они обуславливают друг друга так, что выполнение некоторых работ не может быть начато раньше, чем завершены некоторые другие. Например, укладка фундамента не может быть начата раньше, чем будут доставлены необходимые материалы; эти материалы не могут быть доставлены раньше, чем будут построены подъездные пути; любой этап строительства не может быть начат без составления соответствующей технической документации и т.д.
Сетевое Планирование и Управление включает три основных этапа:
1. Структурное планирование;
2. Календарное планирование;
3. Оперативное управление.
Структурное планирование начинается с разбиения проекта на четко определенные операции, для которых определяется продолжительность. Затем строится сетевой график, который представляет взаимосвязи работ проекта. Это позволяет детально анализировать все работы и вносить улучшения в структуру проекта еще до начала его реализации.
Календарное планирование предусматривает построение календарного графика, определяющего моменты начала и окончания каждой работы и другие временные характеристики сетевого графика. Это позволяет, в частности, выявлять критические операции, которым необходимо уделять особое внимание, чтобы закончить проект в директивных срок. Во время календарного планирования определяются временные характеристики всех работ с целью проведения оптимизации сетевой модели, которая улучшает...

В работе были рассмотрены три метода решения задачи оптимизации календарного графика по критерию «время- затраты».
Анализируя все три метода, прежде всего можно сказать, что их основным различием является определение величины сжатия работ Δt(i,j).
Первый метод решения данной задачи отличает необходимость нахождения подкритического пути, для чего требуются дополнительные вычисления. Если для поиска путей применяется матрица путей, большой объем вычислений требуется только на предварительном этапе, после чего мы можем легко находить как критические, так и подкритические пути простым сравнением длительностей всех путей в матрице. Также необходимо отметить, что в этом случае задача поиска путей решается одним алгоритмом.
Второй подход подразумевает нахождение критических и подкритических путей с помощью двух разных алгоритмов. Еще одним нюансом является необходимость выполнения поиска путей в каждой итерации. По отдельности данные алгоритмы требуют меньшей вычислительной нагрузки, но необходимость их одновременного применения на каждом шаге доказывает большую эффективность алгоритма матрицы путей для данного метода.
Анализирую таблицу итераций можно заметить, что на определенных этапах мы выполняем сжатие одних и тех же работ на протяжении нескольких итераций (работа 1-2 в итерациях 7-9), что увеличивает объем вычислений. Этот нюанс можно отнести к недостаткам алгоритма.
Второй метод решения задачи исключает необходимость нахождения подкритических путей. В этом случае выбор между алгоритмами нахождения критических путей более сложен, поскольку вычислительные нагрузки практически одинаковы, однако в первом случае большая часть вычислений приходится на нулевой этап, а во втором – распределена между этапами равномерно. Таким образом, может быть выбран любой из вариантов нахождения критических путей.
Сложность самого метода по сравнению с предыдущим заключается в необходимости на каждом шаге пересчитывать временные параметры работ, что увеличивает объем...