On real-time scheduling policies for flexible manufacturing systems

The authors consider a model proposed by J.R. Perkins and P.R. Kumar (ibid., vol.34, no.2, pp. 139-148, Feb. 1989) for real-time control of flexible manufacturing systems. In this model, a machine can process a finite number of part types at specified rates, but only one part type can be processed at any given time. To process multiple part types, the machine uses a feedback rule to switch, from time to time, from one part type to another. Such switches incur a setup time of δ time units during which no parts are processed. By introducing the notion of idling, the authors derive a lower bound on the performance, as measured by average buffer size, of any stable feedback scheduling policy for a single machine     

Modechart: a specification language for real-time systems

Present a specification language for real-time systems called Modechart. The semantics of Modechart is given in terms of real-time logic (RTL), which is especially amenable to reasoning about the absolute (real-time clock) timing of events. The semantics of Modechart has an important property that the translation of a Modechart specification into RTL formulas results in a hierarchical organization of the resulting RTL assertions. This gives us significant leverage in reasoning about properties of a system by allowing us to filter out assertions that concern lower levels of abstraction. Some results about desirable properties of Modechart specifications are given. A graphical implementation of Modechart has been completed     

A description language for engineering of complex real-time systems

Typical in modern complex real-time applications are (1) integration of lar ge systems, as well as development of new systems and subsystems, (2) complex, often conflicting, functional and non-functional objectives, and (3) a significant degree of distribution and parallelism. The article takes a particular approach to viewing such applications, and describing them in a new language, called CaRT-Spec. While CaRT-Spec addresses many complex application objectives, the focus of our presentation is on functionality and timeliness, i.e. schedulability.     

Testing real-time systems using genetic algorithms

The development of real-time systems is an essential industrial activity whose importance is increasing. The most important analytical method to assure the quality of real-time systems is dynamic testing. Testing is the only method which examines the actual run-time behaviour of real-time software, based on an execution in the real application environment. Dynamic aspects like the duration of computations, the memory actually needed, or the synchronization of parallel processes are of major importance for the correct function of real-time systems and have to be tested. A comprehensive investigation of existing software test methods shows that they mostly concentrate on testing for functional correctness. They are not suited for an examination of temporal correctness which is essential to real-time systems. Very small systems show a wide range of different execution times. Therefore, existing test procedures must be supplemented by new methods, which concentrate on determining whether the system violates its specified timing constraints. In general, this means that outputs are produced too early or their computation takes too long. The task of the tester is to find the inputs with the longest or shortest execution times to check whether they produce a temporal error. If the search for such inputs is interpreted as a problem of optimization, genetic algorithms can be used to find the inputs with the longest or shortest execution times automatically. The fitness function is the execution time measured in processor cycles. Experiments using genetic algorithms on a number of programs with up to 1511 LOC and 843 integer input parameters have successfully identified new longer and shorter paths than had been found using random testing or systematic testing. Genetic algorithms are able therefore to check large programs and they show considerable promise in establishing the validity of the temporal behaviour of real-time software.     

Modelling flexible manufacturing systems using mean-value analysis

Flexible manufacturing systems (FMS) represent an important new development in automated manufacturing of parts with mid-volume demand. In the design and operation of these complex systems, it is useful to have tools that predict their performance under various conditions. This paper describes one such tool called MVAQ, a computer program based on mean-value analysis of queues. Part production rates, machine utilization and average work-in-process sizes are all easily obtained using MVAQ. The reader is advised on when MVAQ should be used for modelling FMSs and how the program can be used. A simple design example is given to illustrate the use of MVAQ. A brief tutorial on the theory behind MVAQ is also included.     

Real-time Concurrent C: A language for programming dynamic real-time systems

Concurrent C, is a parallel superset of C (and of C++) that provides facilities such as specifying timeouts during process interactions, delaying program execution, accepting messages in a user-specified order, and asynchronous messages that can be used for writing real-time programs. However, Concurrent C does not provide facilities for specifying strict timing constraints, e.g., Concurrent C only ensures that the lower bounds on the specified delay and timeout periods are satisfied. Real-Time Concurrent C extends Concurrent C by providing facilities to specify periodicity or deadline constraints, to seek guarantees that timing constraints will be met, and to perform alternative actions when either the timing constraints cannot be met or the guarantees are not available.In this paper, we will discuss requirements for a real-time programming language, briefly summarize Concurrent C, and motivate and describe the real-time extensions to Concurrent C. We also discuss scheduling and other run-time facilities that have been incorporated to support the real-time extensions. A prototype implementation of Real-Time Concurrent C is nearing completion.     

Scenario-based verification of real-time systems using Uppaal

This article proposes two approaches to tool-supported automatic verification of dense real-time systems against scenario-based requirements, where a system is modeled as a network of timed automata (TAs) or as a set of driving live sequence charts (LSCs), and a requirement is specified as a separate monitored LSC chart. We make timed extensions to a kernel subset of the LSC language and define a trace-based semantics. By translating a monitored LSC chart to a behavior-equivalent observer TA and then non-intrusively composing this observer with the original TA-modeled real-time system, the problems of scenario-based verification reduce to computation tree logic (CTL) real-time model checking problems. When the real-time system is modeled as a set of driving LSC charts, we translate these driving charts and the monitored chart into a behavior-equivalent network of TAs by using a “one-TA-per-instance line” approach, and then reduce the problems of scenario-based verification also to CTL real-time model checking problems. We show how we exploit the expressivity of the TA formalism and the CTL query language of the real-time model checker Uppaal to accomplish these tasks. The proposed two approaches are implemented in the Uppaal tool and built as a tool chain, respectively. We carry out a number of experiments with both verification approaches, and the results indicate that these methods are viable, computationally feasible, and the tools are effective.     

Optimal distributed real-time scheduling of flexible manufacturing networks modeled as hybrid dynamical systems

The paper considers a class of flexible manufacturing networks. We employ hybrid dynamical systems to model such networks. The main and new achievement of the paper is that we propose a distributed implementable in real time scheduling rule such that the corresponding closed-loop system is stable and optimal. In stable systems the processes converge to periodic ones. The paper gives computing relations for the determination of the parameters of the periodic processes. These are very much suitable for planning purposes. On this basis—and this, we consider, is also a new, significant result—optimal arrival (demand) rates determination method is proposed. Quality characteristics are outlined. Field of application of hybrid dynamical approach for FMS scheduling is analyzed. The results open perspectives for MRP level task planning. Example and simulation results are presented.     

A flexible environment for rapid prototyping and analysis of distributed real-time safety-critical systems

Currently, there is a plethora of low-cost commercial off-the-shelf (COTS) hardware available for implementing control systems. These range from devices with fairly low intelligence, e.g. smart sensors and actuators, to dedicated controllers such as PowerPC, programmable logic controllers (PLCs) and PC-based boards to dedicated systems-on-a-chip (SoC) ASICS and FPGAs. When considering the construction of complex distributed systems, e.g. for a ship, aircraft, car, train, process plant, the ability to rapidly integrate a variety of devices from different manufacturers is essential. A problem, however, is that manufacturers prefer to supply proprietary tools for programming their products. As a consequence of this lack of ‘openness’, rapid prototyping and development of distributed systems is extremely difficult and costly for a systems integrator. Great opportunities thus exist to produce high-performance, dependable distributed systems. However, the key element that is missing is software tool support for systems integration. The objective of the Flexible Control Systems Development and Integration Environment for Control Systems (FLEXICON) project IST-2001-37269 is to solve these problems for industry and reduce development and implementation costs for distributed control systems by providing an integrated suite of tools to support all the development life-cycle of the system. Work within the Rolls-Royce supported University Technology Centre (UTC) is investigating rapid prototyping of controllers for aero-engines, unmanned aerial vehicles and ships. This paper describes the use of the developed co-simulation environment for a high-speed merchant vessel propulsion system application.     

Hard real-time multibody simulations using ARM-based embedded systems

The real-time simulation of multibody models on embedded systems is of particular interest for controllers and observers such as model predictive controllers and state observers, which rely on a dynamic model of the process and are customarily executed in electronic control units. This work first identifies the software techniques and tools required to easily write efficient code for multibody models to be simulated on ARM-based embedded systems. Automatic Programming and Source Code Translation are the two techniques that were chosen to generate source code for multibody models in different programming languages. Automatic Programming is used to generate procedural code in an intermediate representation from an object-oriented library and Source Code Translation is used to translate the intermediate representation automatically to an interpreted language or to a compiled language for efficiency purposes. An implementation of these techniques is proposed. It is based on a Python template engine and AST tree walkers for Source Code Generation and on a model-driven translator for the Source Code Translation. The code is translated from a metalanguage to any of the following four programming languages: Python-Numpy, Matlab, C++-Armadillo, C++-Eigen. Two examples of multibody models were simulated: a four-bar linkage with multiple loops and a 3D vehicle steering system. The code for these examples has been generated and executed on two ARM-based single-board computers. Using compiled languages, both models could be simulated faster than real-time despite the low resources and performance of these embedded systems. Finally, the real-time performance of both models was evaluated when executed in hard real-time on Xenomai for both embedded systems. This work shows through measurements that Automatic Programming and Source Code Translation are valuable techniques to develop real-time multibody models to be used in embedded observers and controllers.     

Debugging measurement systems using a domain-specific modeling language

Capturing physical data in the context of measurement systems is a demanding process that often requires many repetitions with different settings. To assist in this activity, a domain-specific modeling language (DSML) called Sequencer has been developed to enable the improved definition of measurement procedures. With Sequencer, the level of abstraction has been raised and sophisticated changes in measurement procedures are now enabled. Although there are numerous DSMLs like Sequencer in the existing literature, there are some obstacles working against the more widespread adoption of DSMLs in practice. One challenge is the lack of supporting tools for DSMLs, which would improve the capabilities of end-users of such languages. For instance, support for debugging a model expressed in a DSML is often neglected. The lack of a debugger at the proper abstraction level limits the domain experts in discovering and locating bugs in a model. In this paper, Sequencer is presented together with debugging facilities (called Ladybird) that are integrated in a modeling environment. Ladybird supports different execution modes (e.g., steps, breakpoints, animations, variable views, and stack traces) that can be helpful during the debugging of a model. Ladybird's primary contribution is in showing the value of error detection in complicated industrial environments, such as data acquisition in automotive testing. The paper contributes to a discussion of the implementation details of DSML debugging facilities and how such a debugger can be reused to support domains other than the measurement context of Sequencer.     

An object-oriented real-time programming language

The real-time object model, an extended object-oriented model for describing real-time systems, is described. The design and implementation of RTC++, a programming language that extends C++ on the basis of the real-time object model, are discussed. The schedulability analysis and specification of rigid timing constraints in systems with active objects are reviewed     

Learning-based scheduling of flexible manufacturing systems using case-based reasoning

A common method of dynamically scheduling jobs in Flexible Manufacturing Systems (FMSs) is to employ dispatching rules. However, the problem associated with this method is that the performance of the rules depends on the state of the system, but there is no rule that is superior to all the others for all the possible states the system might be in. It would therefore be highly desirable to employ the most suitable rule for each particular situation. To achieve this, this paper presents a scheduling approach that uses Case-Based Reasoning (CBR), which analyzes the system's previous performance and acquires "scheduling knowledge," which determines the most suitable dispatching rule at each particular moment in time. Simulation results indicate that the proposed approach produces significant performance improvements over existing dispatching rules.     

Reachability analysis of real-time systems using time Petri nets

Time Petri nets (TPNs) are a popular Petri net model for specification and verification of real-time systems. A fundamental and most widely applied method for analyzing Petri nets is reachability analysis. The existing technique for reachability analysis of TPNs, however, is not suitable for timing property verification because one cannot derive end-to-end delay in task execution, an important issue for time-critical systems, from the reachability tree constructed using the technique. In this paper, we present a new reachability based analysis technique for TPNs for timing property analysis and verification that effectively addresses the problem. Our technique is based on a concept called clock-stamped state class (CS-class). With the reachability tree generated based on CS-classes, we can directly compute the end-to-end time delay in task execution. Moreover, a CS-class can be uniquely mapped to a traditional state class based on which the conventional reachability tree is constructed. Therefore, our CS-class-based analysis technique is more general than the existing technique. We show how to apply this technique to timing property verification of the TPN model of a command and control (C2) system.     

Synthesizing structures of real-time computer systems using genetic algorithms

A genetic algorithm is suggested for synthesizing real-time computer systems. The emphasis is on adjusting the algorithm to specific features of the problem and justifying the decisions made. Results of the analysis of the algorithm are also presented. Parameters of the genetic algorithm that provide good solutions are chosen by using a computational experiment.     

Integrated scheduling of resource-constrained flexible manufacturing systems using constraint programming

This contribution presents a novel approach to address the scheduling of resource-constrained flexible manufacturing systems (FMSs). It deals with several critical features that are present in many FMS environments in an integrated way. The proposal consists in a constraint programming (CP) formulation that simultaneously takes into account the following sub-problems: (i) machine loading, (ii) manufacturing activities scheduling, (iii) part routing, (iv) machine buffer scheduling, (v) tool planning and allocation, and (vi) AGV scheduling, considering both the loaded and the empty movements of the device. Before introducing the model, this work points out the problems that might appear when all these issues are not concurrently taken into account. Then, the FMS scheduling model is presented and later assessed through several case-studies. The proposed CP approach has been tested by resorting to problems that consider dissimilar number of parts, operations per part, and tool copies, as well as different AGV speeds. The various examples demonstrate the importance of having an integrated formulation and show the important errors that can occur when critical issues such as AGV empty movements are neglected.     

Monitoring of flexible production systems using high-level Petri net specifications

The degree of reliability in the operation of flexible production systems depends not only on the operation of the individual components, but also on the structure and evolution of the embedded supervisory control system. Monitoring of operations and of the behaviour of the components and of the system as a whole is an essential function of such a supervisory control system. This paper focuses on the development and implementation of feature- and model-based monitoring methods using high-level Petri net specifications of flexible production systems and of the embedded discrete-event controllers. The combination of machine–human interface concepts with the developed monitoring methods leads to a user-friendly representation of monitoring information. An application at industrial level is shown by means of a case study, i.e., a sample flexible assembly cell, situated at the Institute for Manufacturing Automation and Production Systems, Germany.