какой алгоритм для программы планирования

Question

У меня есть проблема планирования задач. Каждое задание имеет предполагаемое время начала T (оно должно начинаться с [T-10, T + 10]), занимает L минут для завершения и использует ряд ресурсов [R1, R2, ...]. Когда ресурс используется, никакая другая задача не может его использовать. Учитывая, что только время начала является гибким, моя цель состоит в том, чтобы запланировать задачи так, чтобы они могли получить доступ к любому ресурсу, в котором они нуждаются, или указать все конфликты, которые необходимо разрешить.

Какой алгоритм я могу использовать для этой цели? Спасибо.

Answer 1

Поскольку вы пометили это как prolog, я рекомендую реализовать его в программировании логики ограничений (CLP) и использовать алгоритмы, встроенные в вашу реализацию CLP. Частичный пример:

:- use_module(library(clpfd)).

on_time([]).
on_time([Task|Tasks]) :-
    Task = task(TSuggested,TActual,L,Rs),
    TActual #>= TSuggested - 10,
    TActual #=< TSuggested + 10,
    on_time(Tasks).

Другой предикат будет проверять, что никакие две задачи не используют один и тот же ресурс одновременно:

nonoverlap(R,Task1,Task2) :-
    Task1 = task(_,T1,L1,Rs2),
    Task2 = task(_,T2,L2,Rs2),
    ((member(R,Rs1), member(R,Rs2)) ->
        T2 #> T1+L1     % start Task2 after Task1 has finished
        #\/             % OR
        T1 #> T2+L2     % start Task1 after Task2 has finished
    ;
        true            % non-conflicting, do nothing
    ).

Наконец, вызовите labeling для всех ограниченных переменных, чтобы дать им согласованные значения. При этом используется CLP (fd) , который работает для целочисленных единиц времени. CLP (R) делает то же самое для реального времени, но это немного сложнее. Ссылки предназначены для SWI-Prolog, но SICStus и ECLiPSe имеют похожие библиотеки.

Answer 2

Подобные задачи планирования часто лучше всего решать с помощью либо Constraint Programming CP, либо смешанного целочисленного программирования (MIP). Оба являются декларативными подходами, поэтому вам нужно только сосредоточиться на свойствах вашей проблемы и позволить специализированному движку обрабатывать основной алгоритм. Более подробную информацию можно найти в Википедии:

http://en.wikipedia.org/wiki/Constraint_programming

http://en.wikipedia.org/wiki/Linear_programming

Answer 3

Если вы ограничены или ваша проблемная область будет расширена, вам также следует взглянуть на несовершенные алгоритмы, такие как:

• Метаэвристика , например, поиск по табу и имитация отжига. Существует несколько реализаций с открытым исходным кодом, таких как Drools Planner .

• Генетические алгоритмы, такие как JGap.