Modeling and scheduling of ratio-driven FMS using unfolding time Petri nets

In this paper, we focus on the analysis of a cyclic schedule for the determination of the optimal cycle time and minimization of the Work in Process (WIP for short). Especially, this paper deals with product ratio-driven FMS cyclic scheduling problem with each other products and ratios using Timed Petri nets unfolding (TPN for short). TPN slicing and unfolding are applied to analyze this FMS model. We can divide original system into subsystem using TPN slices and change iterated cycle module into acyclic module without any loss of other behavior properties.     

Hybrid heuristic search approach for deadlock-free scheduling of flexible manufacturing systems using Petri nets

Based on the Petri net models of flexible manufacturing systems (FMSs), this paper focuses on deadlock-free scheduling problem with the objective of minimizing the makespan. Two hybrid heuristic search algorithms for solving such scheduling problems of FMSs are proposed. To avoid deadlocks, the deadlock control policy is embedded into heuristic search strategies. The proposed algorithms combine the heuristic best-first strategy with the controlled backtracking strategy based on the execution of the Petri nets. The scheduling problem is transformed into a heuristic search problem in the reachability graph of the Petri net, and a schedule is a transition sequence from the initial marking to the final marking in the reachability graph. By using the one-step look-ahead method in the deadlock control policy, the safety of a state in the reachability graph is checked, and hence, deadlock is avoided. Experimental results are provided and indicate the effectiveness of the proposed hybrid heuristic search algorithms in solving deadlock-free scheduling problems of FMSs. Especially, the comparison against previous work shows that both new algorithms are promising in terms of solution quality and computing times.     

Real-time scheduling of batch systems using Petri nets and linear logic

This paper presents an approach to model, design and verify scenarios of real-time systems used in the scheduling and global coordination of batch systems. The initial requirements of a system specified with sequence diagrams are translated into a single p-time Petri net model representing the global behavior of the system. For the Petri net fragments involved in conflicts, symbolic production and consumption dates assigned to tokens are calculated based on the sequent calculus of linear logic. These dates are then used for off-line conflict resolution within a token player algorithm used for scenario verification of real-time specifications and which can be seen as a simulation tool for UML interaction diagrams.     

Real time identification of discrete event systems using Petri nets

The paper defines the identification problem for Discrete Event Systems (DES) as the problem of inferring a Petri Net () model using the observation of the events and the available output vectors, that correspond to the markings of the measurable places. Two cases are studied considering different levels of the system knowledge. In the first case the place and transition sets are assumed known. Hence, an integer linear programming problem is defined in order to determine a modelling the DES. In the second case the transition and place sets are assumed unknown and only an upper bound of the number of places is given. Hence, the identification problem is solved by an identification algorithm that observes in real time the occurred events and the corresponding output vectors. The integer linear programming problem is defined at each observation so that the can be recursively identified. Some results and examples characterize the identified systems and show the flexibility and simplicity of the proposed technique. Moreover, an application to the synthesis of supervisory control of systems via monitor places is proposed.     

Synthesis of deadlock prevention policy using Petri nets reachability graph technique

This paper proposes a subclass of generalized stochastic Petri net (GSPN) model, called TS³PR, which is modified the systems of simple sequential processes with resources (S³PR) with timed information. Based on the subclass of GSPN, a new deadlock prevention policy is developed by using reachability graph technique. The foundation of the new control policy is to manipulate all the dead states of the system nets. This study is able to change dead states into vanishing ones by additional immediate transitions. A live TS³PR model can then be obtained. It is worthwhile to notice that this study is different from adding additional control place policies in previous literature. Experimental results, indicate that our new control policy is with maximally permissive markings than conventional place‐control ones. As a result, we can infer that our proposed control policy seems to be used in Petri nets deadlocked systems. To our knowledge, this is the first work that employs the additional transitions to obtain the deadlock prevention policy. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

A method of workflow scheduling based on colored Petri nets

Effective methods of workflow scheduling can improve the performance of workflow systems. Based on the study of existing scheduling methods, a method of workflow scheduling, called phased method, is proposed. This method is based on colored Petri nets. Activities of workflows are divided into several groups to be scheduled in different phases using this method. Details of the method are discussed. Experimental results show that the proposed method can deal with the uncertainties and the dynamic circumstances very well and a satisfactory balance can be achieved between static global optimization and dynamic local optimization.     

Petri net based process scheduling: A model of the control system of flexible manufacturing systems

In this paper, we propose a class of algorithms for the sub-optimal solution of a particular class of problems of process scheduling, particularly focusing on a case study in the area of flexible manufacturing systems (FMSs). The general class of problems we face in our approach is characterized as follows: there is a set of concurrent processes, each formed by a number of temporally related tasks (segments). Tasks are executable by alternate resource sets, different both in performance and costs. Processes and tasks are characterized by release times, due dates, and deadlines. Time constraints are also present in the availability of each resource in resource sets. It has been proven that such a problem does not admit an algorithm for an optimal solution in polynomial time. Our proposed algorithm finds a sub-optimal schedule according to a set of optimization criteria, based on task and process times (earliness, tardiness), and/or time independent costs of resources. Our approach to process scheduling is based on Timed Coloured Petri Nets. We describe the structure of the coordination and scheduling algorithms, concentrating on (i) the general-purpose component, and (ii) the application-dependent component. In particular, the paper focuses on the following issues: (i) theautomatic synthesis of Petri net models of the coordination subsystem, starting from the problem knowledge base; (ii) the dynamic behavior of the coordination subsystem, whose kernel is a High Level Petri net executor, a coordination process based on an original, general purpose algorithm; (iii) the structure of the real-time scheduling subsystem, based on particular heuristic sub-optimal multi-criteria algorithms. Furthermore, the paper defines the interaction mechanisms between the coordination and scheduling subsystems. Our approach clearly distinguishes the mechanism of the net execution from the decision support system. Two conceptually distinct levels, which correspond to two different, interacting implementation modules in the prototype CASE tool, have been defined: theexecutor and thescheduler levels. One of the outstanding differences between these levels is that the executor is conceived as a fast, efficient coordination process, without special-purpose problem-solving capabilities in case of conflicts. The scheduler, on the other hand, is the adaptive, distributed component, whose behavior may heavily depend on the problem class. If the scheduler fails, the executor is, in any case, able to proceed with a general-purpose conflict resolution strategy. Experimental results on the real-time performance of the kernel of the implemented system are finally shown in the paper. The approach described in this paper is at the basis of a joint project with industrial partners for the development of a CASE tool for the simulation of blast furnaces.     

Suboptimal liveness-enforcing supervisor design for a class of generalised Petri nets using partial siphon enumeration and mathematical programming

This article develops a deadlock prevention policy for a class of generalised Petri nets, which can well model a large class of flexible manufacturing systems. The analysis of such a system leads us to characterise the deadlock situations in terms of the insufficiently marked siphons in its generalised Petri-net model. The proposed policy is carried out in an iterative way. At each step a minimal siphon is derived from a maximal deadly marked siphon that is found by solving a mixed integer programming (MIP) problem. An algorithm is formalised that can efficiently compute such a minimal siphon from a maximal one. A monitor is added for a derived minimal siphon such that it is max-controlled if it is elementary with respect to the siphons that have been derived. The liveness of the controlled system is decided by the fact that no siphon can be derived due to the MIP solution. After a liveness-enforcing net supervisor computed without complete siphon enumeration, the output-arcs of the additional monitors are rearranged such that the monitors act while restricting the system less. Examples are presented to demonstrate the proposed method.     

柔性作业车间调度分析及其启发式算法

针对多目标柔性作业车间调度问题,基于甘特图和搭积木经验进行了分析,提出了一种组合优先规则和基于此优先规则的启发式算法。组合优先规则面向完工时间、关键机床负荷和总负荷三个指标,改变规则中各数据项的比例可调整三个指标所占的比例。算法采用随机方式调整三个指标的比例,并微调最优解对应的比例,能随机产生多个高质量调度解。对比测试表明,算法求解质量更高,运行速度快,稳定,可直接用于在其他调度算法中产生初始解,或者用于动态调度。     

Deadlock-free scheduling for flexible manufacturing systems using Petri nets and heuristic search

Deadlock-free control and scheduling are two different problems for flexible manufacturing systems (FMSs). They are significant for improving the behaviors of the systems. Based on the Petri net models of FMSs, this paper embeds deadlock control policies into heuristic search algorithm, and proposes a deadlock-free scheduling algorithm to minimize makespan for FMSs. Scheduling is performed as heuristic search in the reachability graph of the Petri net. The searching process is guided by a heuristic function based on firing count vectors of state equation for the Petri net. By using the one-step look-ahead method in the optimal deadlock control policy, the safety of a state is checked. Experimental results are provided to show effectiveness of the proposed heuristic search approach in deadlock-free scheduling for FMSs.     

Liveness-enforcing supervisors synthesis for a class of generalised Petri nets based on two-stage deadlock control and mathematical programming

In this article we deal with deadlock prevention problems for S⁴PR, a class of generalised Petri nets, which can well model a large class of flexible manufacturing systems where deadlocks are caused by insufficiently marked siphons. We present a deadlock prevention methodology that is an iterative approach consisting of two stages. The first one is called siphon control, which is to add for each insufficiently marked minimal siphon a control place to the original net. Its objective is to prevent a minimal siphon from being insufficiently marked. The second one, called control-induced siphon control, is to add a control place to the augmented net with its output arcs connecting to the source transitions, which assures that there are no new insufficiently marked siphons generated. At each iteration, a mixed integer programming approach is adopted for generalised Petri nets to obtain an insufficiently marked minimal siphon from the maximal deadly siphon. This way complete siphon enumeration is avoided that is much more time-consuming for a sizeable plant model than the proposed method. The relation of the proposed method and the liveness and reversibility of the controlled net is obtained. Examples are presented to demonstrate the presented method.     

The fundamental closed-form solution of control-related states of kth order S3PR system with left-side non-sharing resource places of Petri nets

Due to the state explosion problem, it has been unimaginable to enumerate reachable states for Petri nets. Chao broke the barrier earlier by developing the very first closed-form solution of the number of reachable and other states for marked graphs and the kth order system. Instead of using first-met bad marking, we propose ‘the moment to launch resource allocation’ (MLR) as a partial deadlock avoidance policy for a large, real-time dynamic resource allocation system. Presently, we can use the future deadlock ratio of the current state as the indicator of MLR due to which the ratio can be obtained real-time by a closed-form formula. This paper progresses the application of an MLR concept one step further on Gen-Left kth order systems (one non-sharing resource place in any position of the left-side process), which is also the most fundamental asymmetric net structure, by the construction of the system's closed-form solution of the control-related states (reachable, forbidden, live and deadlock states) with a formula depending on the parameters of k and the location of the non-sharing resource. Here, we kick off a new era of real-time, dynamic resource allocation decisions by constructing a generalisation formula of kth order systems (Gen-Left) with r^* on the left side but at arbitrary locations.     

A deadlock prevention approach for a class of timed Petri nets using elementary siphons

To solve the problem of deadlock prevention for timed Petri nets, an effective deadlock prevention policy based on elementary siphons is proposed in this paper. Without enumerating reachable markings, deadlock prevention is achieved by adding monitors for elementary siphons, increasing control depth variables when necessary, and removing implicit, liveness‐restricted and redundant control places. The final supervisor is live. First, a timed Petri net is stretched into a stretched Petri net (SPN). Unchanging the system performance, each transition in the SPN has a unit delay time. Then the siphon‐control‐based approach is applied. Monitors computed according to the marking constraints are added to the SPN model to ensure all strict minimal siphons in the net invariant‐controlled. A liveness‐enforcing supervisor with simple structure can be obtained by reverting the SPN into a TdPN. Copyright © 2010 John Wiley and Sons Asia Pte Ltd and Chinese Automatic Control Society     

资源配置混杂Petri网的混杂系统生产过程动态调度

为了增强混杂生产过程应对突发事件的能力,以一种新的混杂Petri网(资源配置混杂Petri网)为研究模型,给出了相应的使能和激发规则.并在资源配置混杂Petri网建立的仿真模型的基础上,融入事件逻辑网和逻辑规划,提出一种适用于混杂系统动态生产调度建模和优化的方法.以典型的混杂生产过程为例,研究混杂系统生产过程建模及优化.研究结果表明,资源配置混杂Petri网模型描述能力强,能够有效描述混杂系统生产过程,所提出的动态调度方案切实有效.     

基于Petri网和混沌粒子群的JSP优化

以最小化完工时间为目标构建Petri网模型,并基于该模型将混沌原理和粒子群算法相结合,提出了一种基于Logistic映射的混沌粒子群优化（CPSO）算法。仿真实验结果表明,该算法能跳出局部最优,增强了全局寻优能力,进一步提高了计算精度和收敛速度。     

随机柔性Flow shop加权完成时间调度问题的启发式策略性能分析

因实际生产中调度问题的规模很大,分析其近似算法的绝对性能比很难,有时甚至不可能,所以研究近似算法的渐近性能比就很有必要．本文针对随机柔性Flow shop加权完成时间调度问题,使用单机松弛和概率分析方法,证明了基于加权最短期望处理时间需求的启发式策略是渐近最优的．     

An efficient heuristic for adaptive production scheduling and control in one-of-a-kind production

Even though research in flow shop production scheduling has been carried out for many decades, there is still a gap between research and application—especially in manufacturing paradigms such as one-of-a-kind production (OKP) that intensely challenges real time adaptive production scheduling and control. Indeed, many of the most popular heuristics continue to use Johnson's algorithm (1954) as their core. This paper presents a state space (SS) heuristic, integrated with a closed-loop feedback control structure, to achieve adaptive production scheduling and control in OKP. Our SS heuristic, because of its simplicity and computational efficiency, has the potential to become a core heuristic. Through a series of case studies, including an industrial implementation in OKP, our SS-based production scheduling and control system demonstrates significant potential to improve production efficiency.     

生化网络的随机Petri网建模与分析

细胞的行为是随机性的,学习细胞中的随机性有助于理解细胞的组织,设计和进化。建立、确认和分析随机的生化网络模型是当前计算系统生物学领域的一个重要研究主题。当前,标准的Petri网模型已经成为生化网络模拟和定性分析的有力工具。尝试使用随机Petri网对生化网络进行建模与分析,简单描述了随机Petri网理论对标准Petri网的扩充,通过对二聚作用和肌动蛋白这两个典型例子的建模与演化模拟,介绍、论证了随机Petri网理论的新应用。     

间歇式化工系统的Petri网优化调度与控制方法

为了解决复杂间歇式化工系统的优化调度和控制问题,提出了一种基于Petri网的优化调度与控制方法:首先,根据加工工艺,建立加工过程的赋时Petri网模型;其次,根据间歇式化工生产对象的拓扑结构,在该赋时Petri网模型中引入阀门系统的网结构,从而获得系统的受控Petri网模型;最后,利用可达图来计算加工时间最短的控制策略,借助网结构信息,得到了控制策略的阀门控制矩阵,并用一个示例演示验证了本文方法.