Программирование на языке ПРОЛОГ для искуственного интеллекта




Применение поиска с предпочтением к планированию выполнения задач


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

На рис. 12.8 показан пример задачи планирования, а также приведено два корректных плана, один из которых оптимален. Из примера видно, что оптимальный план обладает одним интересным свойством, а именно в нем может предусматриваться "время простоя" процессоров. В оптимальном плане рис. 12.8 процессор  1,  выполнив задачу  t,   ждет в течение двух квантов времени, несмотря на то, что он мог бы начать выполнение задачи  t.

Один из способов построить план можно грубо сформулировать так. Начинаем с пустого плана (с незаполненными временными промежутками для каждого процессора) и постепенно включаем в него задачи

fig12_8.gif (4006 bytes)

Рис. 12. 8.  Планирование прохождения задач в многопроцессорной системе для 7 задач и 3 процессоров. Вверху показано предшествование задач и величины продолжительности их решения. Например, задача t5  требует 20 квантов времени, причем ее выполнение может начаться только после того, как будет завершено решение трех других задач   t1,  t2  и  t3.   Показано два корректных плана: оптимальный план с временем окончания  24  и субоптимальный - с временем окончания  33.  В данной задаче любой оптимальный план должен содержать время простоя.



Содержание  Назад  Вперед