Планирование задач для одного ресурса с использованием Prolog

Я искал здесь, как мог, и, хотя я нашел несколько соответствующих вопросов, я не думаю, что они охватили данный вопрос:

Предположим, что есть один ресурс и известный список запросов для планирования задачи. Каждый запрос включает start_after, start_by, ожидаемую_длительность и действие.

Цель состоит в том, чтобы запланировать задачи для выполнения как можно скорее, сохраняя расписание каждой задачи между start_after и start_by.

Я написал простой пример на Прологе, который, как мне казалось, должен работать, но, к сожалению, во время выполнения я получаю ошибки: «>=/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.

Изменить: по-видимому, моя цель расписания работает, если я предоставляю действительные пары «Запрос, время» ... но я застрял, пытаясь заставить Пролог найти допустимые значения для T1..3 при задании R1..3?


scheduling prolog resource-scheduling clpfd
person Reed Debaets    schedule 27.01.2010    source источник
comment
Отдельный вопрос, который я задал, имеет последний экземпляр этой проблемы: рекурсия"> stackoverflow.com/questions/2156581/   -  person Reed Debaets    schedule 29.01.2010
comment
Вы найдете решения для подобных проблем, помеченных clpfd. Например, в SICStus Prolog проверьте serialized/2, доступный в library(clpfd). Это специальный предикат, описывающий такого рода ограничения.   -  person mat    schedule 27.10.2015

Ответы (1)


arrow_upward
1
arrow_downward

Есть пара проблем с оригинальной реализацией. Он может нормально работать (с небольшими изменениями) в системе программирования логики с ограничениями, но не в чистом Прологе. В Прологе порядок целей имеет решающее значение. Я изменил код, чтобы он работал:

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 до того, как эти переменные будут проверены конфликтами/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

Есть гораздо более эффективные реализации этой проблемы.

person Lindsey Spratt    schedule 27.03.2010