1,720,976 research outputs found
Deterministic estimation of the expected makespan of a POS under duration uncertainty
No full textThis paper is about characterizing the expected makespan of a Partial Order Schedule (POS) under duration uncertainty. Our analysis is based on very general assumptions about the uncertainty: in particular, we assume that only the min, max, and average durations are known. This information is compatible with a whole range of values for the expected makespan.We prove that the largest of these values and the corresponding “worst-case” distribution can be obtained in polynomial time and we present an O(n3) computation algorithm. Then, using theoretical and empirical arguments, we show that such expected makespan is strongly correlated with certain global properties of the POS, and we exploit this correlation to obtain a linear-time estimator. The estimator provides accurate results under a very large variety of POS structures, scheduling problem types, and uncertainty models. The algorithm and the estimator may be used during search by an optimization approach, in particular one based on Constraint Programming: this allows to tackle a stochastic problem by solving a dramatically simpler (and yet accurate) deterministic approximation
The multirate resource constraint
No full textMany real world cyclic scheduling problems involve applications that need to be repeated with different periodicity. For example, multirate control systems present multiple control loops that are organized hierarchically: The higher-level loop responds to the slower system dynamics and typically its period can be a few orders of magnitude longer than the lowest level. Cyclic scheduling problems can be cast into classical RCPSP instances via a technique called unfolding [4,6], which causes graph expansion. In the case of multirate applications, this expansion can be significantly large. In this context, finding a high-quality allocation and schedule could be very challenging. In this paper, we propose a new Multirate Resource Constraint, modeling unary resources, that avoids graph expansion by exploiting the multirate nature of the schedule in its filtering algorithm. In an experimentation on synthetic and real-world instances, we show that our method drastically outperforms approaches based on state-of-the-art unfolding and constraint based scheduling
Swarm-based Traffic Lights Policy Selection
No full textImproving the efficiency of urban vehicular mobility, also via the optimized management of the dynamic behavior of traffic lights with limited infrastructure investments and limited operational costs, is widely recognized as a crucial goal for smart cities, capable of relevant economic impacts in terms of travel time/cost reduction and better sustainability. Within this context, in the framework of the ongoing EU FP7 COLOMBO project, we are investigating, developing, and thoroughly evaluating innovative locality-based vehicular cooperation protocols for the determination of traffic characteristics in proximity of intersections, with no need for communication towards global data collection centers. One of the specific and original goals in COLOMBO is to achieve reasonable and sufficiently accurate traffic estimations with limited penetration rates of actively participating vehicles equipped with differentiated V2X capabilities (full-fledged V2X-enabled cars but also vehicles with only onboard smartphones). In this paper, we specifically focus on our recent research work of implementation and evaluation of our protocols on top of the iTETRIS simulation platform, a state-of-the-art integrated platform resulted from the synergic interworking of the ns-3 network and the SUMO vehicular mobility simulators. In particular, here we originally describe how to effectively and efficiently implement V2X protocols on iTETRIS, as well as lessons learned from our practical experience of deployment, evaluation, and protocol/iTETRIS fine-tuning. The reported simulation results (obtained through realistic simulations based on real traffic traces and the real road topology of the city of Bologna) show the feasibility of the proposed approach also with very limited penetration rates
Embedding Decision Trees and Random Forests in Constraint Programming
No full textAbstract. In past papers, we have introduced Empirical Model Learn-ing (EML) as a method to enable Combinatorial Optimization on real world systems that are impervious to classical modeling approaches. The core idea in EML consists in embedding a Machine Learning model in a traditional combinatorial model. So far, the method has been demon-strated by using Neural Networks and Constraint Programming (CP). In this paper we add one more technique to the EML arsenal, by devising methods to embed Decision Trees (DTs) in CP. In particular, we propose three approaches: 1) a simple encoding based on meta-constraints; 2) a method using attribute discretization and a global table constraint; 3) an approach based on converting a DT into a Multi-valued Decision Di-agram, which is then fed to an mdd constraint. We finally show how to embed in CP a Random Forest, a powerful type of ensemble classifier based on DTs. The proposed methods are compared in an experimental evaluation, highlighting their strengths and their weaknesses.
Going Beyond Counting First Authors in Author Co-citation Analysis
Full text linkThe present study examines one of the fundamental aspects of author co-citation analysis (ACA) - the way co-citation
counts are defined. Co-citation counting provides the data on which all subsequent statistical analyses and mappings
are based, and we compare ACA results based on two different types of co-citation counting - the traditional type that
only counts the first one among a cited work's authors on the one hand and a non-traditional type that takes into
account the first 5 authors of a cited work on the other hand. Results indicate that the picture produced through this non-traditional author co-citation counting contains more coherent author groups and is therefore considerably clearer. However, this picture represents fewer specialties in the research field being studied than that produced through the traditional first-author co-citation counting when the same number of top-ranked authors is selected and analyzed. Reasons for these effects are discussed
Sviluppo di un sistema per allocazione e scheduling di applicazioni periodiche
No full textIn questa tesi, viene illustrato un metodo risolutivo al problema dell’allocazione e schedulazione, su risorse eterogenee con capacità unaria rinnovabile e cumulativa non rinnovabile, di applicazioni multitask periodiche, con periodi in relazione armonica, strutturate in attività indipendenti o sottoposte a vincoli di precedenza e con durate dipendenti dalla specifica risorsa di allocazione.
L’obiettivo è quello di fornire un’implementazione del modello in grado di gestire l’allocazione e la schedulazione di istanze (i.e. insieme di applicazioni) variabili, caratterizzate da una serie di parametri.
La struttura implementativa, realizzata secondo la Logic-based Benders decomposition, prevede la suddivisione del problema in due moduli. Il primo in grado di generare un’allocazione e realizzato con tecniche di programmazione lineare intera mista, il secondo con lo scopo di controllare l’ammissibilità di tale allocazione attraverso una schedulazione ottima e realizzato mediante tecniche di programmazione a vincoli.
Il meccanismo di comunicazione tra i due moduli avviene mediante vincoli lineari, denominati tagli di Benders, che vengono aggiunti dopo ogni iterazione del sistema.
L’efficacia del modello sarà valutata confrontando i risultati ottenuti attraverso una serie di test, con i valori forniti da un metodo di allocazione e schedulazione alternativo
Variations on the Author
Full text link“Variations on the Author” discusses two of Eduardo Coutinho’s recent films (Um Dia na Vida, from 2010, and Últimas Conversas, posthumously released in 2015) and their contribution to the general question of documentary authorship. The director’s filmography is characterized by a consistent yet self-effacing form of authorial self-inscription: Coutinho often features as an interviewer that rather than express opinions propels discourses; an interviewer that is good at listening. This mode of self-inscription characterizes him as an author who is not expressive but who is nonetheless markedly present on the screen. In Um Dia na Vida, however, Coutinho is completely absent form the image, while Últimas Conversas, on the contrary, includes a confessional prologue that moves the director from the margins to the center of his films. This article examines the ways in which these works stand out in the filmography of a director who offers new insights into the notion of cinematic authorship
- …
