Алгоритмы составления расписания.

Предположим, что имеется множество nодинаковых процессоров, обозначенных, и m независимых заданий, которые нужно выполнить. Процессоры могут работать одновременно, и любое задание можно выполнять на любом процессоре. Если задание загружено в процессор, оно остается там до конца обработки. Время обработки заданияизвестно и равноОрганизовать обработку заданий таким образом, чтобы выполнение всего набора заданий было завершено как можно быстрее.

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

Пример. Пусть имеется три процессора и шесть заданий , время выполнения каждого из которых равно:

Рассмотрим расписание В начальный момент времениT=0, процессорначинает обработку задания, процессор- задания, а процессор- задания. Процессорзаканчивает выполнение заданияв момент времении начинает обрабатывать задание, пока процессорыивсе еще работают над своими первоначальными заданиями. ПриT=3процессоропять заканчивает заданиеи начинает обрабатывать задание, которое завершается в моментT=4. Тогда он начинает выполнять последнее задание. Процессорыизаканчивают задания приT=5, но, так как списокLпуст, они останавливаются. Процессорзавершает выполнение заданияприT=12. Рассмотренное расписание проиллюстрировано на рис.1. временной диаграммой, известной каксхема Ганта. Очевидно, что расписание не оптимально. Можно «подобрать», например, расписание, которое позволяет завершить все задания заT* = 8 единиц времени (рис.2.).

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

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