it gb
it gb

A. Grosso - Un approccio di column-generation per la minimizzazione del total flowtime su macchina singola con parallel batching

Viene proposto un nuovo approccio basato su tecniche di programmazione lineare intera per un problema di schedulazione su macchina singola. La macchina deve processare n job caratterizzati sia da un tempo di lavorazione che da un "ingombro". I job vengono impaccati in lotti, che vengono lavorati uno per volta. I job di uno stesso lotto vengono processati in parallelo, e l'intero lotto richiede un tempo di lavorazione pari al tempo di lavorazione del job più lungo. L'"ingombro" dei job limita la possibilità di raggruppare i job in lotti, in quanto ogni lotto non può accogliere job per un ingombro complessivo superiore ad una soglia fissata. Si cerca un piano di lavorazione che minimizzi la somma dei tempi di completamento di tutti i job.

Il problema è NP-completo, e non sono noti modelli di programmazione lineare efficaci per la sua risoluzione. L'approccio proposto rende possibile calcolare un rilassamento continuo molto efficace per il problema, rende immediatamente disponibile un algoritmo euristico veloce ed efficace, e apre la strada per possibili approcci esatti basati sulla tecnica del branch and price.