выполнение всего набора заданий было завершено как можно быстрее. Прежде всего построим модель.

Как действует эта система процессоров и заданий? Каково расписание ее работы? Расписанием просто является упорядоченный список заданий L. Система работает следующим образом: первый освободившийся процессор берет из списка следующее задание. Если одновременно освобождаются два или более процессоров, то выполнять очередное задание из списка будет процессор с наименьшим номером. Предполагается, что время, необходимое для загрузки задания в машину, равно нулю. Процессор будет обрабатывать задание до полного завершения, а затем, если список не исчерпан, получит следующее задание.

Предположим, что имеется три процессора и шесть заданий с i=2, 2=5, 3=8, 4=1, 6=5 и 4=1. Рассмотрим расписание L= (/а, /5. Ju Ji, Ja). В начальный момент времени 7=0, Pi начинает обработку 2. Pi начинает J, а Рз начинает Ji. Процессор Рз заканчивает Ji в момент времени Т=2 и начинает обрабатывать задание J, пока Pi и Ра еще работают над своими первоначальными заданиями. При 7=3 Рз опять заканчивает задание J и начинает обрабатывать задание Je, которое завершается в момент Т=4. Тогда он начинает последнее задание /3. Процессоры Pi и Ра заканчивают задания при Т=5, но, так как список L пуст, они останавливаются. Процессор Рз завершает выполнение Js при 7=12. Рассмотренное расписание проиллюстрировано на рис. 3.2.3 временной диаграммой, известной как схема Ганта. Очевидно, что расписание не оптимально. У процессоров Pi и Ра велико время бесполезного простоя. Расписание L* = - (Js, Jz, Je,, Jl, Ji, Je) позволяет завершить все задания за 7* =8, что должно быть оптимумом, так как никакое расписание не может

Т=12

L=(J2,J5,.Jl,J4.J6,J3)

Рис. 3.2.3. Схема Ганта для расписания L.

позволить завершить все задания за меньшее время, чем требуется для выполнения самого длинного задания.

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

Рассмотрим следующий, очень простой эвристический алгоритм. Обозначим через L* расписание выполнения заданий, в котором задание с наибольшим временем обработки стоит первым, затем в порядке убывания времени обработки стоят остальные задания, последним стоит задание с самым маленьким временем обработки. Эвристический алгоритм создает расписание L*, перечисляющее задания в порядке убывания времени их обработки (при совпадении времен порядок выбирается произвольно).

Возвращаясь к предыдущему примеру, видим, что L*=(Js, J, 5. •1, -4. -е)- Расписание L* завершает все задания за время 7*=8, как показано на рис. 3.2.4. Таким образом, в этом примере эвристический алгоритм построил оптимальное расписание.

Рис. 3.2.4. Схема Ганта для оптимального расписания L*.

Конечно, наивно было бы думать, что такой простой эвристический алгоритм является точнььм. Действительно, легко придумать задачу, для которой он не дает оптимального решения. На рис. 3.2.5 показан пример для двух процессоров и ti=3, /2=8, 4=2, 4=2, 4=2. На рис. 3.2.5, а показано расписание L*, а на рис. 3.2.5, б - оптимальное расписание.

Для этого эвристического алгоритма получается очень полезный результат. Как и раньше, обозначим через Т* время завершения всех заданий в задаче с п процессорами при использовании эвристического

алгоритма с расписанием работ, упорядоченных в порядке убывания времени обработки. Пусть То обозначает время завершения этих заданий при использовании оптимального расписания. Можно доказать тогда, что

г* £ 1

То 3 Зп

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

• 3 2

l.*=(Jl,J2,J3,J4,J5) Т*=7

2 2 2 I

Рис. 3.2.5. Неоптимальное эвристическое расписание L* и оптимальное расписанпе

желай затрачивать усилий.на поиск оптимального расписания. Для п=2, Т*/То7/6, и эта максимальная ошибка достигается, как показано на рис. 3.2.5. Для большого числа процессоров максимальная ошибка может достигать 33%.

Точные верхние оценки эвристических алгоритмов на самых плохих случаях получить трудно. Такие оценки известны фактически для очень малого числа эвристических алгоритмов.

Теперь рассмотрим другой тип задач по составлению расписания для многопроцессорных систем. Вместо вопроса о быстрейшем завершении набора заданий фиксированным числом процессоров теперь ставим вопрос о минимальном числе процессоров, необходимых для завершения данного набора заданий за фиксированное время То. Конечно, время То будет не меньше времени выполнения самого трудоемкого задания.

Эта задача составления расписания эквивалентна следующей задаче упаковки. Пусть каждому процессору Pj соответствует ящик Bj размера То- Пусть каждому заданию /1 соответствует предмет размера ti, равного времени выполнения задания t=l, . . ., п. Теперь для решения задачи по составлению расписания нужно построить алгоритм позволяющий разместить все предметы в минимальном количестве ящиков. Конечно, нельзя заполнять ящики ссерх их объема То и предметы нельзя дробить на части.