Optimizing the scheduling of a pick and place robotic system

Nowadays robotic systems, due to their flexibility and effectiveness are widely used in many manufacturing processes. The packaging industry is no exception to this, and in the last years the industry has registered a steady increase in the demand for robotic systems for pick and place problems. The specific requirements of the pick and place problems can vary, but generally those problems involve at least one input conveyor, from which the system is fed the pieces to be manipulated, and a number of robotic manipulators. The robotic system is tasked to remove the piece goods from the input conveyor and correctly place them in a designated destination. In such problems the quality of the scheduling is of paramount importance, as the scheduling must be able to utilize all the robots to their fullest potential in order to achieve the desired performance. However, the objective of obtaining a high quality scheduling for the system clashes with the very strict time requirements the system imposes to compute the operations of the robots. For this reason the vast majority of the methods proposed for this kind of systems implement very simple techniques, and the most commonly used approaches in the industry use simple queuing strategies for the definition of the scheduling of the system. In this thesis we will focus on the problem of computing the scheduling for a pick and place line for perishable product. In solving the problem we will be putting much emphasis on the quality of the computed solutions, and on the computational time needed to obtain said solutions. For this reason we will approach the problem in two ways. Initially the problem will be formalized in a Mixed Integer Linear Programming formulation and solved using a Row Generation procedure. Then the problem will be solved using a metaheuristic approach, where part of the quality of the solutions is foregone in favour of a much faster solution time. Lastly numerical results for the proposed metaheuristic methods will be presented, showing the effectiveness of the methods and giving some insights on the characteristics of the scheduling problem at hand.

Al giorno d'oggi i sistemi robotici, grazie alla loro flessibilità ed efficacia sono ampiamente utilizzati in molti processi produttivi. L'industria del packaging non fa eccezione, e negli ultimi anni l'industria ha registrato un costante aumento della domanda di sistemi robotici per problemi di pick and place. I requisiti specifici dei problemi pick and place variano notevolmente da caso a caso, ma generalmente coinvolgono almeno un nastro trasportatore di ingresso, che è utilizzando per fornire al sistema i pezzi da manipolare, e un certo numero di manipolatori robotici. Il sistema robotico ha il compito di rimuovere il i pezzi sul nastro trasportatore di ingresso e posizionarli correttamente in una destinazione designata. In tali problemi l'efficienza e la qualità dello scheduling è di fondamentale importanza, in quanto lo scheduling deve essere in grado di utilizzare tutti i robot al loro massimo potenziale per ottenere le prestazioni desiderate. Tuttavia, il problema di ottenere uno scheduling di alta qualità per il sistema scontra con gli stretti requisiti di tempo che il sistema impone per calcolare le operazioni dei robot. Per questo motivo la maggior parte dei metodi proposti per questo tipo di sistemi implementa tecniche molto semplici. In questa tesi ci siamo concentrati sul problema del calcolo dello scheduling per una linea di pick and place per prodotti deperibili. Nel risolvere il problema siamo concentrati sulla qualità delle soluzioni calcolate, ma anche sul tempo di calcolo necessario per ottenere dette soluzioni. Per questo motivo il problema è stato risolto utilizzando due differenti approcci: Inizialmente il problema è stato formalizzato in una formulazione Mixed Integer Linear Programming e risolto in maniera esatta utilizzando una procedura di Row Generation. Successivamente il problema è stato risolto utilizzando il framework metaeuristico dell'Iterated Local Search, dove viene sacrificata l'ottimalità della soluzione trovata in favore di tempi di computazione significativamente ridotti. Infine verranno presentati risultati numerici per i metodi proposti, mostrando l'efficacia dei metodi nel risolvere il problema.