Constraint based methods for allocation and scheduling of periodic applications

This work presents exact algorithms for the Resource Allocation and Cyclic Scheduling Problems (RA&CSPs). Cyclic Scheduling Problems arise in a number of application areas, such as in hoist scheduling, mass production, compiler design (implementing scheduling loops on parallel architectures), software pipelining, and in embedded system design. The RA&CS problem concerns time and resource assignment to a set of activities, to be indefinitely repeated, subject to precedence and resource capacity constraints. In this work we present two constraint programming frameworks facing two different types of cyclic problems. In first instance, we consider the disjunctive RA&CSP, where the allocation problem considers unary resources. Instances are described through the Synchronous Data-flow (SDF) Model of Computation. The key problem of finding a maximum-throughput allocation and scheduling of Synchronous Data-Flow graphs onto a multi-core architecture is NP-hard and has been traditionally solved by means of heuristic (incomplete) algorithms. We propose an exact (complete) algorithm for the computation of a maximum-throughput mapping of applications specified as SDFG onto multi-core architectures. Results show that the approach can handle realistic instances in terms of size and complexity. Next, we tackle the Cyclic Resource-Constrained Scheduling Problem (i.e. CRCSP). We propose a Constraint Programming approach based on modular arithmetic: in particular, we introduce a modular precedence constraint and a global cumulative constraint along with their filtering algorithms. Many traditional approaches to cyclic scheduling operate by fixing the period value and then solving a linear problem in a generate-and-test fashion. Conversely, our technique is based on a non-linear model and tackles the problem as a whole: the period value is inferred from the scheduling decisions. The proposed approaches have been tested on a number of non-trivial synthetic instances and on a set of realistic industrial instances achieving good results on practical size problem.

Sviluppo di sistemi per l'analisi della combustione in tempo reale per motori endotermici alternativi

I moderni motori a combustione interna diventano sempre più complessi L'introduzione della normativa antinquinamento EURO VI richiederà una significativa riduzione degli inquinanti allo scarico. La maggiore criticità è rappresentata dalla riduzione degli NOx per i motori Diesel da aggiungersi a quelle già in vigore con le precedenti normative. Tipicamente la messa a punto di una nuova motorizzazione prevede una serie di test specifici al banco prova. Il numero sempre maggiore di parametri di controllo della combustione, sorti come conseguenza della maggior complessità meccanica del motore stesso, causa un aumento esponenziale delle prove da eseguire per caratterizzare l'intero sistema. L'obiettivo di questo progetto di dottorato è quello di realizzare un sistema di analisi della combustione in tempo reale in cui siano implementati diversi algoritmi non ancora presenti nelle centraline moderne. Tutto questo facendo particolare attenzione alla scelta dell'hardware su cui implementare gli algoritmi di analisi. Creando una piattaforma di Rapid Control Prototyping (RCP) che sfrutti la maggior parte dei sensori presenti in vettura di serie; che sia in grado di abbreviare i tempi e i costi della sperimentazione sui motopropulsori, riducendo la necessità di effettuare analisi a posteriori, su dati precedentemente acquisiti, a fronte di una maggior quantità di calcoli effettuati in tempo reale. La soluzione proposta garantisce l'aggiornabilità, la possibilità di mantenere al massimo livello tecnologico la piattaforma di calcolo, allontanandone l'obsolescenza e i costi di sostituzione. Questa proprietà si traduce nella necessità di mantenere la compatibilità tra hardware e software di generazioni differenti, rendendo possibile la sostituzione di quei componenti che limitano le prestazioni senza riprogettare il software.

A New Test Rig for In-Vitro Evaluation of the Knee Joint Behaviour

The evaluation of the knee joint behavior is fundamental in many applications, such as joint modeling, prosthesis and orthosis design. In-vitro tests are important in order to analyse knee behavior when simulating various loading conditions and studying physiology of the joint. A new test rig for in-vitro evaluation of the knee joint behavior is presented in this paper. It represents the evolution of a previously proposed rig, designed to overcome its principal limitations and to improve its performances. The design procedure and the adopted solution in order to satisfy the specifications are presented here. Thanks to its 6-6 Gough-Stewart parallel manipulator loading system, the rig replicates general loading conditions, like daily actions or clinical tests, on the specimen in a wide range of flexion angles. The restraining actions of knee muscles can be simulated when active actions are simulated. The joint motion in response to the applied loads, guided by passive articular structures and muscles, is permitted by the characteristics of the loading system which is force controlled. The new test rig guarantees visibility so that motion can be measured by an optoelectronic system. Furthermore, the control system of the new test rig allows the estimation of the contribution of the principal leg muscles in guaranteeing the equilibrium of the joint by the system for muscle simulation. Accuracy in positioning is guaranteed by the designed tibia and femur fixation systems,which allow unmounting and remounting the specimen in the same pose. The test rig presented in this paper permits the analysis of the behavior of the knee joint and comparative analysis on the same specimen before and after surgery, in a way to assess the goodness of prostheses or surgical treatments.