Hoist scheduling problem

In industrial production lines, hoists are responsible to move a variety of parts, e.g. circuit boards, along a series of tanks in a predefined order of stages. This hoist scheduling problem must deal with several constraints, such as time-windows, no-wait and hoists collisions, that make it NP-hard in nature. Manufacturers strive to find a schedule that allows to process all given parts in the minimum time while guaranteeing all the imposed constraints. In this thesis we propose novel methods to solve both cyclic and dynamic schedules subject to general scenarios. Extensions such as, multi-hoist, multi-job, multi-tank stages and multi-function tanks, are all considered. A Mixed Integer Linear Programming model has been used to find the optimal solution through a commercial solver. Then, a heuristic algorithm, valid for all types of problems, is developed to obtain an approximation of the optimal solution in a much shorter time. Results demonstrate that our complete model, although capable of solving most of the different cases in literature, can only deal with simple problems as it naturally requires a significant computational time. This is particularly true for dynamic problems, as they usually deal with a larger amount of variables, due to the multi-job extension. For larger problems, the heuristic model performs well both in terms of accuracy and efficiency. Comparison was made with both cases in the literature and real case scenarios of hoist scheduling problems.

Nelle linee di produzione industriali, i carrelli sono responsabili del movimento di diversi pezzi, ad esempio circuiti stampati, lungo una serie di vasche secondo un ordine di fasi prestabilito. Questo problema denominato hoist scheduling problem deve soddisfare molti vincoli, come i vincoli di tempo e di collisione fra i carrelli, i quali lo rendono intrinsecamente un problema NP-completo. Le industrie necessitano di trovare una schedulazione che permetta di processare tutti i pezzi nel minimo tempo possibile, garantendo che tutti i vincoli imposti siano soddisfatti. In questa tesi proponiamo nuovi metodi per risolvere problemi ciclici e dinamici, soggetti a casistiche generali. Estensioni come multi-hoist, multi-job, multi-tank stages and multi-function tanks, sono tutte considerate. Per trovare la soluzione ottimale usiamo un modello di tipo Mixed Integer Linear Programming e un solver commerciale. In aggiunta, abbiamo sviluppato un algoritmo euristico, valido per tutti i tipi di problemi, al fine di ottenere un'approssimazione della soluzione ottimale in un tempo molto più breve. I risultati dimostrano che il nostro modello, anche se in grado di risolvere la maggior parte dei casi presenti in letteratura, può facilmente gestire solo problemi semplici, poichè il tempo di computazione richiesto è considerevole. Questo aspetto è particolarmente osservabile nei problemi dinamici, i quali devono gestire un maggior numero di variabili, dovuto all'estensione multi-job. Per problemi più grandi, le prestazioni del modello euristico sono buone sia in termini di accuratezza che di efficienza. I test sono stati fatti con casi presenti in letteratura e con casi reali.