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

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

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

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

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

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

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

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

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

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

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

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

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