Reachability analysis

An important point is the synchronized execution of the automata Ri, Pi and Ri- They obviously share the same signals/(Ti) and s(T2). In order to ensure correct execution, it is important that both transitions enabled by/(Ti) are taken at the same time. For the same reason, both transitions enabled by s(Ti) must be taken synchronously. Both signals act in this context as synchronization signals. Synchronized transitions share the same synchronization signals and thus must be taken at the same time. Evolutions in which one of them is taken alone are not possible. Note that many implementations of TA support binary synchronizations only. 

Each valid evolution starts in a predefined initial state in which sufficient quantities of the raw materials are given. Furthermore, it must meet the requirements from Section 10.1.3. A schedule will be accepted only if the market demand has been satisfied. Hence, at the end of the evolution, the demanded quantities of final products must be present in the storages. Each evolution which does not satisfy the above requirements leads to an invalid schedule and thus must be rejected. In order to synthesize a valid and optimal schedule, the scheduler has to fix all degrees of freedom by choosing appropriate signals for the resource automata. A valid and optimal schedule corresponds to evolutions which minimize a given optimality criterion. 

The transitions are either time transitions t, f. tn which represent waiting, or discrete transitions S, S, . Sn which correspond to events s(T) and f(T). Each valid schedule is an evolution of A which starts at an initial state qo = (lo, uo, vo) with uo = (0, 0, 0, 0), vo = (20, 0, 0, 0, 0), and ends in a state in which the market demand is satisfied, e.g., q = ((idle, idle, idle, empty), (, , , ), (0, 0, 0, 8, 12)). Note that the number of possible evolutions and the state space of A (a subset of the reachable states q), are infinite. 

In the context of reachability analysis, this graph is called symbolic reachability graph of the automaton A and can be searched using shortest path search techniques as widely used in computer science. Hence, the task of finding the cost-optimal schedule is to find the shortest (or cheapest) path in a (priced) symbolic reachability graph. 

The search starts from the initial state qo. The set W is a data structure which stores symbolic states which are not yet explored. The functionfinal decides whether the given symbolic state is a target state in which the production is completed. The symbolic reachability graph is step-wise constructed by evaluating the successor relation Succ(q), which computes the successor symbolic states of q. The best solution is returned in cost. Existing tools implement numerous extensions of the standard algorithm to improve the efficiency  

---

Scheduling Based on Reachability Analysis of Timed Automata... 

TA are used to model and analyze dynamic systems with discrete and timed behavior. One of their strengths is the easy modeling in a decomposed fashion as a set of often small and individually acting automata. Time in TA is modeled in a very natural way by a set of clocks that simply measure the time between events. This is a major difference to MIP techniques, where time and dynamic components are described in a rather artificial way by providing variables and inequalities for every point of time within a discretized time horizon. In addition to the advantages in modeling, TA serve as a computational model which can be analyzed by techniques for reachability analysis. These techniques are widely used in the context of verification, in which the objective is to detect possible undesired (bad or forbidden) behaviors [9-11]. The success of these techniques was pushed by the availability and increasing performance of tools for TA, e.g., Uppaal [9, 10, 12, 13]. 

A recent and very promising application of the reachability analysis of TA is scheduling. This development, however, required the introduction of the notion of cost. In contrast to the verification of whether a behavior fulfills a specification or not, costs introduce a quantitative measure to evaluate the individual behaviors. Successful applications of priced TA [15, 16] by using the standard and a special version of Uppaal are documented in [17-19]. The first application to deterministic job-shop scheduling was published by Abdeddaim [20] and Abdeddaim and Maler [21], In order to further motivate the use of TA, the next section shows how the schedule in Figure 10.2 and the plant on which the operations are scheduled naturally translate into a set of timed automata. 

Behrmann, G., Larsen, K.G., Pearson, J., et al. (1999) Efficient Timed Reachability Analysis Using Clock Difference Diagrams. Proceedings of CAV 99, Springer, Berlin, pp. 341-353. 

Behrmann, G., Brinksma, E., Hendriks, M. and Mader, A. (2005a) Scheduling Lacquer Production by Reachability Analysis- a Case Study. Proceedings of the 16-th IFAC World Congress. International Federation of Automatic Control, Laxenburg, Austria. 

S. (2004a) Job-Shop Scheduling by Combining Reachability Analysis with Linear Programming. Proceedings of the IFAC... 

Keywords Batch plants, scheduling, timed automata, reachability analysis. 

Recently, the approach to solve scheduling problems by reachability analysis for timed automata has gained great attention. The framework of TA has been originally proposed... 

BDDs, FSMs, Reachability Analysis, Symbolic Breadth-First Traversals, Parallel Computing... 

Although quite successful, symbolic methods cannot complete the reachability analysis of large FSMs, because ... 

G. Cabodi, P. Camurati, and S. Quer. Improved Reachability Analysis of Large Finite State Machine. In Proc. IEEE/ACM ICCAD 96, pages 354-360, San Jose, CA, USA, November 1996. 

A. Narayan, A. J. Isle, J. Jain, R. K. Brayton, and A. Sangiovanni-Vincentelli. Reachability Analysis Using Partitioned-ROBDDs. In Proc. IEEE/ACM IC-CAD 97y San Jose, CA, USA, November 1997. 

Multiway Decision Graphs, Reachability Analysis, Recurrent domains, p-terms... 

In this Section we present an extension of the reachability analysis algorithm that includes the appropriate handling of p-terms. 

---