Heuristic algorithms on a multihead weigher machine setup problem

This thesis work summarizes the results of a research project involving a computer controlled machine called Multihead Weigher. This machine has a wide range of applications in the food industry for dried foods such as pasta, pet foods, coffee, cereals, or fresh foods such as salad, spare ribs, etc. Since the speed and the accuracy of the packaging line mainly depend on its performances, the machine needs an optimal setup strategy and a proper operation software. The operation software, working in real time, selects the best hopper subset to be opened according to the product, the time constraints and the objective function. This industrial problem can be modeled as a knapsack problem. Instead, the setup problem deals with the definition of the average quantity of product (setpoints) delivered by the radial feeders to each hopper. Thus, the focus of this research is on the jointly determination of the optimal setpoints for a specific machine. Those setpoints define the output of the multihead weigher, which is the average weight discharged by the machine. In order to evaluate the output, thus the performances, an economic objective function has been proposed. To assess the system performances we choose to rely on a simulator that mimics the behaviour of a simple Multihead Weigher machine since the analytical way was not viable. In this project three different methods are proposed to find the setpoints that minimize the objective function. The discretized case is fulfilled with a Brute-force search in combination with some heuristic rules that can reduce the number of solutions to be evaluated. On the other hand, to tackle the continuous case, the Response Surface Methodology and the Particle Swarm Optimization are implemented. The three methods have been evaluated with two different operation knapsack problems and with an ad hoc developed economic iterative knapsack. Having defined all the optimizer and the operation policies for the simulator, the research proposes a full comparison of all methods in order to pinpoint the best approach. Eventually, we propose a comparison between the currently used approach and our best approach.

Questo lavoro di tesi riassume i risultati di un progetto di ricerca relativo ad una macchina controllata computericamente chiamata Pesatrice Multitesta. Questa macchina ha ampie possibilità di applicazioni soprattutto nelle industrie alimentari sia per il confezionamento di prodotti secchi come pasta, cibo per animali, caffè e cereali, sia per il confezionamento di prodotti freschi quali insalate, costine, ecc. Poiché la velocità e la precisione della linea produttiva dipendono principalmente dalle sue prestazioni, la macchina necessita si una strategia di setup ottimale e un adeguato software di gestione. Quest'ultimo, operando in tempo reale, seleziona il miglior sottoinsieme di cestelli da aprire in relazione al prodotto, ai vincoli di tempo e alla funzione obiettivo. Questo problema industriale può essere modellato con il cosiddetto “Knapsak problem”. Invece, il problema di setup riguarda la definizione della quantità media di prodotto (setpoint) trasportata dai canali radiali a ciascun cestello. Quindi, l’obiettivo di questo lavoro è la determinazione del setpoint ottimale per una specifica macchina. Questi setpoint influenzano l’output della Pesatrice Multitesta, ovvero il valor medio di prodotto contenuto all'interno di un pacchetto. Al fine di valutare l’output, e di conseguenza le prestazioni della macchina, è stata proposta una funzione obiettivo di tipo economica. Per valutare le prestazioni della macchina abbiamo scelto di basarci su un simulatore che replichi il comportamento di una pesatrice Multitesta poiché la via analitica non risulta attualmente percorribile. In questo progetto sono stati proposti tre differenti metodi per trovare i setpoint che minimizzano la funzione obiettivo. Il caso discreto è trattato seguendo un approccio Brute-force in combinazione con alcune regole euristiche atte alla riduzione del numero di soluzioni da valutare. Il caso continuo, invece, è stato analizzato mediante sia la tecnica Response Surface Methodology che la Particle Swarm Optimization. Questi tre metodi sono stati valutati con due differenti problemi di gestione (Knapsak Problems) e con un Knapsak iterativo sviluppato appositamente. Avendo definito tutti gli ottimizzatori e tutte le politiche di gestione per il simulatore, la ricerca propone un confronto tra tutti i metodi per delineare il miglior approccio. In conclusione, proponiamo un confronto tra in metodo correntemente usato e il metodo da noi proposto.