Планирование задач для одного ресурса с использованием Prolog
-
23-09-2019 - |
Вопрос
Я просмотрел здесь все, что мог, и хотя я нашел несколько актуальных вопросов, я не думаю, что они касались рассматриваемого вопроса:
Предположим, что имеется один ресурс и известный список запросов для планирования задачи.Каждый запрос включает start_after, start_by, expected_duration и действие.
Цель состоит в том, чтобы запланировать задачи для выполнения как можно скорее, сохраняя при этом расписание каждой задачи между start_after и start_by.
Я закодировал простой пример Prolog, который, как я "думал", должен работать, но, к сожалению, я получал ошибки во время выполнения:">=/2:Аргументы недостаточно конкретизированы".
Будем очень признательны за любую помощь или совет
startAfter(1,0).
startAfter(2,0).
startAfter(3,0).
startBy(1,100).
startBy(2,500).
startBy(3,300).
duration(1,199).
duration(2,199).
duration(3,199).
action(1,'noop1').
action(2,'noop2').
action(3,'noop3').
can_run(R,T) :- startAfter(R,TA),startBy(R,TB),T>=TA,T=<TB.
conflicts(T,R1,T1) :- duration(R1,D1),T=<D1+T1,T>T1.
schedule(R1,T1,R2,T2,R3,T3) :-
can_run(R1,T1),\+conflicts(T1,R2,T2),\+conflicts(T1,R3,T3),
can_run(R2,T2),\+conflicts(T2,R1,T1),\+conflicts(T2,R3,T3),
can_run(R3,T3),\+conflicts(T3,R1,T1),\+conflicts(T3,R2,T2).
% when traced I *should* see T1=0, T2=400, T3=200
Редактировать:цель конфликта была не совсем правильной:требовалось дополнительное предложение T>T1.
Редактировать:Очевидно, что моя цель расписания работает, если я предоставляю действительный запрос, временные пары...но я застрял, пытаясь заставить Prolog найти допустимые значения для T1 .. 3 при задании R1..3?
Решение
Есть пара проблем с первоначальной реализацией.Это может нормально работать (с незначительными изменениями) в системе программирования с логикой ограничений, но не в обычном Prolog.В Prolog порядок целей имеет решающее значение.Я изменил код так, чтобы он работал:
can_run(R, T) :-
startAfter(R,TA),
startBy(R,TB),
between(TA,TB,T).
conflicts(T,R1,T1) :-
duration(R1,D1),
T=<D1+T1,
T>=T1.
schedule(R1,T1,R2,T2,R3,T3) :-
can_run(R1,T1),
can_run(R2,T2),
R1 \= R2,
\+ conflicts(T1,R2,T2),
can_run(R3,T3),
R3 \= R1,
R3 \= R2,
\+ conflicts(T1,R3,T3),
\+ conflicts(T2,R1,T1),
\+ conflicts(T2,R3,T3),
\+ conflicts(T3,R1,T1),
\+ conflicts(T3,R2,T2).
between(Low, High, Between) :-
Between is Low
;
Low < High,
Next is Low + 1,
between(Next, High, Between).
Я добавил использование предиката between /3 (определенный встроенный компонент в некоторых реализациях Prolog).Он генерирует целые числа между двумя заданными конечными точками.
Я добавил проверки неравенства в schedule / 6, чтобы заставить R1, R2 и R3 принимать разные значения.
Наконец, я изменил порядок целей в schedule / 6, чтобы гарантировать, что предикат can_run / 2 был оценен для пары переменных Ri / Ti до того, как эти переменные были проверены conflicts /3.
Расписание запросов (R1,T1, R2,T2, R3, T3) выполняется в течение нескольких минут и, наконец, выдает:
?-schedule(R1,T1,R2,T2,R3,T3)
R1 = 1
T1 = 0
R2 = 2
T2 = 400
R3 = 3
T3 = 200
Существуют гораздо более эффективные реализации для решения этой проблемы.