|
Достоинством методов локальной оптимизации является простота соответствующих алгоритмов. Недостатком схемы является отсутствие оценок близости получаемого решения к оптимальному. В задачах календарного планирования метод локальной оптимизации реализуется, в основном, в так называемых алгоритмах «сглаживания» и в алгоритмах улучшения решения путем изменения очередности работ критического пути. Рассмотрим два простых примера, иллюстрирующих эти подходы. Пример 25] На рис. 1.4.1 приведен сетевой график проекта из 4 работ, которым соответствуют вершины сети. В нижней половине вершин указаны объемы работ. Примем, что количество ресурсов на работах 1и 2 не может превышать 4, а на работах 3 и 4 не может превышать 1. Рис. 1.4.1 На рис. 1.4.2приведен график использования ресурсов при выполнении всех работ с максимальной интенсивностью |
Это решение называется локально-оптимальным. Далее можно взять новое начальное решение и повторить процедуру до получения локально-оптимального решения и т.д. Можно поступить по-другому, расширив окрестность. Если т клокальнооптимальное решение, то определяем окрестность следующим образом пч)= U p M с1-2) Другими словами, Р(тгк) это объединение всех окрестностей решений, принадлежащих окрестности локально-оптимальным решения. Если тгк остается локально-оптимальным решением в новой окрестности, то производим дальнейшее расширение окрестности, либо останавливаемся на полученном решении. Достоинством методов локальной оптимизации является простота соответствующих алгоритмов. Недостатком схемы является отсутствие оценок близости получаемого решения к оптимальному. В задачах календарного планирования метод локальной оптимизации реализуется, в основном, в так называемых алгоритмах «сглаживания» и в алгоритмах улучшения решения путем изменения очередности работ критического пути. Рассмотрим два простых примера, иллюстрирующих эти подходы. П ример 1.1. На рис. 1.1 приведен сетевой график проекта из 4 работ, которым соответствуют вершины сети. В нижней половине вершин указаны объемы работ. Примем, что количество ресурсов на работах 1 и 2 не может превышать 4, а на работах 3 и 4 не может превышать 1. Рис. 1.1. На рис. 1.2 приведен график использования ресурсов при выполнении всех работ с максимальной интенсивностью Заметим, что работы 1 и 3 критические, а работы 2 и 4 имеют полные резервы времени равные 4. Поэтому сдвигаем начало работы 2 на 3 единицы и выполняем ее в интервале (3, 7) тремя единицами ресурсов. При этом, естественно сдвигается работа 4 на 4 единицы. График использования ресурсов после локальной оптимизации на рис. 1.2 заштрихован. 79 |