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

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

,

вычисляется разность

(на схеме рис. 23.9, б это была бы TL-1—TL) и производится перераспределение работ между двумя каналами, позво­ляющее получить лучшее значение

.

Поскольку трудоемкость подобных операций невелика (они могут выполняться вручную даже при N~ 100 и легко формализуются), имеет смысл их повторять, добиваясь отклоне­ний

не более чем на 5—7 единиц.

По смыслу исходной задачи все τj и Тl есть рацио­нальные числа. В формальном рассмотрении их можно считать целыми (см. предварительные замечания), ме­няющимися дискретно, причем такой же характер изме­нения должен иметь min Т. Это позволяет наметить пути перехода от одного (лучшего, но недостижимого) значе­ния min T к другому (сравнительно худшему) значению, заключающиеся в последовательном анализе разрешимо­сти диофантовых уравнений при тех Тl, которые соответ­ствуют принятому min Т.

Обратимся к теореме: диофантово уравнение

с целочисленными a и b имеет решения (положи­тельные, отрицательные, нулевые), если наибольший об­щий делитель величин аi (i=l,…, п) делит b.

Использо­вать это утверждение применительно к (23.31) можно лишь в негативном смысле (из-за жестких ограничений в выборе yj, не учитываемых условиями теоремы). В ре­зультате станут известны Т1, ..., TL, заведомо непригод­ные для включения в систему (23.30).

Пусть дано простейшее уравнение τ1y1 + τ2y2 = В. Оче­видно, его решения в виде комбинаций нулей и единиц существуют тогда, когда выполнено хотя бы одно из ус­ловий: τ1 = B, τ2=B, τ1 + τ2 = B. В общем случае (N переменных) число подобных условий составляет

однако не все они представляют интерес. Если упо­рядочить значения τj и найти соответственно наименьший и наибольший номера j=p, j=q, для которых

(рис. 23.11), то легко указать сочетания величин τj, подлежащие оценке (не имеет смысла рассматри­вать сочетания более чем из р—1 и менее чем из N—q+1 элементов, так как р самых коротких и N—q+1 самых длинных отрезков в сумме уже превысили В).

Рис. 23.11

Таким об­разом, количество сохраняемых условий уменьшается до

Их формирование связано с затратой значительных усилий, поэтому целесообразно ориентиро­ваться сразу на все возможные значения В (вертикаль­ные пунктирные линии, рис. 23.11), классифицируя полу­чаемые решения по признаку соответствия тем или иным В.

Если уравнение

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

(число гипотез определится наилучшим

достиг­нутым при проведении подготовительных операций). В результате будет составлена оптимальная схема загруз­ки каналов.

2. Алгоритм поиска оптимума. Конкретным выраже­нием сделанных выше замечаний является алгоритм, объединяющий 6 основных этапов поиска minT.

1. Оценивается

и определяется наибольший общий делитель чисел

τ1, τ 2,..., τ N (НОД).

2. Составляется предварительный план посредством сравнения разностей

(см. рис. 23.10).

3. Уточняется предварительный план путем пере­распределения работ между двумя каналами и фик­сируется полученный

4. Определяется (при данном ) нижняя гра­ница значений

и выбираются такие целые числа (В) из диапазона

которые делятся без остатка НОД.

5. Решается диофантово уравнение

yj = 0,l сразу для всех В, найденных на предыдущем шаге, с одновременной классификацией получаемых результатов.

6. Выбирается гипотеза minT = Tср + δ, δ = 0,1... и находятся соответствующие ей «непересекающие­ся» L наборов τj. В зависимости от исхода поиска — конец процесса или переход к новой гипотезе.

Можно ожидать, что наиболее трудоемкими окажут­ся этапы 3, 5 и 6. На одном из них нужно провести порядка

попарных сравнений загрузки каналов, на другом —проверить от

условий существования решений, на третьем — перебрать и клас­сифицировать полученные сочетания τj. Если ограничить­ся требованием найти хотя бы одно из решений исходной задачи планирования, то будет достаточно организовать на этапе 6 проверку ортогональности векторов {yj}, и тогда общее количество типовых вычислительных циклов останется в пределах

Пример. Четырехканальный вычислительный участок (L = 4) загружается семнадцатью работами (N=17), продолжительность выполнения которых (в часах) есть 5,4; 6; 6; 7,2; 7,5; 7,8; 9; 9; 9,6; 10,8; 11,1; 12; 12; 12,3; 13,5; 15; 15. Поскольку безразлично, какими

единицами измеряется эта продолжительность, удобно принять в ка­честве меры десятую долю часа и свести исходные данные в таб­лицу.

Таблица 23.1

Требуется найти оптимальный (в смысле min T) вариант рас­пределения работ на участке. Получаем

Составляем суммы

что дает р = 7. Величину

сравниваем с

и фиксируем T1 = 399 (в первый канал идут первые 6 paбот). Составляем суммы τ7 + τ 8= 180<423, τ 7+ τ8+ τ 9=276<423,...,

из которых первой, превысившей Tср = 423, оказывается

Сравниваем

и принимаем T2=384 (во второй канал идут работы 7—10) и т. д. В результате форми­руем следующий предварительный план загрузки участка:

Производим перераспределение работ между вторым и третьим каналами с целью уменьшить Т3 (и cоответственно увеличить Т2) примерно на 0,5 (Т3—Т2) =45 единиц, что приводит к передаче в тре­тий канал работ 90, 96 (взамен 111, 120) и получению нового (улучшенного) плана

54, 60, 60, 72, 75, 78 90, 108, 11,1, 1.20 90, 96, 120, 123 135, 150, 150,

в котором maxTl = T4, minTl = T1 и T4 — T1 = 36; разность T4 — T1 довольно большая, поэтому имеет смысл повторить операцию уточ­нения плана, передав в четвертый канал работы 60, 72 (взамен 150), и получить

54,60,75,78,150 90,108,111,120 90,96,120,123 60,72,135,150

l=1 T1 = 417 l = 2 T 2 = 429 l = 3 T 3 = 429 l = 4 T 4 = 417

Для значения

определяем