1,721,057 research outputs found
A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling
Full text linkWe devise the first constant-approximate feasibility test for sporadic multiprocessor real-time scheduling. We give an algorithm that, given a task system and ε > 0, correctly decides either that the task system can be scheduled using the earliest deadline first algorithm on m speed-(2 - 1/m + ε) machines, or that the system is infeasible for m speed-1 machines. The running time of the algorithm is polynomial in the size of the task system and 1/ε. We also provide an improved bound trading off speed for additional machines. Our analysis relies on a new concept for counting the workload of an interval, that might also turn useful for analyzing other types of task systems. © 2008 Springer-Verlag Berlin Heidelberg
Computing delay resistant railway timetables
No full textIn the past, much research has been dedicated to compute optimum railway timetables. A typical objective has been the minimization of passenger waiting times. But only the planned nominal waiting times have been addressed, whereas delays as they occur in daily operations have been neglected. Delays have been rather treated mainly in an online context and solved as a separate optimization problem, called delay management. We provide the first computational study which aims at computing delay resistant periodic timetables. In particular we assess the delay resistance of a timetable by evaluating it subject to several delay scenarios to which optimum delay management will be applied. We arrive at computing delay resistant timetables by selecting a new objective function which we design to be somehow in the middle of the traditional simple timetabling objective and the sophisticated delay management objective. This is a slight extension of the concept of "light robustness" (LR) as it has been proposed by Fischetti and Monaci [2006. Robust optimization through branch-and-price. In: Proceedings of AIRO]. Moreover, in our application we are able to provide accurate interpretations for the ingredients of LR. We apply this new technique to real-world data of a part of the German railway network of Deutsche Bahn AG. Our computational results suggest that a significant decrease of passenger delays can be obtained at a relatively small price of robustness, i.e. by increasing the nominal travel times of the passengers. (C) 2009 Elsevier Ltd. All rights reserved
Delay-robust event scheduling
No full textRobust optimisation is a well-established concept to deal with uncertainty. In particular, recovery-robust models are suitable for real-world contexts, where a certain amount of recovery—although limited—is often available. In this paper we describe a general framework to optimise event-based problems against delay propagation. We also present a real-world application to train platforming in the Italian railways in order to show the practical effectiveness of our framework
A Constant-Approximate Feasibility Test for Multiprocessor Real-Time Scheduling
No full textWe devise an approximate feasibility test for multiprocessor real-time scheduling in the sporadic task model. We give an algorithm that, given a task system and epsilon > 0, correctly decides either that the task system can be scheduled using the Earliest Deadline First algorithm on m speed-(2-1/m+epsilon) machines, or that the system is not schedulable by any algorithm on m unit speed machines. This speedup bound is known to be the best possible for EDF. The running time of the algorithm is polynomial in the size of the task system and 1/epsilon. We also provide a generalized tight bound that trades off speed with additional machines
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
Recoverable robustness for scheduling with precedence constraints
No full textIn this paper we apply the concept of recoverable robustness by network buffering in a real-world context for the first time. In particular, we consider the problem of assigning trains to platforms in a large railway station, and extend the mathematical formulation of the "nominal'' problem with variables and constraints that allow us to limit the propagation of delays that may occur at some point in the schedule. Our experimental results show that the resulting solutions have the same quality in terms of the nominal objective function, whereas delay propagation is significantly reduced
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
Appropriate Similarity Measures for Author Cocitation Analysis
Full text linkWe provide a number of new insights into the methodological discussion about author cocitation analysis. We first argue that the use of the Pearson correlation for measuring the similarity between authors’ cocitation profiles is not very satisfactory. We then discuss what kind of similarity measures may be used as an alternative to the Pearson correlation. We consider three similarity measures in particular. One is the well-known cosine. The other two similarity measures have not been used before in the bibliometric literature. Finally, we show by means of an example that our findings have a high practical relevance.information science;Pearson correlation;cosine;similarity measure;author cocitation analysis
- …
