Modelli di programmazione lineare intera per problemi di schedulazione a lotti

In questo progetto viene trattata la schedulazione del BPM (Batch Processing Machine), considerando elementi denominati jobs, i quali hanno diverse dimensioni e differenti tempi di lavorazione, e un macchinario dotato di batch (vassoi), tutti della stessa dimensione per poter essere inseriti all’interno dello stesso quando si processano i jobs. L’obiettivo delle simulazioni è quello di minimizzare il Makespan, ovvero il tempo che intercorre tra il momento in cui il primo job inizia ad essere processato e quello in cui viene completata la lavorazione dell’ultimo job in produzione. Utilizzando un Arc-flow (flusso ad archi), basato su un approccio di ottimizzazione, si costruisce una nuova formulazione che lo rappresenta come un problema di determinazione dei flussi in un grafico. La dimensione della formulazione cresce con la capacità del macchinario, con il numero di dimensioni distinte e con i vari tempi di processamento tra i jobs, ma non aumenta con il crescere del numero di jobs che rende la formulazione stessa davvero efficace nel risolvere istanze di grandi dimensioni in modo ottimale, specialmente quando diversi jobs hanno uguali dimensioni e tempi di lavorazione. È stato messo a confronto il modello in questione con altri modelli della letteratura, mostrandone chiaramente la sua superiorità nel testare le prestazione e provando l’ottimalità di simulazioni casuali fino a 100 milioni di jobs. Sono stati dunque analizzati i 3 modelli denominati MILP1 (Mixed Integer Linear Programming), MILP1 + e FLOW, implementandoli nel programma Cplex e facendo ad esso testare molteplici dati per verificare la stabilità e l’ottimalità delle soluzioni dei 3 diversi modelli. In Trindade et. al. (2018) gli autori hanno presentato un riformulazione del MILP1 , presentato in Melouk et.al.(2004), in cui le soluzioni simmetriche sono state eliminate utilizzando il seguente approccio: - Gli indici dei jobs sono definiti ordinando in maniera non decrescente i loro tempi di lavorazione - Il vassoio k può essere utilizzato solo se ad esso è assegnato il job k, ∀ k ∈ K - Il job j può essere assegnato al vassoio k solo se j ≤ k, ∀ k ∈ K e ∀ j ∈ J Si vuole verificare, nello specifico, ciò che viene affermato in merito alla comparazione fatta con i 3 modelli sopracitati, ovvero: - FLOW è molto superiore a MILP1 e MILP1+, specialmente quando cresce il numero di jobs - Le piccole istanze, fino a 50 jobs, vengono risolte più velocemente dal MILP1+ rispetto al FLOW, anche se lo scarto è solo di una frazione di secondo. - A differenza dei modelli MILP1 e MILP1+, il numero di variabili nel FLOW non aumenta quando cresce il numero di jobs.