Нашей эвристической функцией будет оптимистическая оценка времени окончания частичного плана с учетом всех ждущих задач. Оптимистическая оценка будет вычисляться в предположении, что два из ограничений, налагаемых на действительно корректный план, ослаблены:

(1) не учитываются отношения предшествования;

(2) делается (не реальное) допущение, что возможно распределенное выполнение задачи одновременно на нескольких процессорах, причем сумма времен выполнения задачи на процессорах равна исходному времени выполнения этой задачи на одном процессоре.

Пусть времена выполнения ждущих задач равны Т1, Т2, ..., а времена окончания задач, выполняемых на процессорах - К1, К2, ... . Тогда оптимистическая оценка времени ОбщКон окончания всех активных к настоящему моменту, а также всех ждущих задач имеет вид:

где m– число процессоров. Пусть время окончания текущего частичного плана равно

Кон = maх(Kj).

j

Тогда эвристическая оценка Н (дополнительное время для включения в частичный план ждущих задач) определяется следующим выражением:

if ОбщКон>Кон then Н = ОбщКон-Кон else H=0

Программа, содержащая определения отношений, связанных с пространством состояний нашей задачи планирования, приведена полностью на рис. 12.9. Эта программа включает в себя также спецификацию конкретной задачи планирования, показанной на рис. 12.3. Одно из оптимальных решений, полученных в процессе поиска с предпочтением в определенном таким образом пространстве состояний, показано на рис. 12.8.

Проект

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

/* Отношения для задачи планирования.

Вершины пространства состояний - частичные планы,

записываемые как

[ Задача1/Т1, Задача2/Т2, ...]*

[ Задача1/К1, Задача2/К2, ...]* ВремяОкончания

В первом списке указываются ждущие задачи и продолжительности их выполнения; во втором - текущие решаемые задачи и их времена окончания, упорядоченные так, чтобы выполнялись неравенства K1<=K2, K2<=K3, ... . Время окончания плана - самое последнее по времени время окончания задачи.

*/

после( Задачи1*[ _ /К | Акт1]*Кон1, Задачи2*Акт2*Кон2,Ст):-

удалить( Задача/Т, Задачи1, Задачи2),

% Взять ждущую задачу

not( принадлежит( Здч1/_, Задачи2),

раньше( ЗДЧ, Задача) ),

% Проверить предшествование

not( принадлежит( Здч1/К1, Акт1), К1<К2,

раньше( К1, Задача) ), % Активные задачи

Время is К + Т,

% Время окончания работающей задачи

встав( ЗадачаВремя, Акт1, Акт2, Кон1, Кон2),

Ст is Кон2 - Кон1.

после( Задачи*[ _ /К | Акт1]*Кон, Задачи2*Акт2*Кон, 0):-

вставпростой( К, Акт1, Акт2).

% Оставить процессор бездействующим

раньше( Задача1, Задача2) :-

% В соответствии с предшествованием

предш( Задача1, Задача2).

% Задача1 раньше, чем Задача2

раньше( Здч1, Здч2) :-

предш( Здч, Здч2),