Применение поиска с предпочтением к планированию выполнения задач
12. 3. Применение поиска с предпочтением к планированию выполнения задач
Рассмотрим следующую задачу планирования. Дана совокупность задач t1, t2, ..., имеющих времена выполнения соответственно T1, Т2, ... . Все эти задачи нужно решить на m идентичных процессорах. Каждая задача может быть решена на любом процессоре, но в каждый данный момент каждый процессор решает только одну из задач. Между задачами существует отношение предшествования, определяющее, какие задачи (если таковые есть) должны быть завершены, прежде чем данная задача может быть запущена. Необходимо распределить задачи между процессорами без нарушения отношения предшествования, причем таким образом, чтобы вся совокупность задач была решена за минимальное время. Время, когда последняя задача в соответствии с выработанным планом завершает свое решение, называется временем окончания плана. Мы хотим минимизировать время окончания по всем возможным планам.
На Рисунок 12.8 показан пример задачи планирования, а также приведено два корректных плана, один из которых оптимален. Из примера видно, что оптимальный план обладает одним интересным свойством, а именно в нем может предусматриваться "время простоя" процессоров. В оптимальном плане Рисунок 12.8 процессор 1, выполнив задачу t, ждет в течение двух квантов времени, несмотря на то, что он мог бы начать выполнение задачи t.
Один из способов построить план можно грубо сформулировать так. Начинаем с пустого плана (с незаполненными временными промежутками для каждого процессора) и постепенно включаем в него задачи
