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


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

9.5. Алгоритм решения общей задачи планирования

Предлагаемый алгоритм объединяет целый ряд частных-алгоритмов, каждый из которых либо разрабатывается специально, либо принимается в "готовом виде", если это возможно и целесообразно. Исходными данными для расчетов являются числа N, M, Lk (k = 1,...,M) матрица ||τkn||, директивные сроки начала и окончания отдельных работ, матрица, задающая отношения абсолютных приоритетов на множестве N работ.

I. На первом шаге решения определяется


Трудоемкость подобной операции невелика, процедура поиска Lm стандартна и практически не оказывает влияния на общие затраты средств и времени. Подготовка к следующему шагу предполагает здесь принятие L1 = Lm, выделение соответствующих блоков матрицы ||τkn|| и формирование ограничений, которые будут учтены в первую очередь.

II. Задача оптимального распределения работ на участке I как таковом представляет самостоятельный интерес (см. § 9.4). Она относится к категории сложных комбинаторных задач, для которых еще не найдены общие методы решения, хотя в отдельных случаях нужные результаты получаются сравнительно легко. Перечни работ, попавших в каждый из Lm каналов, составляют основу используемых информационных массивов.

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

IV. Следующий шаг подготавливает переход к использованию схемы "прямого и обратного времени"; участок с номером m изолируется от остальных участков, и его план, сформированный на предыдущих шагах, уплотняется посредством перевода каких-то работ из канала в канал с целью улучшить показатели Тс(l), а затем - левого сдвига работ в каналах. Подобная операция не нарушает никаких ограничений и дает возможность получить то оптимальное расписание на m-м участке, которое требуется и которым должны определяться расписания на остальных участках в силу существующих ограничений; необходимые соответствия достигаются элементарным пересчетом планов.

V. Дальнейшие действия проводятся применительно к двум группам участков (с номерами от 1 до m и от m до M), причем очередность этих действий произвольная. Их начало связано с определением параметров ε1, ε2, позволяющих, в конечном счете, найти m(1), m(2). Выбор m(1), m(2) означает, что коррекции планов будут проведены на участках 1, 2, ..., m(1) (при m(1)≤m-1) и M, M-1, ..., M-m(2)+1 (при m(2)≤M-m). Соответствующие алгоритмы межканального обмена работами (первый этап улучшения) и последовательного ввода в действие резервных каналов (второй этап улучшения) должны исключить возможность нарушения исходных ограничений задачи и в то же время быть достаточно простыми (это особенно важно в условиях, когда преследуется цель лишь улучшить план того или иного участка, а не оптимизировать его полностью). Если получены заданные значения ε1 и ε2, то схема распределения работ в системе фиксируется, вычисляется общий показатель Тс и процесс составления расписания завершается. Неформальный анализ конечного результата позволяет внести мелкие исправления, оценить коэффициент загрузки оборудования при оптимальном плане и т. п.

Всегда существует опасность того, что хотя бы одна из заданных величин ε1, ε2 не будет достигнута. Для устранения этой опасности можно назвать ряд мер:

- контроль текущего состояния улучшаемых планов и своевременное перераспределение значений ε1 и ε1, что особенно важно при неодинаковой эффективности коррекций в первой и второй группах участков;

- назначение m(1)=m-1, m(2)=M-m независимо от оценок m(1)гр и m(2)гр (т. е. ввод коррекций на всех участках, кроме m-го);

- увеличение числа оптимизируемых планов одноканальных l-систем и доведение его в пределе до Lm;

- отыскание новых опорных планов для первого участка и повторение применительно к ним всех рассмотренных операций. Очевидно, основные трудности реализации предложенного общего алгоритма будут связаны с решением задач II и III. Степень универсальности методов, применяемых в этих задачах, определит возможности алгоритма в целом и в первую очередь допустимость его использования при тех или иных классах ограничений; то же самое относится к проблеме снижения затрат средств и времени на получение нужных результатов.

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





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


Диски от INNOBI.RU




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