Applicazioni di Intelligenza Artificiale - CLP

Prof. Marco Gavanelli

29 Marzo 2007

Esercizio (8 punti)

Un'azienda che produce automobili ha tre linee di montaggio per inserire i tre possibili optional: cerchi in lega, aria condizionata e navigatore satellitare. Si ha una sequenza di richieste, memorizzate nel file automobili.pl ; ciascuna richiesta è strutturata come segue:

• Num è un identificatore univoco della richiesta
• Consegna è l'orario massimo di consegna (in minuti)
• CerchiLega, AriaCondizionata e Satellitare sono i possibili optional: essi valgono 1 se l'optional è stato richiesto, 0 altrimenti.

1. ciascuna automobile può essere mandata in una delle 3 linee di montaggio degli optional (non può essere contemporaneamente in due linee)
2. ciascuna linea di montaggio può lavorare su un'automobile alla volta
3. l'installazione degli optional ha i seguenti tempi
   • cerchi in lega: 20 minuti
   • aria condizionata: 80 minuti
   • navigatore satellitare: 50 minuti

Si scriva un programma CLP che stabilisca l'orario in cui vengono montati gli optional sulle auto rispettando tutti i vincoli e minimizzando il tempo totale.

Suggerimento   Si veda sul manuale la libreria edge_finder (o, equivalentemente, edge_finder3 ).

Soluzione

:- lib(fd).
:- lib(edge_finder3).
:- [automobili].

schedule(Lrich,LT):-
% Creo la lista delle richieste Lrich
    findall(rich(Num,Consegna,Cerchi,Aria,Sat),
        rich(Num,Consegna,Cerchi,Aria,Sat),
        Lrich),
    crea_task(Lrich,LT,Span,D1,D2,D3),
    seleziona_linee(LT,L1,L2,L3),
% Impongo che ciascuna delle linee non sia occupata da due
% auto contemporaneamente
    disjunctive(L1,D1),
    disjunctive(L2,D2),
    disjunctive(L3,D3),
    append(LT,[Span],Ltot),
    min_max(labeling(Ltot),Span).

% crea_task(Richieste,StartTimes,TempoTotale,Durate1,Durate2,Durate3)
crea_task([],[],_,[],[],[]).
crea_task([rich(_N,C,O1,O2,O3)|Lrich],[T1,T2,T3|LT],Span,[D1|LD1],[D2|LD2],[D3|LD3]):-
% Creo i domini
    [T1,T2,T3] :: 0..C,
% Calcolo la durata dell'installazione di ciascun optional
% Se l'optional non e` selezionato -> durata 0
    D1 #= O1*20,
    D2 #= O2*80,
    D3 #= O3*50,
% Impongo che il tempo in cui si termina l'installazione
% Sia minore del tempo di consegna e del tempo totale dello schedule
    T1+20 #<= C, T1+20 #<= Span,
    T2+80 #<= C, T2+80 #<= Span,
    T3+50 #<= C, T3+50 #<= Span,
% Impongo che l'automobile non sia contemporaneamente in due delle tre linee
    disjunctive([T1,T2,T3],[D1,D2,D3]),
    crea_task(Lrich,LT,Span,LD1,LD2,LD3).

% seleziona_linee(StartTimes,StartOpt1,StartOpt2,StartOpt3)
% Data una lista di StartTimes, fornisce in uscita le 3 liste (una per ogni linea)
seleziona_linee([],[],[],[]).
seleziona_linee([T1,T2,T3|LT],[T1|L1],[T2|L2],[T3|L3]):-
    seleziona_linee(LT,L1,L2,L3).