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


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

10.2. Оценка нижней границы множества {Тс}. Вырожденные системы

Выше было замечено, что значения Т*с(и) могут быть получены из анализа задачи о распределении N работ с последействием по каналам производственного участка (см. § 9.4). В принципе эта задача мало отличается от только что рассмотренной в § 10.1, хотя и имеет свои особенности. Первой такой особенностью является требование выдержать определенный порядок выполнения работ в отдельно взятом канале (в задаче 10.1 этого не было, так как любая перестановка одних и тех же τj на l-й линии позволяла сохранять неизменным соответствующее Tl). Вторая особенность связана с необходимостью поиска . новой оценки наилучшего показателя общих затрат времени (вместо Т = Тср). Кроме того, можно ожидать усложнения процедур межканального обмена работами в ходе улучшений имеющихся промежуточных планов.

Рис. 10.5
Рис. 10.5

Пусть дана технологическая линия, на которую приходятся n работ с последействием. Время выполнения υ-й по очереди работы есть


(рис. 10.5), а принятый порядок характеризуется величиной


Всегда желательно разместить эти работы так, чтобы достичь


Это нетрудно сделать, используя утверждение приведенной ниже теоремы (21): для получения оптимальной в смысле


последовательности работ достаточно упорядочить величины


по признаку их убывания.

Доказательство: если рекомендуемая расстановка работ принята, то нетрудно указать номер р такой работы, что


Улучшение подобной ситуации связано с левым сдвигом р-й работы, происходящим за счет обмена местами с v-й работой (v<p) причем признаком допустимости обмена служит неравенство


Действительно,


не изменится от такой перестановки, а сумма


уменьшится только тогда, когда уменьшится слагаемое


что и выражено в неравенстве). Но реализовать все это нельзя, так как по предположению


следовательно, | искомый минимакс достигнут. □

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


показателем его плана в целом становится величина


связанная с одним из номеров l.

В этой ситуации для любого l выполнено


где


Очевидно


поэтому


или (после суммирования по номерам д)

(10.2)

Суммы


могут принимать значения, совпадающие с какими-то из N значений


Обозначив r-е по величине число


как


и имея в ввиду равенство


можно представить (10.2) в виде


Таким образом, правая часть неравенства (10.3) показывает, какой предел улучшений Т̃С(И) (и находящихся среди них Т*с(и)) достижим вообще (в § 10.1 это было просто Тср). В каждом отдельном случае идеальная оценка Т*С(И) будет скорее всего превышена, однако ни один план участка не даст Т*С(И), меньшее, чем


Последовательность действий, приводящих к получению Т*с(и), следующая:

- определяются



- составляется исходный план участка (По) по схеме, описанной в п. 10.1, и для него отыскиваются



- проводится первое улучшение П0 сначала с целью уменьшить


а затем


В результате возникают планы П1 и П2 с лучшими чем у П0 показателями


- планы Π1, П2 улучшаются по той же схеме; из четырех новых планов выбираются два, оставляемые для дальнейшей перестройки; признаками отбора служат те же


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

По-видимому, полностью выполнять всю эту программу нужно тогда, когда тенденции изменения max Т; и max {Тl+ΔТl} совпадают (с улучшением первого показателя улучшается второй и наоборот). В противном

случае достаточно ограничиться только оценками ТС(И). Дополнительные пояснения дает приводимый ниже пример.

Пример: четырехканальный производственный участок загружается работами с последействием (N = 21); их характеристики даны в таблице


Требуется найти оптимальный (в смысле Т*С(и)) план проведения указанных работ.

Решение. Вычисляются значения


и


все НОД равны здесь единице; начальный план П0 составляется по схеме, рассмотренной в § 10.1, т. е. производится суммирование упорядоченных τj1 до получения величины, превышающей Тср = 120 (здесь для этого достаточно взять первые 8 значений τj1). Накопленная сумма сравнивается с Тср, что позволяет разместить на первой линии работы (1)-(7). Повторение этой процедуры применительно к остальным работам приводит к искомому П0:


очевидными оценками являются


Вычисление


сводится к упорядочению работ в каналах по признаку убывания показателей MΣk=2 τjk и определению сумм



(для l = 2) и т. д. (рис. 10.6). Таким образом,


(расхождение оценок существенно).

Для улучшения Π0 имеет смысл сразу ориентироваться на полученные предельные значения Tl+ΔTl. работы (1) - (7) и (14) - (18), подлежащие перераспределению между каналами 1 и 3, упорядочиваются по признаку убывания


(7) (6) (14) (17) (18) (15) (2) (3) (4) (16) (1) (5). Какой бы ни оказалась будущая загрузка каналов 1 и 3, работа (7) обязательно займет первое место в одном из них (например, в том же канале 1), так как у нее наибольшая


Работу (6) передаем в канал 3, после чего реализуется следующая процедура:


Теперь новый план (П1) имеет вид


(улучшение П0 произошло, но незначительное).

Рис. 10.6
Рис. 10.6

-Корректирование П1 связано с перераспределением группы работ, попавших в каналы 1, 4, т. е. (21) (7) (14) (20) (18) (19) (3) (16). Применяя схему, рассмотренную на предыдущем шаге, получаем


Произошло заметное улучшение П1 (вместо


имеем 190); отклонение от идеального показателя


составляет ∼ 2%, и приходится решать вопрос о целесообразности преобразований П2. В приведенном примере можно ограничиться достигнутым результатом, хотя дальнейший поиск мог бы привести к другому варианту загрузки линий:


Вероятно, величина Т*с(и) = 186 либо недостижима, либо приближение к ней требует большого объема вычислений.

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





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


Диски от INNOBI.RU




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