Modelling and control of timed discrete-event systems and its applications to scheduling

This thesis presents anew approach to the scheduling of batch processes based on the optimal control of timed discrete-event systems in the framework of supervisory control theory. The author modifies the model of timed discrete-event systems proposed by Brandin and Wonham and develops finite-state-machine-based models and fast algorithms for construction of optimal supervisors. This framework is applied to modelling and control of batch production lines. The new model and algorithms allow significantly larger problems to be solved than was possible before through the use of the modelling approach proposed by Brandin and Wonham (BW).; The thesis reviews the state-of-the art in both classical and other existing approaches to scheduling. It presents major solution techniques and identifies their main drawbacks. A conclusion is reached that one of the most promising approaches to scheduling seems to be a theory for discreteevent systems. Subsequently a treatment of untimed discrete-event systems (DES) is provided. Based on the basic theory for DES, a simple but expressive modelling approach for batch production lines is proposed. The approach implements a case of a “one-shot” supervisory synthesis. One of the nice features of this approach is the fact that the composition of the automata gives automatically an optimal supervisor for the system. Since this composition is optimal an additional step to find the supremal controllable language is not necessary. In addition, this approach does not require precedence constraints to be modelled explicitly, thus greatly simplifying the modelling process. Precedence constraints are satisfied by an appropriate modelling and choice of the set of synchronization events. The proposed approach is verified on a cluster of different machines for both single- and multi-product cases. The modelling framework constitutes a point of departure for the main topic of this work, namely scheduling of batch processes. Subsequently, a timed model of discrete-event systems is developed. Since this model is based on the BW model the attractive features of the BW model still apply. Our algorithm for the generation of a timed model allows us to solve significantly larger problems than those that can be solved in the basic BW framework. The assignment of time and cost variables to each event allows us to define an optimal control problem. In our framework the frequent problem of finding an optimal production cycle is greatly simplified by detecting all those transitions (uptransitions) that may create cycles. The detection of uptransitions is accomplished without any overhead during the construction of the supervisor. A polynomial-time algorithm for generation of a timed controller with all optimal cycles is provided.; This work was motivated and strongly influenced by a batch plant scheduling environment found in a real industrial environment.