Metodi di ottimizzazione per problemi di knapsack e tool switching

This Ph.D. thesis deals with two different classes of optimization problems: knapsack problems and tool switching problems. Knapsack problems became a classical and rich research area in combinatorial optimization after the seminal books by Martello and Toth (1990) and Kellerer, Pferschy, and Pisinger (2004). The first purpose of this thesis is to provide a comprehensive survey to cover the developments that appeared in this field after the publication of the latter volume. After a brief introduction, the second chapter is devoted to problems whose goal is to optimally assign items to a single knapsack. Besides the classical knapsack problems (binary, subset sum, bounded, unbounded, change-making), we review problems with special constraints (setups, multiple-choice, conflicts, precedences, sharing, compartments) as well as relatively recent fields of investigation, like robust and bilevel problems. The third chapter covers multiple, multidimensional, and quadratic knapsack problems, and includes a succinct treatment of online and multiobjective knapsack problems. Motivated by a real-world application in the colour printing industry, in the subsequent part of the thesis, we deal with different variants of the well-known Tool Switching Problem (ToSP). In the fourth chapter, we introduce four different variants of ToSP. For each variant, we discuss its complexity and propose a mathematical formulation. The third and fourth variants introduce a novel requirement into ToSP: the tool order constraint. Under this requirement, during the processing of each job, the selected tools must be sorted along the slot sequence in the machine, and the machine will use them for processing the job applying the tools in that order. We show that the new problem variants are NP-hard even when the job sequence is given as part of the input and the setup times are binary. We solve them by using dedicated arc flow models. We evaluate the effectiveness of the models on several instances that are generated with the aim of covering different scenarios of interest. In the fifth chapter, we tackle an interesting real-world industrial problem arising in a food packaging company located in the city of Reggio Emilia (Italy). The problem faced by the company generalizes the last variant of ToSP tackled in the fourth chapter to a great extent (as it includes parallel heterogeneous machines, release and due dates, and several additional complicating features). In particular, we addressed a scheduling problem that consists in assigning printing jobs to a heterogeneous set of parallel flexographic printer machines, with the aim of minimizing a weighted sum of total weighted tardiness and total setup time. To solve it, we developed a greedy randomized adaptive search procedure equipped with several local search procedures. The excellent performance of the algorithm is proved by extensive computational experiments on real-world instances, for which it produced good-quality solutions within a limited computing time. Since in the real problem the setup and processing times are subject to significant uncertainties, the forecasting of these times is a very difficult task and significantly influences the quality and efficiency of scheduling. In the last chapter, we use machine learning regression algorithms to estimate these times using a real-world industrial database.

Questa tesi di dottorato affronta due diverse classi di problemi di ottimizzazione: i knapsack problem e i tool switching problem. I knapsack porblem sono diventati un'area di ricerca classica e ricca nell'ottimizzazione combinatoria dopo i libri seminali di Martello e Toth (1990) e Kellerer, Pferschy e Pisinger (2004). Il primo scopo del nostro lavoro è quello di fornire un quadro completo degli sviluppi che sono apparsi in questo campo dopo la pubblicazione di quest'ultimo volume. Dopo una breve introduzione, il secondo capitolo è dedicato ai problemi il cui obiettivo è assegnare in modo ottimale gli oggetti ad un unico zaino. Oltre ai classici problemi di knapsack (binary, subset sum, bounded, unbounded, change-making), esaminiamo problemi con vincoli particolari (setups, multiple-choice, conflicts, precedences, sharing, compartments) così come campi di indagine relativamente recenti, come problemi robusti e bilivello. Il terzo capitolo copre problemi multipli, multidimensionali e quadratici del knapsack e include una sintetica trattazione dell'onine e del multiobjective knapsack problem. Motivati da un'applicazione del mondo reale nel settore della stampa a colori, nella parte successiva della tesi, ci occupiamo di diverse varianti del noto Tool Switching Problem (ToSP). Nel quarto capitolo introduciamo quattro diverse varianti del ToSP. Per ogni variante, ne discutiamo la complessità e proponiamo una formulazione matematica. La terza e la quarta variante introducono un nuovo vincolo nel ToSP: il vincolo d'ordine dei tool. In base a questo vincolo, durante il processamento di ogni lavoro, i tool selezionati sono ordinati lungo la sequenza di slot della macchina in un dato ordine e la macchina li dovrà utilizzare in quell'ordine. Mostriamo che le nuove varianti del problema sono NP-hard anche quando la sequenza di lavoro viene fornita come input e i tempi di setup sono binari. Risolviamo il problema utilizzando specifici modelli di arc flow. Ne valutiamo quindi l'efficacia su più istanze che sono state generate con l'obiettivo di coprire diversi scenari di interesse. Nel quinto capitolo, affrontiamo un interessante problema industriale di un'azienda di confezionamento alimentare situata nella città di Reggio Emilia (Italia). Il problema affrontato dall'azienda generalizza in larga misura l'ultima variante del ToSP affrontata nel quarto capitolo (in quanto include macchine parallele eterogenee, date di rilascio e di scadenza e altre diverse caratteristiche aggiuntive). In particolare, affrontiamo un problema di schedulazione che consiste nell'assegnare i lavori di stampa a un insieme eterogeneo di macchine da stampa flessografiche parallele, con l'obiettivo di ridurre al minimo una somma ponderata del ritardo totale pesato e del tempo totale di setup. Per risolverlo, abbiamo sviluppato un greedy randomized adaptive search procedure dotato di diverse procedure di ricerca locale. Le eccellenti prestazioni dell'algoritmo sono dimostrate da estesi esperimenti computazionali su istanze del mondo reale, per le quali l'algoritmo produce soluzioni di buona qualità in un tempo di calcolo limitato. Poiché nel problema reale i tempi di setup e processamento sono soggetti a notevoli incertezze, la previsione di questi tempi è un compito molto difficile e influenza significativamente la qualità e l'efficienza della schedulazione. Nell'ultimo capitolo, utilizziamo algoritmi di apprendimento automatico per stimare questi tempi utilizzando un database industriale.