Иванов, А.А. Автоматизация технологических процессов и производств

4 .4 . Оптимизация ИПС по производительности 99 Таблица 4.4. Распределение заготовок по трем станкам в динамической системе 4.4.3. Оптимальное расписание при обработке заготовок с переналадкой станка В этом случае при составлении оптимального расписания обра­ ботки Жзаготовок на станке следует учитывать, что каждый раз при переходе от обработки заготовки і к обработке заготовки j требуется время ty на переналадку станка. Число вариантов очередности обработки Жзаготовок составляет /V! и может быть представлено в виде матрицы переналадок станка (табл. 4.5). Таблица 4.5. Матрица переналадок станка № заготовки 1 2 3 N - 1 N 1 X *12 ' і з ' l ( J V - l ) ' u v 2 '2 1 X *23 ' 2 ( Л Ч ) % 3 '3 1 *32 X h ( N - l ) ' з N X Ж - 1 '<2V—1)1 '< Л Г -1 ) 2 '(2V—1)3 X ' ( J V - l ) iV 1 » 'да 'lV 2 'да 'jV(JV—1) X Для решения этой задачи оптимизации рассмотренные выше ал­ горитмы оптимальных расписаний не подходят. Однако достаточно эффективно подобные задачи можно решать с помощью метода вет­ вей и границ [9, 10, 21]. Метод ветвей и границ (МВГ) часто применяется для решения транспортной задачи оптимизации маршрута следования. МВГ позво­ ляет установить, в каком порядке необходимо посетить Ж - 1 пунктов (пункт выезда задан), чтобы суммарные затраты на маршрут были ми­ нимальные. Если не задан начальный пункт маршрута, то получаем