Constraint Programming

Prof. Marco Gavanelli

14 giugno 2018

Descrizione problema

Un server di stampa deve decidere lo scheduling delle stampe su una stampante. Il server ha ricevuto un insieme di richieste di stampa, riportate nel file task.pl; ciascuna richiesta è rappresentata da un fatto

dove

• ID è un identificatore univoco della richiesta
• EST (Earliest Start Time) è il primo istante di tempo in cui può iniziare la stampa: la stampa non può iniziare prima di EST.
• LCT (Latest Completion Time) è l'ultimo istante di tempo in cui la stampa può terminare: può terminare prima di LCT oppure in LCT ma non dopo
• D è la durata della stampa.

Poiché alcune stampe potrebbero avere una durata superiore a quella prevista, si è deciso di massimizzare la distanza temporale fra le coppie di stampe. Più precisamente, date una stampa i ed una stampa j, la distanza fra i e j è la differenza fra l'istante di terminazione della prima stampa e l'istante di inizio della seconda (in ordine temporale). Ad esempio, se

• la stampa 1 inizia all'istante 6 e finisce all'istante 10
• la stampa 2 inizia all'istante 2 e finisce all'istante 3
• la stampa 3 inizia all'istante 12 e finisce all'istante 14

allora

• la distanza fra 1 e 2 è 6−3=3
• la distanza fra 1 e 3 è 12−10=2
• la distanza fra 2 e 3 è 12−3=9

quindi la minima distanza fra due stampe è 2.

CLP (punti 13)

Si risolva il problema usando ECLⁱPS^e.

ASP (12 punti)

Per semplicità, il file task.pl contiene anche i predicati

• maxend/1, che ha come argomento l'istante di tempo più grande che ha senso tenere in considerazione
• temp/1, che è vero per tutti gli istanti di tempo che interessano nel problema (da 0 al valore riportato in maxend)

Si risolva il problema in Answer Set Programming.