Applicazioni di Intelligenza Artificiale - CLP

Prof. Marco Gavanelli

31 marzo 2011

Esercizio (8 punti)

Un insieme di attività è definito tramite il predicato task/2 nel file task.pl . Il predicato task è definito tramite alcuni fatti Prolog, con questa sintassi:

• ID è un identificatore univoco dell'attività
• Durata è un intero che rappresenta la durata dell'attività

Ciascuna attività deve essere eseguita su una macchina e, una volta iniziata, l'attività non può essere interrotta. Ogni macchina può eseguire una sola attività alla volta.

Poiché si vuole terminare tutte le attività entro un tempo dato Tmax, si desidera sapere qual è il numero minimo di macchine necessario.

Si scriva un programma CLP(FD) che, preso in ingresso un parametro Tmax, fornisce il minimo numero di macchine necessario per eseguire tutti i task e l'istante di tempo in cui ciascuna attività inizia.

Soluzione

Utilizziamo il vincolo cumulative, assegnando ad ogni attività un tempo di inizio, la durata stabilita dal predicato task/2 e un consumo di risorse pari a 1.

Poiché il limite di risorse nel vincolo cumulativo deve essere ground, non posso metterlo nella funzione obiettivo. Per questo, considero il massimo numero possibile di macchine necessario, che e` pari al numero delle attivita` (Ntask). Poi inserisco una attività fittizia, che inizia al tempo 0, ha come durata tutta la durata possibile (fino a Tmax) e consuma un numero di risorse variabile (FreeRes). Poi massimizzo il numero di risorse usate da tale attività, ovvero minimizzo il numero di risorse utilizzate dagli altri task.

:- lib(fd).
:- lib(cumulative).

:- [task].

minoverlap(Lstart,Tmax):-
    findall(D,task(_,D),Ldur),
    length(Ldur,Ntask),
    length(Lstart,Ntask),
    Lstart ::0..Tmax,
    max_span(Lstart,Ldur,Tmax),
    FreeRes :: 0..Ntask,
    ones(Ones,Ntask),
    cumulative([0|Lstart],[Tmax|Ldur],[FreeRes|Ones],Ntask),
    UsedRes #= Ntask-FreeRes,
    append(Lstart,[UsedRes],Lvars),
    minimize(labeling(Lvars),UsedRes).

% max_span(StartTimes,Durate,Tmax)
% Impone che tutti i task terminino entro Tmax
max_span([],[],_).
max_span([Start|Lstart],[D|Ldur],Tmax):-
    Start+D #<= Tmax,
    max_span(Lstart,Ldur,Tmax).

% ones(L,N)
% crea una lista di lunghezza N con tutti '1'
ones([],0):-!.
ones([1|T],N):-
    N1 is N-1,
    ones(T,N1).