Dynamic Dispatching of Cyclic Real-Time Tasks with Relative Timing Constraints

In some hard real-time systems, relative timing constraints may be imposed on task executions, in addition to the release time and deadline constraints. Relative timing constraints such as separation or relative deadline constraints may be given between start or finish times of tasks (Gerber et al., 1995; Han and Lin, 1989; Han et al., 1992; Han and Lin, 1992; Han et al., 1996).One approach in real-time scheduling is to find a total order on a set of N tasks in a scheduling window, and cyclically use this order at run time to execute tasks. However, in the presence of relative timing constraints, if the task execution times are nondeterministic with defined lower and upper bounds, it is not always possible to statically assign task start times at pre-runtime for a given task ordering (Gerber et al., 1995).We develop a technique called dynamic cyclic dispatching as an extension of a parametric dispatching mechanism in (Gerber et al., 1995). An ordered set of N tasks is assumed to be given in a scheduling window and this schedule(ordering) is cyclically repeated at runtime in consecutive scheduling windows. Relative timing constraints between tasks may be defined across scheduling window boundaries as well as within one scheduling window. A task set is defined to be dispatchable if there exists any way in which the tasks can be dispatched with all their timing constraints satisfied. An off-line algorithm is presented to check the dispatchability of a task set and to obtain parametric lower and upper bound functions for task start times if the task set is dispatchable. These parametric bound functions are evaluated at runtime to obtain a valid time interval during which a task can be started. The complexity of this off-line component is shown to be O(n ² N ³) where n is the number of tasks in a scheduling window that have relative timing constraints with tasks in the next scheduling window. An online algorithm can evaluate these bounds in O(N) time.Unlike static approaches which assign fixed start times to tasks in the scheduling window, our approach allows us to flexibly manage the slack times at runtime without sacrificing the dispatchability of tasks. Also, a wider class of relative timing constraints can be imposed to the task set compared to the traditional approaches.     

On satisfying timing constraints in hard-real-time systems

The authors explain why pre-run-time scheduling is essential if one wishes to guarantee that timing constraints will be satisfied in a large complex hard-real-time system. They examine some of the major concerns in pre-run-time scheduling and consider what formulations of mathematical scheduling problems can be used to address those concerns. This work provides a guide to the available algorithms     

Pre-run-time scheduling in real-time systems: Current researches and Artificial Intelligence perspectives

This paper presents the taxonomy of real-time systems with special emphasize on pre-run-time scheduling problem. Firstly, we present real-time systems, real-time tasks, timing, precedence and exclusion constraints. Then, we describe the problem of pre-run-time scheduling of tasks under constraints. After that, we present the most existing efficient techniques to deal with the latter problem. We summarize the discussion of existing techniques and possible research perspectives after surveying the Artificial Intelligence’s point of view about the problem of pre-run-time scheduling of real-time tasks. The Artificial Intelligence survey includes Constraint Satisfaction Problems class since pre-run-time scheduling belongs to the latter class. The Artificial Intelligence survey includes also Path-finding Problems from which intelligent algorithms could be observed such as Learning-Real-Time-A1(LRTA1) thanks to its important properties (optimality, linear space complexity and determinism). The development of an algorithm like LRTA1 to solve Constraints Satisfaction Problems and particularly the pre-run-time scheduling of real-time tasks problem is one clear research direction to deal with large-scale real-time systems. The overall objective of this paper is to show what are the perspectives to Artificial Intelligence literature that could be beneficial firstly to Artificial Intelligence community itself and secondly to real-time systems community.     

An inequality governing nonlinear H∞ control

This note gives necessary and sufficient conditions for solving a reasonable version of the nonlinear H^∞ control problem. The most objectionable hypothesis is elegant and holds in the linear case, but every possibly may not be forced for nonlinear systems. What we discover in distinction to Isidori and Astolfi (1992) and Ball et al. (1993) is that the key formula is not a (nonlinear) Riccati partial differential inequality, but a much more complicated inequality mixing partial derivatives and an approximation theoretic construction called the best approximation operator. This Chebeshev-Riccati inequality when specialized to the linear case gives the famous solution to the H^∞ control problem found in Doyle et al. (1989). While complicated the Chebeshev-Riccati inequality is (modulo a considerable number of hypotheses behind it) a solution to the nonlinear H^∞ control problem. It should serve as a rational basis for discovering new formulas and compromises. We follow the conventions of Ball et al. (1993) and this note adds directly to that paper.     

Toward a comprehensive treatment of temporal constraints about periodic events

In this article, we propose an Allen‐like approach to deal with different types of temporal constraints about periodic events. We consider the different components of such constraints (thus, unlike Allen, we also take into account quantitative constraints) including frame times, user‐defined periods, qualitative temporal constraints, and numeric quantifiers and the interactions between such components. We propose a specialized high‐level formalism to represent temporal constraints about periodic events; temporal reasoning on the formalism is performed by a path‐consistency algorithm repeatedly applying our operations of inversion, intersection, and composition and by a specialized reasoner about periods and numeric quantification. The high‐level formalism has been designed in such a way that different types of temporal constraints about periodic events can be represented in a compact and (hopefully) user‐friendly way and path‐consistency‐based temporal reasoning on the formalism can be performed in polynomial time. We also prove that our definitions of inversion, intersection, and composition and, thus, of our path‐consistency algorithm, are correct. This article also sketches the general architecture of the temporal manager for periodic events (TeMP⁺), that has been designed on the basis of our approach. As a working example, we show an application of our approach to scheduling in a school. © 2003 Wiley Periodicals, Inc.     

A pre-run-time scheduling algorithm for hard real-time systems

Process scheduling, an important issue in the design and maintenance of hard real-time systems, is discussed. A pre-run-time scheduling algorithm that addresses the problem of process sequencing is presented. The algorithm is designed for multiprocessor applications with preemptable processes having release times, computation times, deadlines and arbitrary precedence and exclusion constraints. The algorithm uses a branch-and-bound implicit enumeration technique to generate a feasible schedule for each processor. The set of feasible schedules ensures that the timing specifications of the processes are observed and that all the precedence and exclusion constraints between pairs of processes are satisfied. the algorithm was tested using a model derived from the F-18 mission computer operational flight program     

基于对象分布式实时系统约束的一致性研究

在分布式实时系统中,时间约束规格的一致性是解决任务分配和调度等关键问题的必要前提。该文给出了一种基于对象分布式实时系统调度的通用模型,并对该模型进行了形式化描述。该模型克服了以往模型不能在应用系统的逻辑和功能部件上描述系统实时约束的不足,允许从方法和活动上描述所需的约束,降低了单一约束描述的繁杂程度。为了解决使用该模型进行约束规格的一致性问题,该文给出了绝对时间约束、相对时间约束、一致性约束以及相对时间约束和一致性约束之间的一致性判定的必要条件。     

Three-dimensional shape optimization with variational geometry

The unification of computer aided design (CAD) and the finite element method (FEM) has greatly enhanced the engineer's ability to evaluate potential designs (Finniganet al. 1989). However, analysis alone is not the answer to design, and thus shape optimization methods have become increasingly popular, particularly for structural problems (Yanget al. 1992; Botkin 1992). However, for shape optimization methods to be fully accepted by the engineering community they must first be integrated with CAD systems. To date, the difficulty of integrating CAD and shape optimization is the inability to relate the finite element nodal coordinates to the CAD solid model dimensions. Here, the critical link between these CAD and FEM data is developed within an industry standard feature-based modelling environment. A three-dimensional connecting rod model is optimized to exemplify the method.Also: Department of Theoretical and Applied Mechanics     

Multi-granularity locking for nested transactions

 The choice of granularity for locking items in a database involves performance trade-offs. In order to provide a choice between different locking granularities within a single system, the two-phase locking algorithm needs to be modified to include intention locks. This paper extends the well-known multi-granularity locking algorithm of Gray et al. to deal with nested transactions, and verifies the correctness of the extended algorithm, using a possibilities mapping to abstract commutativity-based locking. Received: June 4, 1993/November 28, 1994     

Fuzzy job shop scheduling problem with availability constraints

This paper presents the fuzzy job shop scheduling problem with availability constraints. The objective is to find a schedule that maximizes the minimum agreement index subject to periodic maintenance, non-resumable jobs and fuzzy due-date. A random key genetic algorithm (RKGA) is proposed for the problem, in which a novel random key representation, a new decoding strategy incorporating maintenance operation and discrete crossover (DX) are used. RKGA is applied to some fuzzy scheduling problem with availability constraints and compared with other algorithms. Computational results show that RKGA performs better than other algorithms.     

On the air damping of flexible microbeam in free space at the free-molecule regime

Predicting air damping is crucial in the design of high Q microelectromechanical systems. In the past, air damping of rigid microbeam in free space at molecular regime is usually estimated using the free molecular model proposed by Christian (Vacuum 16:175–178, 1966), air damping of flexible microbeam is estimated using the model proposed by Blom (J Vac Sci Technol B 10:19–26, 1992). The relation between the two models is Q _Blom = 3Q _Christian. In this paper, a general proof is presented that shows the Christian’s model is valid for the air damping of flexible microbeam in free space at molecular regime. By comparing with the experimental results available in the literatures (Blom et al. in J Vac Sci Technol B 10:19–26, 1992; Yasumura et al. in J Micromech Syst 9:117–125, 2000), we conclude that the Christian’s model is the best choice in predicting the air damping of flexible microbeam in free space at the molecular regime.     

On some applications of ant colony optimization metaheuristic to plane truss optimization

Ant colony optimization metaheuristic (ACO) represents a new class of algorithms particularly suited to solve real-world combinatorial optimization problems. ACO algorithms, published for the first time in 1991 by M. Dorigo [Optimization, learning and natural algorithms (in Italian). Ph.D. Thesis, Dipartimento di Elettronica, Politecnico di Milano, Milan, 1992] and his coworkers, have been applied, particularly starting from 1999 (Bonabeau et al., Swarm intelligence: from natural to artificial systems, Oxford University Press, New York, 1999; Dorigo et al., Artificial life 5(2):137–172, 1999; Dorigo and Di Caro, Ant colony optimization: a new metaheuristic, IEEE Press, Piscataway, NJ, 1999; Dorigo et al., Ant colony optimization and swarm intelligence, Springer, Berlin Heidelberg New York, 2004; Dorigo and Stutzle, Ant colony optimization, MIT Press, Cambridge, MA, 2004), to several kinds of optimization problems such as the traveling salesman problem, quadratic assignment problem, vehicle routing, sequential ordering, scheduling, graph coloring, management of communications networks, and so on. The ant colony optimization metaheuristic takes inspiration from the studies of real ant colonies’ foraging behavior. The main characteristic of such colonies is that individuals have no global knowledge of problem solving but communicate indirectly among themselves, depositing on the ground a chemical substance called pheromone, which influences probabilistically the choice of subsequent ants, which tend to follow paths where the pheromone concentration is higher. Such behavior, called stigmergy, is the basic mechanism that controls ant activity and permits them to take the shortest path connecting their nest to a food source. In this paper, it is shown how to convert natural ant behavior to algorithms able to escape from local minima and find global minimum solutions to constrained combinatorial problems. Some examples on plane trusses are also presented.     

Fair online load balancing

We revisit from a fairness point of view the problem of online load balancing in the restricted assignment model and the 1-∞ model. We consider both a job-centric and a machine-centric view of fairness, as proposed by Goel et al. (In: Symposium on discrete algorithms, pp. 384–390, 2005). These notions are equivalent to the approximate notion of prefix competitiveness proposed by Kleinberg et al. (In: Proceedings of the 40th annual symposium on foundations of computer science, p. 568, 2001), as well as to the notion of approximate majorization, and they generalize the well studied notion of max-min fairness. We resolve a question posed by Goel et al. (In: Symposium on discrete algorithms, pp. 384–390, 2005) proving that the greedy strategy is globally O(log?m)-fair, where m denotes the number of machines. This result improves upon the analysis of Goel et al. (In: Symposium on discrete algorithms, pp. 384–390, 2005) who showed that the greedy strategy is globally O(log?n)-fair, where n is the number of jobs. Typically, n?m, and therefore our improvement is significant. Our proof matches the known lower bound for the problem with respect to the measure of global fairness. The improved bound is obtained by analyzing, in a more accurate way, the more general restricted assignment model studied previously in Azar et al. (J. Algorithms 18:221–237, 1995). We provide an alternative bound which is not worse than the bounds of Azar et al. (J. Algorithms 18:221–237, 1995), and it is strictly better in many cases. The bound we prove is, in fact, much more general and it bounds the load on any prefix of most loaded machines. As a corollary from this more general bound we find that the greedy algorithm results in an assignment that is globally O(log?m)-balanced. The last result generalizes the previous result of Goel et al. (In: Symposium on discrete algorithms, pp. 384–390, 2005) who proved that the greedy algorithm yields an assignment that is globally O(log?m)-balanced for the 1-∞ model.     

Refinement verification of the lazy caching algorithm

The lazy caching algorithm of Afek et al. (ACM Trans. Program. Lang. Syst. 15, 182–206, 1993) is a protocol that allows the use of local caches with delayed updates. It results in a memory model that is not atomic (linearizable) but only sequentially consistent as defined by Lamport. In Distributed Computing 12 (1999), specifying and proving sequential consistency for the lazy caching algorithm was made into a benchmark for verification models. The present note contains such a specification and proof. It provides a simulation from the implementation to the abstract specification. The concrete verification only relies on the state space and the next-state relation. All behavioural aspects are treated in theories independent of the specific algorithm. The proofs of the underlying theories and of the concrete algorithm have been verified with the proof assistant PVS.     

Bicriteria approximation algorithms for scheduling problems with communications delays

We study the problem of simultaneously minimizing the makespan and the average weighted completion time for the precedence multiprocessor constrained scheduling problem with unit execution times and unit communication delays, known as the UET–UCT problem (Munier and König, Operations Research, 45(1), 145–148 (1997)). We propose a simple (16/9, 16/9)-approximation algorithm for the problem with an unrestricted number of machines. We improve our algorithm by adapting a technique first introduced by Aslam et al. (Proceedings of ACM-SODA, pp. 846–847, 1999) and provide a (1.745, 1.745)-approximate solution. For the considered scheduling problem, we prove the existence of a (1.445, 1.445)-approximate solution, improving the generic existence result of Aslam et al. (Proceedings of ACM-SODA, pp. 846–847, 1999). Also notice that our results for the case of an unrestricted number of processors hold for the more general scheduling problem with small communication delays (SCT problem), and for two other classical optimality criteria: maximum lateness and weighted lateness. Finally, we propose an approximation algorithm for the UET–UCT problem with a restricted number of processors.Research partially supported by the thematic network APPOL II (IST 2001-32007) of the European Union, the ACI-GRID2 project of the French government, and the MULT-APPROX project of the France-Berkeley Fund.     

An implicit model for multi-activity shift scheduling problems

We consider a multi-activity shift scheduling problem where the objective is to construct anonymous multi-activity shifts that respect union rules, satisfy the demand and minimize workforce costs. An implicit approach using adapted forward and backward constraints is proposed that integrates both the shift construction and the activity assignment problems. Our computational study shows that using the branch-and-bound procedure of CPLEX 12.6 on the proposed implicit model yields optimal solutions in relatively short times for environments including up to 2970 millions of explicit shifts. Our implicit model is compared to the grammar-based implicit model proposed by Côté et al. (Manag Sci 57(1):151–163, 2011b) on a large set of instances. The results prove that both implicit models have their strengths and weaknesses and are more or less efficient depending on the scheduling environment.     

Complete Bound Consistency for the Global Cardinality Constraint

We show an algorithm for bound consistency of global cardinality constraints, which runs in time O(n + n′) plus the time required to sort the assignment variables by range endpoints, where n is the number of assignment variables and n′ is the number of values in the union of their domains. It is the first efficient algorithm that achieves bound consistency for all variables, and not only the assignment variables.Partially supported by DFG grant SA 933/1-1.Partially supported by the EU IST Programme, IST-1999-14186 (ALCOM-FT).     

Senses and Texts

This paper addresses the question of whether it is possible tosense-tag systematically, and on a large scale, and how we shouldassess progress so far. That is to say, how to attach each occurrenceof a word in a text to one and only one sense in a dictionary – aparticular dictionary of course, and that is part of the problem. Thepaper does not propose a solution to the question, though we havereported empirical findings elsewhere (Cowie et al., 1992;Wilks et al., 1996; Wilks and Stevenson, 1997), and intend to continue andrefine that work. The point of this paper is to examine two well-knowncontributions critically: The first (Kilgarriff, 1993), which is widelytaken to show that the task, as defined, cannot be carried outsystematically by humans and, secondly (Yarowsky, 1995), which claimsstrikingly good results at doing exactly that.     

Online Randomized Multiprocessor Scheduling

The use of randomization in online multiprocessor scheduling is studied. The problem of scheduling independent jobs on m machines online originates with Graham [16]. While the deterministic case of this problem has been studied extensively, little work has been done on the randomized case. For m= 2 a randomized 4/3-competitive algorithm was found by Bartal et al. A randomized algorithm for m ≥ 3 is presented. It achieves competitive ratios of 1.55665, 1.65888, 1.73376, 1.78295, and 1.81681, for m = 3, 4, 5, 6,7 , respectively. These competitive ratios are less than the best deterministic lower bound for m=3,4,5 and less than the best known deterministic competitive ratio for m = 3,4,5,6,7 . Two models of multiprocessor scheduling with rejection are studied. The first is the model of Bartal et al. Two randomized algorithms for this model are presented. The first algorithm performs well for small m , achieving competitive ratios of 3/2 , , for m=2,3,4 , respectively. The second algorithm outperforms the first for m ≥ 5 . It beats the deterministic algorithm of Bartal et al. for all m = 5 ,. . ., 1000 . It is conjectured that this is true for all m . The second model differs in that preemption is allowed. For this model, randomized algorithms are presented which outperform the best deterministic algorithm for small m . Received August 11, 1997; revised February 25, 1998.     

Multiprocessor scheduling of processes with release times,deadlines, precedence, and exclusion relations

The author presents a scheduling algorithm that solves the problem of finding a feasible nonpreemptive schedule whenever one exists on M identical processors for a given set of processes such that each process starts executing after its release time and completes its computation before its deadline. A given set of precedence relations and a given set of exclusion relations defined on ordered pairs of process segments are satisfied. This algorithm can be applied to the important problem of automated pre-run-time scheduling of processes with arbitrary precedence and exclusion relations on multiprocessors in hard-real-time systems