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


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

10.3. Вычислительная эффективность алгоритмов загрузки линий. Динамика роста затрат

Отдельного изучения требуют вопросы, относящиеся к определению числа перебираемых вариантов решений на разных этапах поиска Т* и Т*с(и). Очевидно, построение П0 делением суммы всех τj (j = 1,...,N) на L примерно равных частей (см. п. 10.1) дает разницу между


порядка


можно ожидать, что разница между


составит здесь величину, приближающуюся к


(тем более, что всегда допустимо строить П0, ориентируясь сразу на max {Тl+ΔTl}). Количество элементарных операций, приводящих к получению П0, невелико и имеет порядок N (упорядочение N чисел с одновременным составлением L сумм, оценка


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

Если теперь обратиться к процедурам решения диофантовых уравнений, завершающим составление расписаний для рассматриваемого изолированного участка, то оценки затрат, приведенные в § 10.1, указывают на резкое возрастание числа перебираемых вариантов плана (сочетаний работ). Когда ставится цель найти все оптимальные решения, это число приближается к 2N, однако оно может быть уменьшено приблизительно на порядок (т. е. примерно до 2N-3) за счет тщательного отбора значений B (см. § 10.1). Существенного улучшения оценок можно ожидать в случае, когда достаточно найти хотя бы одно оптимальное решение, но и здесь количество анализируемых вариантов находится на уровне 2N/2-2M-3.

Значительные различия трудоемкостей начальной и заключительной фаз планирования на участке приводят к необходимости более подробного изучения промежуточных состояний плана с целью уточнить характер соотношений между качеством (точностью) получаемых результатов и производимыми затратами. Пусть на очередном шаге требуется провести обмен предварительно упорядоченными работами между двумя каналами с тем, чтобы уменьшить разность Δ времен их занятости. Число работ в первом канале равно n1, во втором - n2. Значения τυ(1)(υ = 1, ...., n1), τυ2(υ = 1,...,n2) известны, причем t̄υ(2)-t̄υ(1)>Δ и τ1(2)>Δ для всех пар номеров υ(1), υ(2), которым отвечает условие t̄υ(2)>t̄υ(1) (в противном случае правила обмена станут очевидными). Наилучшим результатом здесь, как обычно, явилось бы равенство T1+Δ/2 = T2-Δ/2, но его достижение необязательно, поскольку имеется в виду лишь улучшение показателя max{Т1, Т2} (рис. 10.7,а).

Рассмотрим ряд перестановок работ в канале 2, сводящихся к замене отрезка τ1(2) последовательно отрезками τ2(2), τ3(2), ..., τn2(2) (см. рис; 10.7,6) с соответствующими сдвигами точек t̄υ(2). Всего таких перестановок будет n2-1, и их использование приведет к изменению первоначальных разностей t̄υ(2)-t̄υ(1) и к увеличению возможности уменьшить Δ (например, в схеме, показанной на рис. 10.7,а, оказывается достаточным заменить τ1(1) + τ2(1) на τn2(2)). Формально рассматриваемая операция сводится к вычислению τυ+1(2)υ(2) (υ = 1, ..., n2-1) и сравнению чисел


с τ1(1), τ1(1)2(1), ... Подобные действия можно повторять, связывая их с произвольными τυ(2) (а не только с τ1(2)), выбираемыми на основе предварительного анализа исходных разностей t̄υ(2)-t̄υ(1). Схемы размещения отрезков вблизи некоторого τυ(2) показаны на рис. 10.7,в; первая из них строится по принципу схемы б), вторая использует обратную последовательность работ с сохранением первоначальной нумерации (рис. 10.7,а); возможности реализации этих схем расширяются с увеличением n2. Ожидаемый результат сравнения получаемых таким образом новых t̄υ(2) с имеющимися t̄υ(1) - приближение max{T1, Т2} к 0,5(T1+T2) с погрешностью порядка


Количество сравнений (или исследуемых вариантов расстановки работ) составит 2(n2-1)V, где V - число отрезков τυ(2), относительно которых проводятся все рассмотренные операции (рис. 10.7,в). Даже допуская V∼n2/2, можно утверждать, что уровень затрат характеризуется здесь величиной порядка n22.

Если теперь повторить предложенную процедуру для каких-то τυ(1), то указанная выше погрешность будет оцениваться как


но затраты возрастут примерно до уровня (n21 + n22). По скольку всегда числа n1 и n2 находятся в пределах [N/L] и количество пар каналов, участвующих в обменах работами, есть C2L∼L2/2, характер отношений между точностью результатов улучшений плана участка в целом и произведенными затратами представляется следующим: специально организованный перебор вариантов загрузки линий, сопровождаемый несложными вычислениями, позволяет достичь оптимума с погрешностью порядка


(средняя разность длительностей соседних работ в их исходной последовательности, упорядоченной по признаку возрастания τj, j = 1,...,N

Очевидно,


величина τN сравнима с τ1 по модулю Нτ = НОДτj (т. е. τN1+kNHτ, kN - целочисленный неотрицательный коэффициент), поэтому полученная оценка точности приводится к kNHτ/(N-1). Вырожденный случай kN=0 (все τj одинаковы) мало интересен (для него решения находятся с помощью более простых схем), и в дальнейшем принимается kN >0.

Рассмотренная процедура и связанные с ней оценки сохранятся в принципе неизменными и в случаях, когда в качестве Δ выступает (Т2+ΔТ2) - (T1+ΔT1). Здесь меняется лишь признак упорядочения работ, и вместо χNHΣ, вводится произведение где HΣ = НОД


хотя в основе улучшения показателя max {(Т1 + ΔТ1), (Т2 + ΔТ2)} лежит, как и раньше, межканальный обмен работами. Усложнение вычислений выразится прежде всего в увеличении требуемых объемов памяти ЭВМ для производства тех же переборов.

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

Таблица 10.1
Таблица 10.1

Данные табл. 10.1 позволяют обоснованно выбирать значения ε, от которых зависит выполнение условий сходимости процесса коррекций общесистемного плана на более поздних стадиях его формирования (см. п. 9.3). Для этого нужно обратиться к анализу относительных ошибок



возникающих при умеренных затратах времени и материальных средств.

Имея в виду равенства Тср = NτСр/L, τcp/Hτ = kcp (средняя продолжительность работ, выраженная в единицах Hτ) и


получаем


при kN, kcp, χN, χср не меньших 1.

Коэффициент kср может быть определен как (τ1 + τN)/2Hτ, поэтому kN/kcp≤2, ив дальнейшем имеет смысл

ориентироваться на худший случай kN = 2kcp.

То же справедливо и для χср, следовательно, в качестве общей формулы остается

(10.4)

Соотношение (10.4), характеризующее качество плана, составленного путем перебора порядка N2 вариантов, оказывается полезным тогда, когда N заметно больше L, и схемы, приведенные на рис. 10.7, реальны. Это условие выполняется практически всегда, причем высокая точность приближения к оптимуму обеспечивается в широком диапазоне значений N, L.

Например, δτ,Σ [%] ≤ 1%, если N≥√200L (для L = 2 нужно иметь N≥20, для L = 3, N≥25 и т. д.).

Возвращаясь к е (§ 9.3), заметим, что правило его выбора принимает теперь вид

ε≤1-L/N2

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

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





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


Диски от INNOBI.RU




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