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


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

10.6. Способы использования резервных каналов. Восстановление структуры системы

Другая важная задача, требующая перевода отдельных работ из канала в канал, возникает на этапе поочередного подключения резервных технологических линий, оставшихся временно свободными после искусственного уменьшения Lk(k = 1,...,M, k≠m) с целью упростить построение предварительного системного плана (см. гл. 9). Все замечания, сделанные в начале § 10.5, остаются в силе, однако необходимо добавить следующее.

- Принципы выбора работ, переносимых в резервные каналы, должны основываться на анализе внутренних свойств решений, полученных в § 10.1 -10.4 и характеризуемых связями между τυkl, Δtυ-1,k, θυkl.

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

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

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

Обратимся теперь непосредственно к анализу формальных соотношений. Несложные преобразования равенств (10.5) позволяют получить

(10.10)

Сумма


представима в виде


предполагая θυkl>0 (только работы со строго положительными θυlk дают эффект улучшения расписаний при переходе в свободный канал), можно считать Δtυ-1,kl = 0 (так как всегда θυlkΔtυ-1,kl = 0). Кроме того,


Таким образом, из (10.10) следует


или

(10.11)

Формула (10.11) показывает, что разность θυlk - θυ-1,lk знакопеременна, но всегда меньше τυ-1,kl Это свойство используется при формулировании правил заполнения очередного свободного канала работами из других каналов.

Теорема (24): последовательность разностей


является строго возрастающей.

Доказательство: из выражения Δυlk следует Δυlk-υ-1,lkυ-1,klυlkυ-1,lk но θυlkυ-1,lkυ-1,lk>Δtυ-2,lk поэтому Δυlkυ-1,lk Любая из величин Δt неотрицательна, и последнее равенство переходит в Δυlkυ-1,lk>0 или Δυlkυ-1,lk(υ = 2, 3, ...). □

По своему смыслу Δυlk есть интервал времени от начального момента t0lk до момента tυlkυlk (рис. 10.11). Если l - номер разгружаемого канала, то теорема (24) утверждает возможность указать отрезок "υlk", который после переноса в свободный канал и левого сдвига на соответствующую величину θυlk займет ближайшее к t0kl положение, обеспечив наименьшие потери времени, однако решение о его изъятии из l-го канала еще не устраняет неопределенности положения других отрезков работ, расположенных справа.

Рис. 10.11
Рис. 10.11

Будем теперь считать, что (υ+1)-я работа рассматривается в условиях, когда стоящая перед ней υ-я работа перешла в резервный канал, заняв там некоторое положение и освободив место в основном l-м канале (для наглядности здесь удобно сохранить индексы m, рис. 10.12). Возникает принципиальная возможность левого смещения (о + 1)-й работы либо в пределах l-го, либо в пределах нового, (Lm+1)-го канала. Имеет смысл осуществить это смещение там, где находится больший из промежутков δtl = tυ+1,lk-t'l, δtLm+1 = tυ+1,lk-t̄υlk(целесообразность такого выбора определяется теоремой (24)), после чего вся ситуация повторится для работы υ + 2, и т. д. В результате будут найдены работы, которые должны выполняться в подключаемом канале.

Очевидно, рассмотренная схема загрузки свободных линий не является единственной. Ее преимущество состоит в том, что сокращаются потери времени и, следовательно, повышается эффективность использования резервов. В каких-то случаях подобное требование становится излишним, и правила выбора переносимых работ модифицируются (например, при перестройке расписания последнего участка может оказаться полезной схема, дающая наибольшее число нулевых θυlk подряд, начиная с θnllk). Независимо от этого объем вычислений

остается небольшим.

Рис.10.12
Рис.10.12

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





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


Диски от INNOBI.RU




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