TestAnt: An ant colony system approach to sequential testing under precedence constraints

We consider the problem of minimum cost sequential testing (diagnosis) of a series (or parallel) system under precedence constraints. We model the problem as a nonlinear integer program. We develop and implement an ant colony algorithm for the problem. We demonstrate the performance of this algorithm for special type of instances for which the optimal solutions can be found in polynomial time. In addition, we compare the performance of the ant colony algorithm with a branch and bound algorithm for randomly generated general instances of the problem. The ant colony algorithm is particularly effective as the problem size gets larger.     

Dynamic scheduling of real-time tasks under precedence constraints

While scheduling theory has been developed over a long period of time, it is important to note that most results concern problems with static characteristics. However, a real-time system is dynamic and requires on-line and adaptive scheduling strategies. So, an important aspect of real-time systems research is to devise methods flexible enough to react to a dynamic change of processor load and to attempt to schedule all the tasks judiciously.In this paper, we are particularly concerned with the problem of scheduling tasks which are of two kinds: periodic and sporadic, on a monoprocessor machine. Periodic tasks are independent, run cyclically and their characteristics are known in advance. In addition, we allow for the unpredictable occurrence of aperiodic task groups, with timing and precedence constraints. Clearly, the main problem is to devise a schedulability test that makes it possible to decide whether a new occurring group can be accepted, without upsetting the tight timing behavior requirements.We present an optimal acceptance test which returns a decision on the basis of the current state of processor load and by considering tasks to be scheduled according to the well known preemptive algorithm Earliest Deadline. The acceptance algorithm and a complexity analysis are presented.     

Optimal release policies for software systems with testing effort

Optimal release policies for software systems are discussed maximizing expected gain and simultaneously achieving a given level of failure intensity incorporating the effect of testing effort expenditure. The software error detection phenomenon in the software testing is modelled by a non-homogeneous Poisson process. Testing effort expenditures sire assumed to be described by testing effort curves. Assuming a particular form for the testing effort curve a numerical example is presented.     

The feasibility of general task systems with precedence constraints on multiprocessor platforms

Feasibility analysis determines (prior to system execution-time) whether a specified collection of hard-real-time jobs executed on a processing platform can meet all deadlines. In this paper, we derive near-optimal sufficient tests for determining whether a given collection of jobs can feasibly meet all deadlines upon a specified multiprocessor platform assuming job migration is permitted. The collection of jobs may contain precedence constraints upon the order of execution of these jobs. The derived tests are general enough to be applied even when the collection of jobs is incompletely specified. We discuss the applicability of these tests to the scheduling of collections of jobs that are generated by systems of recurrent real-time tasks. We also show that our feasibility conditions may be used to obtain global-EDF schedulability conditions.

Output-maximal control policies for cascaded production-inventory systems with control and state constraints

Optimal control policies are derived for cascaded production-inventory systems. As objectives, output maximization and the minimum time to produce a fixed output are considered. An example consisting of three subsystems is detailed to illustrate the proposed theory.     

Stability analysis for linear systems under State constraints

This note revisits the problem of stability analysis for linear systems under state constraints. New and less conservative sufficient conditions are identified under which such systems are globally asymptotically stable. Based on these sufficient conditions, iterative linear matrix inequality (LMI) algorithms are proposed for testing global asymptotic stability of the system. In addition, these iterative LMI algorithms can be adapted for the design of globally stabilizing state feedback gains.     

Tardiness bounds for fixed-priority global scheduling without intra-task precedence constraints

Real-Time Systems - Fixed-priority multiprocessor schedulers are often preferable to dynamic-priority ones because they entail less overhead, are easier to implement, and enable certain tasks to be...     

Local Models for data-driven learning of control policies for complex systems

An approach based on local learning, relying on Nadaraya–Watson models (NWMs), is introduced for the problem of deriving an automatic controller able to exploit data collected during the operation of some complex plant or system by a reference teacher (e.g., a human operator). Such learning approach is particularly useful when the system is too complex to be modeled accurately and/or the task cannot be easily formalized by a cost function, a situation which rules out classic approaches based, e.g., on dynamic programming. Here it is proved that local models are a suitable solution for a real-time employment, since they allow to incorporate new information directly and efficiently without the need of offline training, and new data immediately reflect in improvement of performance. To this purpose, convergence analysis of the method is provided, also considering the case where the reference controller introduces random variations in the training data. Finally, a simulation test, concerning the control of a mechanical system, is provided to showcase the use of local models in an applicative scenario.     

Considerations for automatic testing of complex shipboard systems

An approach for automatically testing complex shipboard systems is developed. After first considering the general system requirements of such a system, the paper considers the advantages and disadvantages associated with automatic testing. Based on these tradeoffs, a technique is developed for automatically testing large complex systems such as that found aboard a ship. The concept considers both hardware and software requirements which will minimize uncertainties associated with automatic testing. The paper concludes with an example of a recent Navy development in the area of centralized shipboard, general-purpose, on-line systems for monitoring and fault isolation—the Test Evaluation and Monitoring System (TEAMS).     

Practical encoders for controlling nonlinear systems under communication constraints

We introduce a new class of dynamic encoders for continuous-time nonlinear control systems which update their parameters only at discrete times. We prove that the information reconstructed from the encoded feedback can be used to deliver a piece-wise constant control law which yields semi-global practical stability.     

Algorithm for synthesis of real-time systems under reliability constraints

The problem of constructing a real-time computing system that has a minimum number of processors is addressed. It is necessary that the system meets the deadlines of program execution and the system reliability requirements implying that the system must tolerate both hardware and software failures. The formal statement of this problem is presented, a method for its solution using an iterative scheduling algorithm based on the method of simulated annealing is proposed, and an experimental study of the proposed algorithm is conducted.     

Exact algorithms for single-machine scheduling with time windows and precedence constraints

We study a single-machine scheduling problem that is a generalization of a number of problems for which computational procedures have already been published. Each job has a processing time, a release date, a due date, a deadline, and a weight representing the penalty per unit-time delay beyond the due date. The goal is to schedule all jobs such that the total weighted tardiness penalty is minimized and both the precedence constraints as well as the time windows (implied by the release dates and the deadlines) are respected. We develop a branch-and-bound algorithm that solves the problem to optimality. Computational results show that our approach is effective in solving medium-sized instances, and that it compares favorably with existing methods for special cases of the problem.     

A bi-objective genetic algorithm for intelligent rehabilitation scheduling considering therapy precedence constraints

The rehabilitation inpatients in hospitals often complain about the service quality due to the long waiting time between the therapeutic processes. To enhance service quality, this study aims to propose an intelligent solution to reduce the waiting time through solving the rehabilitation scheduling problem. In particular, a bi-objective genetic algorithm is developed for rehabilitation scheduling via minimizing the total waiting time and the makespan. The conjunctive therapy concept is employed to preserve the partial precedence constraints between the therapies and thus the present rehabilitation scheduling problem can be formulated as an open shop scheduling problem, in which a special decoding algorithm is designed. We conducted an empirical study based on real data collected in a general hospital for validation. The proposed approach considered both the hospital operational efficiency and the patient centralized service needs. The results have shown that the waiting time of each inpatient can be reduced significantly and thus demonstrated the practical viability of the proposed bi-objective heuristic genetic algorithm.     

Parallel machine scheduling with precedence constraints and setup times

This paper presents different methods for solving parallel machine scheduling problems with precedence constraints and setup times between the jobs. These problems are strongly NP-hard and it is even conjectured that no list scheduling algorithm can be defined without explicitly considering jointly scheduling and resource allocation. We propose dominance conditions based on the analysis of the problem structure and an extension to setup times of the energetic reasoning constraint propagation algorithm. An exact branch-and-bound procedure and a climbing discrepancy search (CDS) heuristic based on these components are defined. We show how the proposed dominance rules can still be valid in the CDS scheme. The proposed methods are evaluated on a set of randomly generated instances and compared with previous results from the literature and those obtained with an efficient commercial solver. We conclude that our propositions are quite competitive and our results even outperform other approaches in most cases.     

On a parallel machine scheduling problem with precedence constraints

We characterize a nontrivial special case with a polynomial-time algorithm for a well-known parallel machine scheduling problem with precedence constraints, with a fixed number of machines, and with tasks of unit length. The special case is related to instances with given maximum path length and maximum degree of the task precedence graph. The method is based on the observation that the number of tasks is either small and bounded by a constant depending on the maximum path length and maximum degree, or alternatively, the number of tasks is large, giving a “dense” schedule.     

Designing parsimonious scheduling policies for complex resource allocation systems through concurrency theory

In a recent work we have proposed a theoretical framework for developing optimized scheduling policies for complex resource allocation systems (RAS). This framework relies heavily on the expression of the RAS dynamics in the modeling framework of the Generalized Stochastic Petri Nets (GSPNs), and the employment of this GSPN-based representation towards the establishment of a systematic trade-off between the representational economy of the target scheduling policies and their operational efficiency. In this paper, we enhance the representational economy of the target policies in the aforementioned framework by taking advantage of some notions of “(non-)conflict” in the transitional dynamics of the underlying RAS-modeling GSPNs. A series of numerical experiments demonstrate that the representational gains resulting from the presented methodology can be very substantial.     

Supervision of networked dynamical systems under coordination constraints

In this paper, we present a discrete-time predictive control strategy for the supervision of networked dynamic systems subject to coordination constraints. Such a network paradigm is characterized by a set of spatially distributed systems, possibly dynamically coupled and connected via communication links, which need to be controlled and coordinated in order to accomplish their overall objective. The network latency is modeled abstractly as a time-varying time-delay, which is allowed to become unbounded for taking into account data-loss. The method can be specialized to deal more efficiently either with random, possibly unbounded, time-delays, such as the case over the Internet, or constant/bounded time-delays, typically encountered in space and underwater applications. An example of coordination of two autonomous vehicles under input-saturation and formation accuracy constraints is presented.     

Decentralized multi-robot allocation of tasks with temporal and precedence constraints

Abstract

We present an auction-based method for a team of robots to allocate and execute tasks that have temporal and precedence constraints. Temporal constraints are expressed as time windows, within which a task must be executed. The robots use our priority-based iterated sequential single-item auction algorithm to allocate tasks among themselves and keep track of their individual schedules. A key innovation is in decoupling precedence constraints from temporal constraints and dealing with them separately. We demonstrate the performance of the allocation method and show how it can be extended to handle failures and delays during task execution. We leverage the power of simulation as a tool to analyze the robustness of schedules. Data collected during simulations are used to compute well-known indexes that measure the risk of delay and failure in the robots’ schedules. We demonstrate the effectiveness of our method in simulation and with real robot experiments.