|
Заметим, что работы 1и 3 критические, а работы 2 и 4 имеют полные резервы времени равные 4. Поэтому сдвигаем начало работы 2 на 3 единицы и выполняем ее в интервале (3, 7) тремя единицами ресурсов. При этом, естественно сдвигается работа 4 на 4 единицы. График использования ресурсов после локальной оптимизации на рис. 2.2 заштрихован. Пример 1.4.2 (задача о станках). [25] Требуется обработать пдеталей. Каждая деталь проходит обработку на двух станках. Продолжительность обработки детали ( на первом станке равна а*, а на втором Ь(. Имеется всего один станок первого типа и достаточное количество станков второго типа. Требуется определить очередность обработки деталей, минимизирующую продолжительность обработки всех деталей. На рис. 1.4.3 приведен сетевой график из трех деталей. В нижней половине вершин указаны времена обработки. Возьмем произвольную очередность, например, 1,2,3 (очередность обработки указана пунктиром на рис. 1.4.3, критический путь выделен двойными дугами). Продолжительность обработки Т = 23. Естественно определить соседние решения, как решения, получаемые изменением очередности работ, лежащих на критическом пути. В нашем случае окрестность состоит из одного решения (2,1,3), рис. 1.4.4. 35 Продолжительность обработки Т = 22 уменьшилось. Для нового решения имеем два соседних (1,2,3) и (2,3,1). Из них первое мы уже рассматрива |
Это решение называется локально-оптимальным. Далее можно взять новое начальное решение и повторить процедуру до получения локально-оптимального решения и т.д. Можно поступить по-другому, расширив окрестность. Если т клокальнооптимальное решение, то определяем окрестность следующим образом пч)= 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 Рис. 1.2 Пример 1.2 (задача о станках). Требуется обработать п деталей. Каждая деталь проходит обработку на двух станках. Продолжительность обработки детали i на первом станке равна сц , а на втором Ь< . Имеется всего один станок первого типа и достаточное количество станков второго типа. Требуется определить очередность обработки деталей, минимизирующую продолжительность обработки всех деталей. На рис. 1.3 приведен сетевой график из трех деталей. В нижней половине * вершин указаны времена обработки. Возьмем произвольную очередность, например, 1,2,3 (очередность обработки указана пунктиром на Рис. 1.3, критический путь выделен двойными дугами). Продолжительность обработки Т = 23. Естественно определить соседние решения, как решения, получаемые изменением очередности работ, лежащих на критическом пути. В нашем случае окрестность состоит из одного решения (2,1,3), Рис. 1.4. Продолжительность обработки Т = 22 уменьшилось. Для нового решения имеем два соседних (1,2,3) и (2,3,1). Из них первое мы уже рассматривали. Для 80 |