Confronto tra le formulazioni NV e TIV per il problema della schedulazione

In questa tesi si analizzano due formulazioni diverse per il problema della schedulazione, il cui obbiettivo generale è allocare lavori su macchine nel tempo. Si affrontano problemi di schedulazione di n lavori indipendenti su m macchine identiche parallele (PS) con un singolo server con l’obbiettivo di minimizzare il makespan. Si sceglie di affrontare il problema attraverso due formulazioni di programmazione intera mista (MIP): network variables (NV) e time-indexed variables (TIV). I modelli verranno testati con un set di lavori generale (general job set). La prima cosa che caratterizza e differenzia i modelli è il modo in cui vengono scelte e definite le variabili decisionali. Il modello NV è un modello di MIP basato sul problema storico del commesso viaggiatore. La variabile decisionale è una variabile binaria indicizzata dai lavori e dalle macchine ed assume valore 1 se il lavoro i precede immediatamente il lavoro j sulla stessa macchina. Per evitare che i lavori che richiedono il server si sovrappongano viene introdotta un’altra variabile decisionale binaria che assume valore 1 se il lavoro dummy i+n finisce di essere processato prima del lavoro dummy j+n. Il modello TIV è una formulazione più innovativa e migliorata basata sulla discretizzazione del tempo. Il tempo è diviso in periodi 1,2,...,T dove il periodo t inizia in t-1 e finisce in t. L’orizzonte di tempo fissato T è una parte molto importante del modello la cui dimensione dipende da esso e il makespan è minore o uguale a T. La variabile decisionale è una variabile binaria indicizzata dal lavoro e dal tempo ed assume valore 1 se il lavoro i inizia il suo processo al tempo t. I due modelli sono stati implementati in Cplex e si è deciso di estrarre come risultati il makespan, il tempo impiegato e il numero di nodi analizzati. Si confrontano i due modelli in base ai valori ottenuti.