http://npc-news.ru/

Рассмотрим теперь задачу

Рассмотрим теперь задачу оптимального прохождения взаи­мозависимых работ через систему. Пусть длительность выполне­ния к-й работы равна Если fc-я работа выполняется первой, то для подготовки системы, находящейся в исходном состоянии, к обслуживанию требуется времени. Если работа j выполня­ется непосредственно после г-й, то для перенастройки системы требуется время Uj. Если к-я работа выполняется последней, то требуется t^о времени для возврата системы в исходное состоя­ние. Необходимо найти такую последовательность выполнения работ, при которой минимизируется общее время их прохож­дения через систему. Поскольку суммарное время выполнения

Эта задача имеет следующую графическую интерпретацию. Рассмотрим полный ориентированный граф (Х,С/), где X =

= {0, 1…… п} —множество вершин, U — множество дуг. Каждой

дуге {i,j) припишем число (вес) tij, называемое также длиной дуги. Нулевая вершина здесь соответствует начальному и ко­нечному состоянию системы. Требуется найти такой контур, проходящий через каждую вершину только один раз, которому соответствует наименьшая длина, равная сумме длин его дуг. Задачу можно решить, используя все перестановки п задач. Для каждой перестановки вычисляется длина пути на графе. Этот алгоритм решения задачи называется исчерпывающим и имеет экспоненциальную сложность. Однако существуют алгоритмы с меньшей сложностью, которые дают хорошие, хотя не обя­зательно оптимальные решения. Таким алгоритмом является,
например алгоритм GTS [8], который осуществляет поиск на графе, выбирая на каждом шаге дугу с минимальным весом. Алгоритм имеет квадратичную сложность 0(п2).

2.1.2. Системы с многофазным обслуживанием. Рас­смотрим теперь следующую задачу: пусть необходимо выпол­нить п работ, каждая из которых выполняется последовательно в пунктах А и В. Обозначим через Bi время выполнения г-й (г = 1 , …,п) работы в пунктах А и В соответственно. Требу­ется найти оптимальный порядок прохождения п задач через систему, минимизирующий общее время выполнения всех работ. Джонсон предложил ограничиться рассмотрением расписаний, в которых работы на первой фазе (в пункте А) выполняются плотно без простоя до полного завершения [7]. Иначе говоря, работы в пункте А выполняются потоком без дополнительных временных потерь и в заданном порядке.

Выполнение очередной работы в пункте В связано с воз­можным ожиданием завершения обслуживания предыдущей ра­боты. Джонсоном показано, что при доступности всех работ в каждый такт времени оптимальное расписание таково, что

работа г предшествует работе j, если mm{Ai,Bj) < тт(А,-,Д;).

Рассмотрим пример. Пусть имеются шесть работ, которые первоначально выполняются в порядке, указанном в табл. 2.1. В таблице содержатся также длительности выполнения дан­ных работ на пунктах А и В.

Построив диаграмму совмещения работ (рис. 2.1) с учётом возможных простоев, связанных с ожиданием освобождения пункта В, находим, что общее время Т выполнения всех работ в порядке, представленном таблицей, равно 35.


Комментарии закрыты.