Hybrid Methods for Resource Allocation and Scheduling Problems in Deterministic and Stochastic Environments

This work presents exact, hybrid algorithms for mixed resource Allocation and Scheduling problems; in general terms, those consist into assigning over time finite capacity resources to a set of precedence connected activities. The proposed methods have broad applicability, but are mainly motivated by applications in the field of Embedded System Design. In particular, high-performance embedded computing recently witnessed the shift from single CPU platforms with application-specific accelerators to programmable Multi Processor Systems-on-Chip (MPSoCs). Those allow higher flexibility, real time performance and low energy consumption, but the programmer must be able to effectively exploit the platform parallelism. This raises interest in the development of algorithmic techniques to be embedded in CAD tools; in particular, given a specific application and platform, the objective if to perform optimal allocation of hardware resources and to compute an execution schedule. On this regard, since embedded systems tend to run the same set of applications for their entire lifetime, off-line, exact optimization approaches are particularly appealing. Quite surprisingly, the use of exact algorithms has not been well investigated so far; this is in part motivated by the complexity of integrated allocation and scheduling, setting tough challenges for ``pure'' combinatorial methods. The use of hybrid CP/OR approaches presents the opportunity to exploit mutual advantages of different methods, while compensating for their weaknesses. In this work, we consider in first instance an Allocation and Scheduling problem over the Cell BE processor by Sony, IBM and Toshiba; we propose three different solution methods, leveraging decomposition, cut generation and heuristic guided search. Next, we face Allocation and Scheduling of so-called Conditional Task Graphs, explicitly accounting for branches with outcome not known at design time; we extend the CP scheduling framework to effectively deal with the introduced stochastic elements. Finally, we address Allocation and Scheduling with uncertain, bounded execution times, via conflict based tree search; we introduce a simple and flexible time model to take into account duration variability and provide an efficient conflict detection method. The proposed approaches achieve good results on practical size problem, thus demonstrating the use of exact approaches for system design is feasible. Furthermore, the developed techniques bring significant contributions to combinatorial optimization methods.

Development and application of a thermo-hydraulic model supporting the design and the deterministic safety analysis in a sodium cooled fast reactor

Il CP-ESFR è un progetto integrato di cooperazione europeo sui reattori a sodio SFR realizzato sotto il programma quadro EURATOM 7, che unisce il contributo di venticinque partner europei. Il CP-ESFR ha l'ambizione di contribuire all'istituzione di una "solida base scientifica e tecnica per il reattore veloce refrigerato a sodio, al fine di accelerare gli sviluppi pratici per la gestione sicura dei rifiuti radioattivi a lunga vita, per migliorare le prestazioni di sicurezza, l'efficienza delle risorse e il costo-efficacia di energia nucleare al fine di garantire un sistema solido e socialmente accettabile di protezione della popolazione e dell'ambiente contro gli effetti delle radiazioni ionizzanti. " La presente tesi di laurea è un contributo allo sviluppo di modelli e metodi, basati sull’uso di codici termo-idraulici di sistema, per l’ analisi di sicurezza di reattori di IV Generazione refrigerati a metallo liquido. L'attività è stata svolta nell'ambito del progetto FP-7 PELGRIMM ed in sinergia con l’Accordo di Programma MSE-ENEA(PAR-2013). Il progetto FP7 PELGRIMM ha come obbiettivo lo sviluppo di combustibili contenenti attinidi minori 1. attraverso lo studio di due diverse forme: pellet (oggetto della presente tesi) e spherepac 2. valutandone l’impatto sul progetto del reattore CP-ESFR. La tesi propone lo sviluppo di un modello termoidraulico di sistema dei circuiti primario e intermedio del reattore con il codice RELAP5-3D© (INL, US). Tale codice, qualificato per il licenziamento dei reattori nucleari ad acqua, è stato utilizzato per valutare come variano i parametri del core del reattore rilevanti per la sicurezza (es. temperatura di camicia e di centro combustibile, temperatura del fluido refrigerante, etc.), quando il combustibile venga impiegato per “bruciare” gli attinidi minori (isotopi radioattivi a lunga vita contenuti nelle scorie nucleari). Questo ha comportato, una fase di training sul codice, sui suoi modelli e sulle sue capacità. Successivamente, lo sviluppo della nodalizzazione dell’impianto CP-ESFR, la sua qualifica, e l’analisi dei risultati ottenuti al variare della configurazione del core, del bruciamento e del tipo di combustibile impiegato (i.e. diverso arricchimento di attinidi minori). Il testo è suddiviso in sei sezioni. La prima fornisce un’introduzione allo sviluppo tecnologico dei reattori veloci, evidenzia l’ambito in cui è stata svolta questa tesi e ne definisce obbiettivi e struttura. Nella seconda sezione, viene descritto l’impianto del CP-ESFR con attenzione alla configurazione del nocciolo e al sistema primario. La terza sezione introduce il codice di sistema termico-idraulico utilizzato per le analisi e il modello sviluppato per riprodurre l’impianto. Nella sezione quattro vengono descritti: i test e le verifiche effettuate per valutare le prestazioni del modello, la qualifica della nodalizzazione, i principali modelli e le correlazioni più rilevanti per la simulazione e le configurazioni del core considerate per l’analisi dei risultati. I risultati ottenuti relativamente ai parametri di sicurezza del nocciolo in condizioni di normale funzionamento e per un transitorio selezionato sono descritti nella quinta sezione. Infine, sono riportate le conclusioni dell’attività.

Forbidden ordinal patterns of periictal intracranial EEG indicate deterministic dynamics in human epileptic seizures

Epileptic seizures typically reveal a high degree of stereotypy, that is, for an individual patient they are characterized by an ordered and predictable sequence of symptoms and signs with typically little variability. Stereotypy implies that ictal neuronal dynamics might have deterministic characteristics, presumably most pronounced in the ictogenic parts of the brain, which may provide diagnostically and therapeutically important information. Therefore the goal of our study was to search for indications of determinism in periictal intracranial electroencephalography (EEG) studies recorded from patients with pharmacoresistent epilepsy.

Stress parameters and behaviour of horses in walkers with and without the use of electricity

In order to investigate stress responses of horses in walkers with and without electricity, 12 horses were trained during 3 weeks in a horse walker with and without the use of electricity (3.7 kV). To evaluate the stress response, cortisol levels in the blood were measured, the heart rate was monitored using the Polar® system and the behaviour was evaluated. Neither the cortisol levels nor the heart rates showed any relevant statistically significant difference between horses moved in the horse walker with or without the use of electricity. The highest cortisol levels and heart rates were recorded during the first week (habituation period). A significant difference could be observed regarding spontaneous compartment changes: while this happened mainly during the first week and before the first use of electricity, no horses changed compartments in the periods when electricity was used and thereafter. The results of this study indicate that the use of electricity in the horse walker does not seem to cause significant detectable stress in the horses.

Flexible scheduling for non-deterministic, and-parallel execution of logic programs

Abstract is not available.

A contribution to the deterministic modelling of circadian rhythms in cell proliferation activity

This paper presents a deterministic continuous model of proliferative cell activity. The classical series of connected compartments is revisited along with a simple mathematical treatment of two hypotheses: constant transit times and harmonic Ts. Several examples are presented to support these ideas, both taken from previous literature and recent experiences with the fish Carassius auratus, developed at the Junta de Energía Nuclear, Madrid, Spain.

A proposal for a flexible scheduling and memory management scheme for non-deterministic, andparallel execution of logic programs

In this paper, we examine the issue of memory management in the parallel execution of logic programs. We concentrate on non-deterministic and-parallel schemes which we believe present a relatively general set of problems to be solved, including most of those encountered in the memory management of or-parallel systems. We present a distributed stack memory management model which allows flexible scheduling of goals. Previously proposed models (based on the "Marker model") are lacking in that they impose restrictions on the selection of goals to be executed or they may require consume a large amount of virtual memory. This paper first presents results which imply that the above mentioned shortcomings can have significant performance impacts. An extension of the Marker Model is then proposed which allows flexible scheduling of goals while keeping (virtual) memory consumption down. Measurements are presented which show the advantage of this solution. Methods for handling forward and backward execution, cut and roll back are discussed in the context of the proposed scheme. In addition, the paper shows how the same mechanism for flexible scheduling can be applied to allow the efficient handling of the very general form of suspension that can occur in systems which combine several types of and-parallelism and more sophisticated methods of executing logic programs. We believe that the results are applicable to many and- and or-parallel systems.

Bounded non-deterministic planning for multimedia adaptation

This paper proposes a novel combination of artificial intelligence planning and other techniques for improving decision-making in the context of multi-step multimedia content adaptation. In particular, it describes a method that allows decision-making (selecting the adaptation to perform) in situations where third-party pluggable multimedia conversion modules are involved and the multimedia adaptation planner does not know their exact adaptation capabilities. In this approach, the multimedia adaptation planner module is only responsible for a part of the required decisions; the pluggable modules make additional decisions based on different criteria. We demonstrate that partial decision-making is not only attainable, but also introduces advantages with respect to a system in which these conversion modules are not capable of providing additional decisions. This means that transferring decisions from the multi-step multimedia adaptation planner to the pluggable conversion modules increases the flexibility of the adaptation. Moreover, by allowing conversion modules to be only partially described, the range of problems that these modules can address increases, while significantly decreasing both the description length of the adaptation capabilities and the planning decision time. Finally, we specify the conditions under which knowing the partial adaptation capabilities of a set of conversion modules will be enough to compute a proper adaptation plan.

Integrated deterministic-probabilistic safety assessment methodologies

(ENG) IDPSA (Integrated Deterministic-Probabilistic Safety Assessment) is a family of methods which use tightly coupled probabilistic and deterministic approaches to address respective sources of uncertainties, enabling Risk informed decision making in a consistent manner. The starting point of the IDPSA framework is that safety justification must be based on the coupling of deterministic (consequences) and probabilistic (frequency) considerations to address the mutual interactions between stochastic disturbances (e.g. failures of the equipment, human actions, stochastic physical phenomena) and deterministic response of the plant (i.e. transients). This paper gives a general overview of some IDPSA methods as well as some possible applications to PWR safety analyses (SPA)DPSA (Metodologías Integradas de Análisis Determinista-Probabilista de Seguridad) es un conjunto de métodos que utilizan métodos probabilistas y deterministas estrechamente acoplados para abordar las respectivas fuentes de incertidumbre, permitiendo la toma de decisiones Informada por el Riesgo de forma consistente. El punto de inicio del marco IDPSA es que la justificación de seguridad debe estar basada en el acoplamiento entre consideraciones deterministas (consecuencias) y probabilistas (frecuencia) para abordar la interacción mutua entre perturbaciones estocásticas (como por ejemplo fallos de los equipos, acciones humanas, fenómenos físicos estocásticos) y la respuesta determinista de la planta (como por ejemplo los transitorios). Este artículo da una visión general de algunos métodos IDSPA así como posibles aplicaciones al análisis de seguridad de los PWR.

The evolution of mass tourism destinations: new approaches beyond deterministic models in Benidorm (Spain)

Although deterministic models of the evolution of mass tourism coastal resorts predict an almost inevitable decline over time, theoretical frameworks of the evolution and restructuring policies of mature destinations should be revised to reflect the complex and dynamic way in which these destinations evolve and interact with the tourism market and global socio-economic environment. The present study examines Benidorm because its urban and tourism model and large-scale tourism supply and demand make it one of the most unique destinations on the Mediterranean coast. The investigation reveals the need to adopt theories and models that are not purely deterministic. The dialectic interplay between external factors and the internal factors inherent in this destination simultaneously reveals a complex and diverse stage of maturity and the ability of destinations to create their own future.

Deterministic mathematical morphology for CAD/CAM

Purpose – The purpose of this paper is to present a new geometric model based on the mathematical morphology paradigm, specialized to provide determinism to the classic morphological operations. The determinism is needed to model dynamic processes that require an order of application, as is the case for designing and manufacturing objects in CAD/CAM environments. Design/methodology/approach – The basic trajectory-based operation is the basis of the proposed morphological specialization. This operation allows the definition of morphological operators that obtain sequentially ordered sets of points from the boundary of the target objects, inexistent determinism in the classical morphological paradigm. From this basic operation, the complete set of morphological operators is redefined, incorporating the concept of boundary and determinism: trajectory-based erosion and dilation, and other morphological filtering operations. Findings – This new morphological framework allows the definition of complex three-dimensional objects, providing arithmetical support to generating machining trajectories, one of the most complex problems currently occurring in CAD/CAM. Originality/value – The model proposes the integration of the processes of design and manufacture, so that it avoids the problems of accuracy and integrity that present other classic geometric models that divide these processes in two phases. Furthermore, the morphological operative is based on points sets, so the geometric data structures and the operations are intrinsically simple and efficient. Another important value that no excessive computational resources are needed, because only the points in the boundary are processed.

The automatic generation of deterministic parsing algorithms /

ILIAC IV document no. 248

A deterministic procedure for the design of carry-save adders and borrow-save subtracters /

"To be presented at the First Annual IEEE Computer Conference, Chicago, Illinois, September 6-8, 1967."