Managing distributed flexible manufacturing systems

For several years, research has focused on several aspects of manufacturing, from the individual processes towards the management of virtual enterprises, but several aspects, like coordination and control, still have relevant problems in industry and remain challenging areas of research. The application of advanced technologies and informational tools by itself does not guarantee the success of control and integration applications. In order to get a high degree of integration and efficiency, it is necessary to match the technologies and tools with models that describe the existing knowledge and functionality in the system and allow the correct understanding of its behaviour. In a global and wide market competition, the manufacturing systems present requirements that lead to distributed, self-organised, co-operative and heterogeneous control applications. A Distributed Flexible Manufacturing System (DFMS) is a goal-driven and data-directed dynamic system which is designed to provide an effective operation sequence for the products to fulfil the production goals, to meet real-time requirements and to optimally allocate resources. In this work first a layered approach for modeling such production systems is proposed. According to that representation, a DFMS may be seen as multi-layer resource-graph such that: vertices on a layer represent interacting resources; a layer at level l is represented by a node in the layer at level (l-1). Then two models are developed concerning with two relevant managerial issues in DFMS, the task mapping problem and the task scheduling with multiple shared resources problem. The task mapping problem concerns with the balanced partition of a given set of jobs and the assignment of the parts to the resources of the manufacturing system. We study the case in which the jobs are quite homogeneous, do not have precedence constraints, but need some communications to be coordinated. So, jobs assignment to different parts causes a relevant communication effort between those parts, increasing the managerial complexity. We show that the standard models usually used to formal represent such a problem are wrong. Through some graph theoretical results we relate the problem to the well-known hypergraph partitioning problem and briefly survey the best techniques to solve the problem. A new formulation of the problem is then presented. Some considerations on an improved version of the formulation permit the computation of a good Lower Bound on the optimal solution in the case of the hypergraph bisection. The task scheduling with multiple shared resources problem is addressed for a robotic cell. We study the general problem of sequencing multiple jobs, where each job consists of multiple ordered tasks and tasks execution requires simultaneous usage of several resources. NP-completeness results are given. A heuristic with a guarantee approximation result is designed and evaluated.

Per molti anni la ricerca scientifica si è concentrata sui diversi aspetti di gestione dei sistemi manifatturieri, dall’ottimizzazione dei singoli processi produttivi, fino alla gestione delle più complesse imprese virtuali. Tuttavia molti aspetti inerenti il coordinamento e il controllo, ancora presentano problematiche rilevanti in ambito industriale e temi di ricerca aperti. L’applicazione di tecnologie avanzate e di strumenti informatici evoluti non riesce da sola a garantire il successo nelle funzioni di controllo e di integrazione. Al fine di ottenere un alto grado di efficienza, è necessario supportare tali tecnologie e strumenti con dei modelli che siano in grado di rappresentare le funzionalità e i processi dei sistemi manifatturieri, e consentano di prevederne e gestirne l’evoluzione. Ne emerge l’esigenza di politiche di controllo e di gestio ne distribuite, che favoriscano l’auto-organizzazione e la cooperazione nei sistemi manifatturieri. I sistemi manifatturieri flessibili distribuiti (DFMS), in risposta a tale esigenza, sono sistemi di produzione dinamici in grado di garantire una risposta in tempo reale alla allocazione ottima delle risorse, e organizzare efficientemente le lavorazioni dei prodotti. In questa tesi viene proposta una modellizzazione a livelli per tali sistemi. Secondo tale rappresentazione un DFMS può essere visto come un grafo strutturato su più livelli, tale che: i vertici del grafo rappresentano le risorse interagenti nel sistema; ogni nodo di un livello rappresenta a sua volta un livello successivo. Partendo da questa rappresentazione, sono stati quindi sviluppati due modelli per lo studio dell’allocazione ottima delle risorse (task mapping) e per l’organizzazione di lavorazioni (task scheduling) che richiedono l’uso simultaneo di risorse condivise nel sistema. Il task mapping problem consiste nella suddivisione bilanciata di un certo insieme di lavorazioni tra le risorse del sistema. In questa tesi si è studiato il caso in cui le lavorazioni sono omogenee, non presentano vincoli di precedenza, ma necessitano di un certo volume di comunicazione tra le risorse cui sono assegnate per garantirne il coordinamento, incidendo in tal senso sulla complessità di gestione. L’analisi critica dei modelli che sono tipicamente usati in letteratura per rappresentare tale problema, ne hanno posto in evidenza l’inadeguatezza. Attraverso alcuni risultati teorici si è quindi dimostrato come il problema possa ricondursi ad un hypergraph partitioning problem. Studiando la formulazione matematica di tali problemi, e limitandosi al caso di due risorse produttive, si è infine giunti alla determinazione di una buona approssimazione sulla soluzione ottima. Il problema di sequenziamento delle lavorazioni (task scheduling) che richiedono l’uso simultaneo di risorse condivise è stato trattato nel caso specifico di celle robotizzate. E’ stata quindi dimostrata l’NP-completezza di questo problema ed è stata progettata una euristica di soluzione, validandone i risultati in diversi scenari produttivi.