Парадигма развития науки (стр. 56 )

23.5. Определение оптимальной последовательности работ

1. Постановка и формализация задачи. Организация вычислительных процессов ставит проблему планирова­ния различных по своему характеру работ. Задачи оп­тимального планирования решаются в условиях, когда заранее однозначно заданы продолжительности выполне­ния операций (τsk), что накладывает отпечаток на мето­дологию поиска оптимума. Возникающие здесь трудно­сти связаны, в основном, с необходимостью анализа мно­гочисленных вариантов плана.

Пусть дана система, объединяющая М одноканальных участков, каждый из которых реализует вполне оп­ределенный этап вычислительного процесса. Имеются N работ, выполняемых системой в некоторой последова­тельности, причем известны нормы времени τvk (v — но­мер работы по порядку следования, k — номер участка или этапа). Введены ограничения:

а) очередность работ сохраняется на всех участках неизменной;

б) момент начала k-го этапа v-й работы не может на­ступить раньше момента окончания (k—1)-го этапа той же работы;

в) для отдельных работ установлены плановые сроки окончания, которые необходимо выдержать;

г) возможна частичная упорядоченность работ (неко­торые из них не могут проводиться раньше каких-то дру­гих) .

В этих условиях требуется определить последователь­ность проведения работ, наилучшую в смысле минимума общего времени (Т), затрачиваемого на их выполнение (рис. 23.7).

Pис. 23.7

Введем единый отсчет времени (t = 0). Пусть t0k — момент возможного начала k-го этапа, a ∆tv—1,k —за­держка начала k- го этапа v-й работы относительно мо­мента окончания того же этапа (v— 1)-й работы. Оче­видно, ∆tv—1,k ≥0 и условие б) может быть выражено как

(23.23)

или

где Θvk — вспомогательные неотрицательные переменные (Θvk ≥0), имеющие размерность времени; ∆t0k—1 — задержка начала (k—1)-го этапа (своего рода начальные условия). Последнее равенство показывает, что v-я (по порядку) работа будет выполнена за время

Объединив номера v, для которых существуют плано­вые сроки, в множество Sп, получим формальное выра­жение условия в):

или

(23.24)

где φvп—вспомогательные неотрицательные переменные. Условия а) и г) связывают порядковые номера, которые получат работы, проводимые в оптимальной последова­тельности, поэтому формализация этих условий априори ничего не дает.

Система уравнений (23.23) может быть представлена в виде

или (после попарного вычитания строк)

(23.25)

Заметим, что всегда можно положить ∆t0k(k=1,…,M) равными нулю (или, что то же, включить их условно в τ1k). Кроме того, работы подготовительные и регламентные могут быть учтены как полезные своими τ в общих соотношениях типа (23.23) — (23.25).

Обозначим τv,k-1 — τ v-1,k через wvk,

— через T0v,

— через T0 и обратимся к оптимизационной задаче:

найти Θvk, ∆tv—1,k, φvп, доставляющие

при ограничениях:

(23.26)

Зафиксировав произвольным образом все τvk, рассмот­рим эту задачу как обычную задачу линейного програм­мирования. Из выражения Т следует, что всякое допу­стимое базисное решение системы (23.26), содержащее в числе свободных переменные ∆tv—1,1 (v = 2,…,N), ΘNk

(k =2,…,M), будет и оптимальным для сформулированной задачи. Однако подобные решения могут встретиться да­леко не всегда, поэтому необходимы дополнительные ис­следования (23.26).

Докажем следующее утверждение: оптимальным яв­ляется такое допустимое базисное решение (23.26), кото­рое содержит в числе свободных все ∆tv—1,1 и одновремен­но удовлетворяет требованиям Θvk∆tv—1,k =0, v = 2,…,N; k = 2,…,M (переменная Θvk может войти в базис только тогда, когда ∆tv—1,k является свободной, и наоборот). Цель доказательства — убедиться в том, что небазисные (свободные) переменные рассматриваемого решения име­ют неотрицательные коэффициенты в выражении Т (при­знак оптимальности).

Пусть BN-p — множество номеров k таких, что ΘN-p,k входит в базис при k BN-p (соответственно, ∆tN—p-1,k является свободной при k BN-p, 0≤p≤N —2); пусть далее kN — наибольший из номеров kBN (p=0). Учитывая это, нетрудно указать те ΘNk, которые заведомо относятся к числу свободных пере­менных (они собраны под знаком третьей суммы в равенстве

причем

если kN=M).

Независимо от того, какие еще пе­ременные Θvk, ∆tv—1,k, φvп станут свободными и какие базисными, можно утверждать, что

В свою очередь

где kN-1 - наибольший из номеров k≤kN, k BN-1

Здесь опять под знаком третьей суммы собраны заведомо свободные ΘN-1,k и

Продолжив процесс отделения величин ΘN-p,k, для которых, kBN-p (0≤р≤ N — 2), приходим к формуле

(23.27)

где

при kN-p+1 > kN-p+1. Очевидно, в правой части (23.27) присутствуют только свободные переменные ΘN-p,k, ∆tα—1,1, (относительно это за­мечание справедливо, так как

kN-pBN-p). Они войдут в выражение Т (после подстановки 23.27) с неотрицатель­ными коэффициентами:

(23.28)

Таким образом, определена структура оптимальных решений. Чтобы найти такие решения в каждом кон­кретном случае, достаточно использовать простое пра­вило: если в очередной строке (23.26) сумма

∆tv—1,k-1- Θv-1,k+wvk неотрицательна, в базис вводится пере­менная ∆tv—1,k, a Θvk считается свободной (равной нулю); если же ∆tv—1,k-1-Θv-1,k+wvk <0, базисной переменной становится Θvk, a ∆tv—1,k обращается в нуль; сформи­рованное решение должно удовлетворять требова­ниям φvп≥0 (v Sп), иначе оно окажется недопус­тимым.

В этих условиях можно говорить об оптимальной ор­ганизации работ даже при фиксированном порядке их производства (не нарушающем ограничений в), г). Так, этапы работы, выполняемой первой, должны следовать друг за другом без задержек (Θ1k =0, k = 2,…, М); этапы любой промежуточной работы идут, вообще говоря, со сдвигами по времени один относительно другого (исключение составляет случай, когда все