quale algoritmo per un programma di programmazione

Question

Ho questo problema di pianificazione delle attività. Ogni attività ha un orario di inizio T suggerito (deve iniziare a [T-10, T + 10]), richiede L minuti per essere completato e utilizza un numero di risorse [R1, R2, ...]. Quando viene utilizzata una risorsa, nessun'altra attività può utilizzarla. Dato che solo l'orario di inizio è flessibile, il mio obiettivo è pianificare le attività in modo che possano accedere a qualsiasi risorsa di cui hanno bisogno o segnalare tutti i conflitti che devono essere risolti.

Quale algoritmo posso utilizzare per questo scopo? Grazie.

Answer 1

Dal momento che hai codificato questo come prolog, vi consiglio di attuazione nel constraint logic programming (CLP) e utilizzando gli algoritmi integrati nel vostro implementazione CLP. Esempio parziale:

:- 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). 

Un altro predicato sarebbe controllare che non ci sono due compiti utilizzano la stessa risorsa contemporaneamente:

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 
    ). 

Infine, chiamano labeling su tutte le variabili vincolate per dare loro valori coerenti. Questo utilizza CLP(fd), che funziona per unità di tempo interi. CLP(R) fa lo stesso per il tempo reale, ma è leggermente più complicato. I collegamenti sono per SWI-Prolog ma SICStus e ECLiPSe hanno librerie simili.

Answer 2

I problemi di pianificazione di questo tipo sono spesso affrontati utilizzando CP con programmazione vincolata o MIP (Mixed Integer Programming). Entrambi sono approcci dichiarativi, quindi è sufficiente concentrarsi sulle proprietà del problema e lasciare che un motore specializzato gestisca l'algoritmo sottostante. Maggiori informazioni possono essere trovate su Wikipedia:

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

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

Answer 3

Se sei vincoli o il vostro dominio del problema scalerà fuori, si dovrebbe anche dare un'occhiata a degli algoritmi imperfette, come ad esempio:

• Metaheuristics come la ricerca tabu e ricottura simulata. Ci sono un paio di implementazioni open source là fuori, come ad esempio Drools Planner.

• Algoritmi genetici, come JGap.