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

23.6. Планирование работы вычислитедьного участка

1. Постановка задачи и анализ ее особенностей. Свое­образная задача планирования возникает при распреде­лении работ по линиям («каналам»), выполняющим одинаковые функции.

Пусть имеются N работ (например, вычислительных), проводимых на участке, объединяющем L однотипных «каналов». Каждый канал самостоятельно реализует все операции, предусмотренные программой, поэтому любая работа может выполняться в любом канале и время, необходимое для этого, из­вестно. Требуется распреде­лить N работ по L каналам, так, чтобы полное время (Т) занятости участка этими работами было минималь­ным (предполагается N>L). На рис. 23.9, а показан возможный вариант распре­деления работ.

Здесь t0 — об­щее начало отсчета времени, τvl— продолжительность вы­полнения v-й (по порядку) ра­боты в l-м канале (1≤v≤nl), (1≤l≤L), ∆tv-1,l — задерж­ка начала v-й работы относи­тельно окончания (v — 1)-й работы, ∆t01 —задержка на­чала работ в l-м канале относительно момента t0; очевидно,

Время занятости канала с номером l (1≤l≤L) оценивается как

Рис. 23.9

Оно отличается от среднего времени

причем всегда

Следовательно, нельзя ожидать значений Т меньших Tср, и задача заключается в том, чтобы мини­мизировать отклонения Тl (l= 1,.., L) от Tср (наилучшим из всех было бы решение, дающее Т = Тср). В этих условиях увеличение Тср является нежелательным, но оно может произойти из-за неудачного выбора ∆tv-1,l. Если ∆tv-1,l фиксированы заранее (например, учтены потери времени на подготовку очередных работ или запланированы какие-то вспомогательные операции), то их удобно включить в соответствующие τvl, изъяв фор­мально из рассмотрения. Если же ∆tv-1,l выбираются произвольно, их лучше считать равными нулю с самого начала и не вводить в оценку Tср. Таким образом, в лю­бом случае достаточно исследовать схему рис. 23.9, б с целью отыскания величины

Здесь оказывается удобным использовать понятие диофантова уравнения. Уравнение Р(х1, .., хп) = 0, содержащее в левой части функцию полиномиально­го вида с рациональными коэффициентами, относится к классу диофантовых, если необходимо найти его решения в целых (часто положительных) числах. Степень такого уравнения определяется степенью полинома Р(х1, ..., хп). В дальнейшем интерес представят только линейные диофантовы уравнения вида

в которых b и аi являются рациональными дробями. Приведя эти дроби к общему знаменателю, легко перейти к уравнениям с целочисленными b и аi.

Возможности практического использования решений линейного диофантова уравнения связаны с задачами об отыскании способов разбиения положительного числа A на слагаемые с известными свойствами или составле­ния отрезков заданной длины из меньших отрезков (в последнем случае требуется выбрать из имеющихся N отрезков с длинами τj (j=1, N) такие, которые точно со­ставят величину В. Формально это приводит к анализу уравнения

при условии, что переменные у, могут принимать значения 0 или 1). Диофантовы урав­нения (и, тем более, системы таких уравнений) разреши­мы далеко не всегда, но для линейного случая условия существования решений сформулированы в достаточно общем виде.

Предположим, что из каких-либо соображений вы­браны Тl>0

(l=1,…, L). Можно ли указать вариант загруз­ки участка N работами, отвечающий принятым Tl? Ответ на этот вопрос будет утвердительным, если существуют неотрицательные решения системы диофантовых урав­нений:

(23.30)

где τ1, τ2, ..., τN — известные длительности выполнения работ (в произвольной нумерации). Каждое соотношение вида

выражает требование точно составить из комбинаций «отрезков» τj величину Ti (после чего вводятся обозначения τvl, см. рис. 23.9). Ограничения на знак переменных xjl (j=1,…, N, l=1,…, L) вместе с условиями

Исключают возможность использования одного и того же т. для со­ставления разных Тl.

Из последних N уравнений системы (23.30) следуют равенства

Подстановка этих xj1 (j=1,…, N) в первую строку (23.30) дает

(23.31)

(в строки с номерами 2, 3,..., L переменные xj1 не входят). Суммы

могут рассматриваться как новые переменные yj(j=1,…, N), принимаю­щие значения 0 или 1, и первым шагом исследования системы (23.30) становится поиск решения диофантова уравнения

Если такое решение существует и найдено, оно представляет собой набор уі в виде нулей и единиц, количества которых определяются ве­личинами L, Tcp, T1, τj (j=1,…, N) и составляют соответ­ственно и

N — (≥ L — 1). Поскольку для общих оценок безразлично, какие именно yj обратятся в ноль, можно считать, что это будут yN,

уN-1, . От­сюда

и даль­нейшие операции связаны с системой

(23.32)

которая по своей структуре не отличается от (23.30) и от­носится к задаче распределения N— работ по остав­шимся L—1 каналам, переходящей в задачу с L—2 ка­налами и т. д. Это вполне соответствует представлениям о возможности постепенного формирования схемы загруз­ки участка.

Основные трудности заключаются здесь в следующем: неясны принципы выбора величин Т1, Т2, ..., TL; процеду­ры решения диофантовых уравнений довольно громоздки, поэтому искать эти решения имеет смысл тогда, когда есть уверенность в их существовании.

Первая трудность может быть частично устранена, если иметь в виду, что наилучшей (в смысле min T) ком­бинацией значений Т1, ..., TL является Tl = Тср (l =1,…, L), и ее нужно исследовать в первую очередь. Кроме того, всегда можно указать значения Tl (l =1,…, L), при которых система (23.30) разрешима, но которые почти наверное не доставляют минимума Т. Для этого достаточно упоря­дочить τj по признаку неубывания, определить наименьший номер j = p, отвечающий условию

(рис. 23.10), сравнить между собой разности

выбрать в качестве Т1 либо величину

(если первая разность меньше второй), либо

(если вторая разность меньше первой), исключив таким обра­зом из дальнейшего рассмотрения τj, составившие T1, и повторить всю эту несложную процедуру применитель­но к оставшимся τj, что даст сначала Т2, затем Т3 и т. д.

Рис. 23.10

Среди указанных T1, T2,... находится величина

,

так что

Если расхождение между Тср и найденным