| To respond to the increasing market demands for personalized products,the large-scale centralized production mode is gradually replaced by the flexible production mode with small batch and multiple varieties.Manufacturing resources and manufacturing equipment are allocated on demand through a network.The production organization of factories and the supply of raw materials can be scheduled through intelligent logistics and intelligent production management.The order requirement is flexible and diverse,and the equipment combination is complex and changeable.How to respond to these demands quickly,flexibly,and reliably is a major challenge.From the point of view of the discrete event systems(DESs)theory,the scheduling of manufacturing systems is a typical DES scheduling problem.Petri nets can accurately describe choices,synchronizations,parallelisms,and logical specifications of these systems.With the deepening of research on Petri nets,their advantages in modeling,design and analysis of these systems have become more and more obvious.Taking into account the time specification and constraints of the production process,scheduling algorithms are designed based on the time Petri net model and its state space abstraction technology.The main contributions are as follows.1.Based on the time Petri net model of a DES,the state space of the time Petri net model is represented by the timed extended reachability graph(TERG).Furthermore,we combine the filtered beam search algorithm with the heuristic function to dynamically search the TERG for obtaining near-optimal schedules.Compared with other scheduling approaches,the time information of the system is directly encoded in the TERG,which makes the design of the heuristic function simple and direct.Moreover,compared with other searching algorithms,the variant of the filtered beam search algorithm proposed in this thesis has better efficiency and performance.2.A clustering TERG is proposed to simplify the state space of the time Petri net model,and then a global search algorithm is used to directly search this graph to obtain a nearoptimal transition firing sequence corresponding to the near-optimal processing sequence of the system.Since the design of heuristic algorithm greatly depends on a certain production scenario,it is tedious to design efficient heuristic algorithms.By constructing and clustering the states of the approximated TERG,time information about the system is directly reflected on the graph,and the complex design of heuristics is avoided.Such an approach makes it easier to obtain schedules by directly and globally searching the graph of the time Petri net model.3.Considering the delayed firing of transitions in the time Petri net model,we further propose a sampled TERG.In this graph,the delayed firing of transitions is characterized.Specifically,a transition fires after the minimal residual time or before the maximal residual time,and all feasible logical sequences are retained in this graph.In addition,a special case of the sampled TERG,namely extremum TERG,is proposed to reduce the state space and to retain the corresponding feasible timed sequences with minimal and maximal durations for any feasible logical sequence.Therefore,the extremum TERG can be used to accurately calculate the end to end delay for any feasible sequence with respect to any feasible processing sequence of the system. |
