Новости    Библиотека    Байки    Ссылки    О сайте


предыдущая главасодержаниеследующая глава

10.5. Улучшение показателей формируемых расписаний. Межканальный обмен работами

Предлагаемые здесь алгоритмы основаны на структурных преобразованиях схем предварительного распределения работ, дающих определенную информацию о достигнутых и ожидаемых состояниях формируемого плана. Последнее обстоятельство способствует упрощению процедур перестройки расписаний, хотя не исключает всех трудностей, характерных для задач упорядочения работ.

Предположим, что все подготовительные операции, связанные с построением Lm планов одноканальных систем, переходом к схеме "прямого и обратного времени", определением ε, χ/ε, m и т. д., завершены. Ситуация, возникающая на произвольном k-м участке, характеризуется в этих условиях следующим.

Моменты начала работ в каждом канале (t0lk) не совпадают, вообще говоря, друг с другом (см. рис. 9.2), поскольку они зависят от параметров оптимальных (или квазиоптимальных) планов l-систем, формировавшихся самостоятельно.

Левый сдвиг работ в пределах любого канала невозможен (в противном случае следовало бы возвратиться к анализу планов соответствующих l-систем).

Каждой работе с номером υlk приписаны три показателя: τυlk (продолжительность выполнения), Δtυ-1,lk (время простоя канала перед началом этой работы), θυlk (допустимый, но пока невозможный сдвиг влево), причем Δtυ-1,lk×θυlk = 0.

Имеется резерв из Lk-Lm каналов, образовавшийся вследствие искусственного уменьшения Lk на начальных стадиях исследований (см. гл. 9).

Все Lm занятых каналов различаются по степени их влияния на общий результат Тс, и это должно учитываться при перестройках расписаний. В формальных оценках допустимо считать наиболее важным в указанном смысле первый канал, вторым по важности - второй канал и т. д. (для этого достаточно изменить нумерацию), причем в ходе коррекций такое согласование номеров приходится проводить неоднократно.

Таким образом, улучшение плана k-ro участка, выражающееся в уменьшении каких-то θυlk>0 и соответствующих изменениях общего показателя Тс, может быть достигнуто, во-первых, за счет межканального обмена работами и, во-вторых, за счет ввода в действие резервных линий. В первую очередь необходимо исследовать процесс обмена.

Обратимся к задаче: дан план участка в виде Гантт-карты или в виде блочной матрицы, элементами которой являются наборы чисел t0l, Δtυ-1,k, τυl, θυl(индекс "к" можно пока опустить). Правые сдвиги работ безусловно запрещены (этим устраняется опасность нарушения сроков TυΠ и других ограничений, см. § 10.4, 8.5). Требуется получить условия переноса произвольно взятой работы из одного канала в другой и построить на этой основе алгоритм обмена, приводящий к наибольшему эффекту (в смысле уменьшения Тс) при фиксированном количестве переборов.

Рис. 10.9
Рис. 10.9

Идею поиска вариантов обмена удобно рассмотреть сначала на частном примере. Пусть имеется схема загрузки участка с Lm = 3 и конкретными θυl(υ = 1, ..., nl; l = 1,.., 3) (рис. 10.9). Нетрудно найти границы возможных левых сдвигов работ с θυl>0, и первой такой границей будет I (она принадлежит работе "22" с θ22 = 1). Имея в виду отказ от правых сдвигов, приходим к выводу: работа "22" могла бы переходить из канала в канал, оставаясь обязательно в пределах полосы шириной t̄22-t2222, однако это невозможно из-за отсутствия в указанных пределах хотя бы одного промежутка Δtυ-1,l≥τ22. Та же ситуация повторяется для работы "33", но работа "43" оказывается в лучшем положении, так как в связанной с ней полосе π43 есть Δt2243 (рис. 10.9). Передав "43" в канал l = 2 и сместив влево работы "53"-"83", получаем новый план, после чего следует пересчет Тс.

Формализация подобной процедуры связана с анализом схемы, представленной на рис. 10.10. Некоторая работа, принадлежащая каналу λ(1≤λ≤Lm), имеющая порядковый номер со и продолжительность τωλ переводится в канал l(1≤l≤Lm, l≠λ). Левая граница полосы перемещений, отсчитанная от момента t0l вычисляется по формуле


правая граница есть J2l = J1l + τωλ + θωλ. Вводя в рассмотрение единичную ступенчатую функцию 1 (t) = 0 при t<0 и 1(t) = 1 при t≥0, а также функцию Fl(t) (принимающую в произвольный момент времени t≥t0l значение 0, если в этот момент канал l простаивает, и значение v, если в нем выполняется работа с номером υ≥1), приходим к группе условий, лежащих в основе алгоритма межканального обмена.

Теорема (23): для того чтобы оказался возможным перевод работы "ωλ" в канал l, необходимо и достаточно найти такое значение tωλ из диапазона; J1l≤tωλ≤J1lωλ при котором произведение Fl(t)1[-t2+(2tωλωλ)t-tωλ(tωλωλ)] тождественно равно нулю.

Доказательство: поскольку для всех t<tωλ и t > tωλωλ значение 1 есть нуль (при этих t аргумент 1 отрицателен), имеет смысл рассмотреть случай tωλ≤t≤tωλωλ. Здесь 1 = 1, и выполнение условий теоремы связывается с равенством Fl(t) = 0. Пусть при не котором допустимом tωλ перевод работы ωλ оказался возможным, следовательно, в течение времени τωλ, начиная с момента tωλ канал I оставался бы незанятым. Но это означает Fl(t) = 0, tωλ≤t≤tωλωλ (необходимость). Наоборот, если Fl(t) = 0 при tωλ≤t≤tωλωλ и J1l≤tωλ≤J1lωλ то существует такое время простоя l-го канала в пределах полосы перемещений работы "ωλ", что его можно использовать для выполнения этой работы (достаточность). □

Машинная реализация рассмотренных требований сводится к анализу систем неравенств вида

(10.9)

где r и ρ - наименьшие порядковые номера сумм τ1l, τ1l+Δtl1, τ1l+Δt1l2l, τ1l+Δt1l2l+Δt2l,... превышающих соответственно J1l, J2l. Соблюдение хотя бы одной группы неравенств (10.9) равносильно отысканию нужного промежутка Δtυ-1,k≥τωλ в который попадает работа ωλ.

Если операция однократного обмена между каналами λ и l проведена, фиксируются новые значения θωλ, и т. п., после чего дается оценка изменений общего показателя Tc. Число исследуемых вариантов, определяющее уровень затрат на первом этапе улучшения общесистемного плана, имеет порядок NLm≤NLM (на каждом из m участков проверяются N работ с целью найти какой-либо из L каналов, допускающий разовый обмен). Реальные затраты будут скорее всего нижеуказанных здесь, так как рассматриваемым операциям предшествует уплотнение расписаний и, кроме того, присутствие различных ограничений затрудняет подбор комбинаций перемещаемых работ.

предыдущая главасодержаниеследующая глава





Пользовательский поиск


Диски от INNOBI.RU




© Злыгостев Алексей Сергеевич, подборка материалов, оцифровка, статьи, оформление, разработка ПО 2001-2017
При копировании материалов проекта обязательно ставить активную ссылку на страницу источник:
http://informaticslib.ru/ "InformaticsLib.ru: Информатика"