A meta-heuristic algorithm to minimise the total weighted tardiness in a single machine scheduling problem with release dates and sequence dependent set-up times

This study aims to generate a meta-heuristic algorithm to minimize the total weighted tardiness on the single machine with sequence dependent set up and release dates. Due to the computational complexity of the considered problem, an heuristic method is preferred to an exact method. The developed meta-heuristic approach combines a composite dispatching rule with a local search method. The selected dispatching rule is based on an Apparent Tardiness Cost index, and it is known by the literature as ATCRS. The solution generated with this rule becomes the initial solution for a Tabu Search algorithm. Tabu Search performs an exploration of the solution neighborhood trying to improve the solution quality. The proposed methodology is therefore composed by two heuristic approaches: a construction method and an improvement method. The performances of the new solution approach have been evaluated on a set of properly generated single machine scheduling problems. Performances' results have been obtained through a benchmark with an exact method. The outcome of the performance evaluation has shown the effectiveness of the meta-heuristic algorithm in minimizing the total weighted tardiness for the considered problem. Moreover, the solution methodology has been applied to an industrial use-case in order to test its applicability in industrial settings. In this real problem application the scheduling algorithm proved again its effectiveness and the results highlighted the improvement generated on company schedules.

Questa tesi ha l'obiettivo di generare un algoritmo meta-euristico per minimizzare le ore totali di ritardo pesate, per un problema di schedulazione della produzione su singola macchina, con date di rilascio e tempi di set up dipendenti dalla sequenza produttiva. Un approccio euristico è stato preferito ad un approccio esatto a causa della complessità computazionale del problema considerato. L'algoritmo meta-euristico combina una regola di sequenziamento composta con un metodo di ricerca locale. In particolare l'approccio risolutivo è composto da una regola di sequenziamento basata su indice ATC, conosciuta in letteratura come ATCRS. La soluzione generata con questa regola diventa la soluzione iniziale per un algoritmo di Tabu Search. Tabu Search esplora il vicinato della soluzione nello spazio delle soluzioni provando a minimizzare ulteriormente la funzione obiettivo. L'algoritmo sviluppato combina quindi due diversi approcci euristici: un metodo costruttivo e un metodo di miglioramento. Il nuovo approccio risolutivo è stato valutato su un insieme di istanze del problema opportunamente generate. I risultati sulle performance dell'algoritmo sono stati ottenuti facendo un confronto con un metodo esatto. Le analisi su questi risultati hanno dimostrato l'efficacia dell'algoritmo meta-euristico nel minimizzare le ore totali di ritardo pesate per il problema considerato. Inoltre, il metodo risolutivo è stato applicato a un caso industriale per testare l'applicabilità dell'algoritmo in un contesto aziendale. In questo caso di applicazione reale l'algoritmo di schedulazione ha dimostrato la sua efficacia e i risultati ottenuti evidenziano un netto miglioramento sulle schedulazioni dell'azienda.