Politecnico di Torino | Servizi per la didattica

KEYWORD

Schedulazione di macchine parallele con tempi di setup dipendenti dalla sequenza

keywords MACHINE SCHEDULING, METAEURISTICHE, OTTIMIZZAZIONE COMBINATORIA

Research Groups DISMA - Ottimizzazione e ricerca operativa

Description Oggetto della tesi e' la schedulazione di un insieme di job (ordini di produzione) su un insieme di macchine parallele, non necessariamente identiche, caratterizzate da significativi tempi di setup dipendenti dalla sequenza (esempio: saldatura di componenti su schede elettroniche; industria tessile; produzioni caratterizzate da problemi di compatibilita' cromatica e chimica; etc.). Il problema richiede di assegnare i job alle macchine e metterli in sequenza, rispettando vincoli tecnologici e vincoli sui tempi di rilascio (dipendenti dalla disponibilita' di materie prime), in modo da ottimizzare un tradeoff tra efficienza e rispetto delle date di consegna. In linea di principio, un modello MILP risolve il problema, ma dati i tempi di calcolo eccessivi si devono applicare metaeuristiche (iterated local search, GRASP, Tabu search, etc.) basate su meccanismi di ricerca locale. Scopo della tesi e' sperimentare metaeuristiche avanzate (variable neighborhood search, large neighborhoods) che integrano i meccanismi di exploration/exploitation con la soluzione di modelli di ottimizzazione ristretti.