Esercizio Stampe
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 minima 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.
