Modular Petri nets for simulation of flexible production systems

The use of Petri nets for modelling, analysing and simulating complex distributed production systems meets serious problems when the size of the model grows. Therefore, it would be very useful to decompose a Petri net based model into smaller models linked with one another. The aim of this paper is to suggest and discuss some possible definitions of Modular Petri nets. This is accomplished by introducing the concept of Petri subnet. Two possible definitions are proposed and the meaning and the usefulness with respect to both model definition and model executability for simulation are pointed out. All definitions are given for the basic model of Petri nets. The extension of modularity concepts to high level Petri nets is shown to be possible in the second part of the paper, where an application is illustrated. In particular an algorithm is given which allows automatic composition of subnets into a larger model     

Optimisation of block erection scheduling based on a Petri net and discrete PSO

The shipyard block erection system (SBES) is a typical discrete-event dynamic system. To model multiprocessing paths and a concurrent assembly procedure, a timed Petri net (TPN) is proposed. The definition of a Petri net is extended to accord with the real-world SBES organisation. The basic TPN modules are presented to model the corresponding variable structures in the SBES, and then the scheduling model of the whole SBES is easily constructed. A modified discrete particle swarm optimisation (PSO) based on the reachability analysis of Petri nets is developed for scheduling of the SBES. In the proposed algorithm, particles are coded by welding transitions and selecting places of the TPN model, and then the collaboration and competition of particle individuals is simulated by crossover and mutation operators in a genetic algorithm. Numerical simulation suggests that the proposed TPN–PSO scheduler can provide an improvement over the conventional scheduling method. Finally, a case study of the optimisation of a back block erection process is provided to illustrate the effectiveness of the method.     

Intuitionistic Fuzzy Petri Nets Model Based on Back Propagation Algorithm for Information Services

Intuitionistic fuzzy Petri net is an important class of Petri nets, which can be used to model the knowledge base system based on intuitionistic fuzzy production rules. In order to solve the problem of poor self-learning ability of intuitionistic fuzzy systems, a new Petri net modeling method is proposed by introducing BP (Error Back Propagation) algorithm in neural networks. By judging whether the transition is ignited by continuous function, the intuitionistic fuzziness of classical BP algorithm is extended to the parameter learning and training, which makes Petri network have stronger generalization ability and adaptive function, and the reasoning result is more accurate and credible, which is useful for information services. Finally, a typical example is given to verify the effectiveness and superiority of the parameter optimization method.     

Lagrangian relaxation and cut generation for sequence-dependent setup time flowshop scheduling problems to minimise the total weighted tardiness

The Lagrangian relaxation and cut generation technique is applied to solve sequence-dependent setup time flowshop scheduling problems to minimise the total weighted tardiness. The original problem is decomposed into individual job-level subproblems that can be effectively solved by dynamic programming. Two types of additional constraints for the violation of sequence-dependent setup time constraints are imposed on the decomposed subproblems in order to improve the lower bound. The decomposed subproblem with the additional setup time constraints on any subset of jobs is also effectively solved by a novel dynamic programming. Computational results show that the lower bound derived by the proposed method is much better than those of CPLEX and branch and bound for problem instances with 50 jobs and five stages with less computational effort.     

A Branch-and-price algorithm for placement routing for a multi-head beam-type component placement tool

We develop a branch-and-price procedure for a placement routing problem for a multi-head beam-type component placement tool. The problem is modelled as an integer programming model with a huge number of variables, each of which corresponds to a placement route. Its linear programming relaxation is solved by a column generation method. For the column generation subproblem to determine the columns to be added, we develop a dynamic programming procedure. We also propose an effective branching rule to partition the current solution space to eliminate the current fractional solution. Through experiments using real tool data, we observe that the LP relaxation solution value is noticeably close to an integer optimal solution value and hence the integer program formulation and the column generation approach are effective.     

Petri net based scheduling

Timed Petri nets can be used to model and analyse scheduling problems. To support the modelling of scheduling problems, we provide a method to map tasks, resources and constraints onto a timed Petri net. By mapping scheduling problems onto Petri nets, we are able to use standard Petri net theory. In this paper we will show that we can use Petri net based tools and techniques to find conflicting and redundant precedences, upper- and lower-bounds for the makespan, etc. This is illustrated by a Petri net based analysis of the notorious 10×10 problem due to Fisher & Thompson (1963)     

分布式FMS智能调度和控制系统的研究与开发

介绍了分布式ＦＭＳ智能调度和控制系统的研究与开发情况：提出了一种新的适合于分布式系统建模的网络计时Ｐｅｔｒｉ网ＮＴＰＮ；将ＮＴＰＮ模型与专家系统技术相结合，为系统控制器开发了基于工程的专家系统ＥＢＥＳ；利用面向对象的技术开发了仿真的对象类库，并实现了从仿真到控制的软件重用。     

Graph contractability problem for VLSI layer assignment

Abstract

The layer assignment problem for VLSI routing is the problem of determining which layers can be used for routing the wire segments in the interconnections of nets so that the number of vias is minimized. In this paper, we transform the problem of layer assignment for three‐layer routing to the contractability problem of 3‐colorable graph. This problem is shown to be NP‐complete and a heuristic algorithm is proposed on the basis of the graph contractability model. From our experimental results, the algorithm is faster and efficient to generate very good results. In the average, the number of vias can be reduced by 30 percent or so.     

Efficient Lagrangian relaxation algorithms for industry size job-shop scheduling problems

We improve the job specific decomposition Lagrangian relaxation algorithm applied to industry size job shop scheduling problems with more than 10 000 resource constraints. We introduce two new features in the Lagrange multiplier updating procedure. First, the usual solution of all subproblems followed by dual cost estimation and update of multiplier values is replaced by the estimation of a surrogate dual cost function and a more frequent update of multipliers is implemented after each subproblem solution. Second, an adaptive step size in the subgradient based multiplier update is introduced. Asymptotic properties of the surrogate dual cost function are obtained and the proposed algorithmic improvements are evaluated in extensive numerical examples including published data used by other researchers, as well as extensive real industrial scheduling system data.     

Lagrangean relaxation approach to joint optimization for production planning and scheduling of synchronous assembly lines

This paper focuses on simultaneous optimisation of production planning and scheduling problem over a time period for synchronous assembly lines. Differing from traditional top-down approaches, a mixed integer programming model which jointly considers production planning and detailed scheduling constraints is formulated, and a Lagrangian relaxation method is developed for the proposed model, whereby the integrated problem is decomposed into planning, batch sequencing, tardiness and earliness sub-problems. The scheduling sub-problem is modelled as a time-dependent travelling salesman problem, which is solved using a dynasearch algorithm. A proposition of Lagrangian multipliers is established to accelerate the convergence speed of the proposed algorithm. The average direction strategy is employed to solve the Lagrangian dual problem. Test results demonstrate that the proposed model and algorithm are effective and efficient.     

Petri nets and genetic algorithms for complex manufacturing systems scheduling

In this paper we propose the GAPN (genetic algorithms and Petri nets) approach, which combines the modelling power of Petri nets with the optimisation capability of genetic algorithms (GAs) for manufacturing systems scheduling. This approach uses both Petri nets to formulate the scheduling problem and GAs for scheduling. Its primary advantage is its ability to model a wide variety of manufacturing systems with no modifications either in the net structure or in the chromosomal representation. In this paper we tested the performance on both classical scheduling problems and on a real life setting of a manufacturer of car seat covers. In particular, such a manufacturing system involves features such as complex project-like routings, assembly operations, and workstations with unrelated parallel machines. The implementation of the algorithm at the company is also discussed. Experiments show the validity of the proposed approach.     

Nested coloured timed Petri nets for production configuration of product families

Production configuration is as an effective technique to deal with product variety while maintaining production stability and efficiency. It involves a diverse set of process elements (e.g., machines, operations), a high variety of component parts and assemblies and many constraints arising from product and process variety. Production configuration entails the selection and subsequent arrangement of process elements into complete production processes and the final evaluation of configured multiple alternatives. To better understand production configuration and its implementation, we study the underlying logic for configuring production processes using a dynamic modelling and visualisation approach. This is accomplished by developing a new formalism of nested coloured timed Petri nets (PNs). In view of the inherent modelling difficulties, in the formalism three types of nets–process nets, assembly nets and manufacturing nets–together with a nested net system are defined. Using an industrial example of vibration motors, we show how the proposed formalism can be applied to specify production processes at different levels of abstraction to achieve production configuration.     

An efficient optimization procedure for designing a capacitated distribution network with price-sensitive demand

This paper considers a location-allocation problem in a supply-chain distribution network with capacitated distribution centers and customers with price-sensitive demands. The problem determines location, allocation and price decisions in order to maximize the total profit under two supply policies. Serving all of the customers is compulsory under the first policy, but is optional under the second. The problem is formulated as a mixed-integer linear program and solved by a Lagrangian relaxation algorithm under each policy. The numerical study indicates that the proposed algorithms are highly efficient and effective for solving large-sized instances of the problem.     

Supply chain modelling and managing,using timed coloured Petri nets: a case study

This paper aims at developing a new methodology for designing and managing a supply chain (SC) and, at the same time, for evaluating the performance of every stakeholder involved in a production chain. The methodology proposed has been applied to a footwear supply chain and is based on coloured Petri nets (CPNs). The supply chain analysed in this paper is a complex production system consisting of a network of manufacturers and service suppliers related to logistics systems that provide transportation and storage. The model developed uses coloured, timed Petri nets to represent a supply chain and it is such that resources are the Petri Net (PN) places, the tokens are jobs, orders and/or products, while the colours represent job attributes. These colours are used to encode different data types and values that are attached to tokens. A “coloured token” represents a specific production order or a certain amount of a particular material supplied. Thus, it can be processed in different ways and it can be easily localised within the CPN model. The use of coloured Petri nets allows companies to create a compact representation of states, actions and events of the modelled system. The particular structure of this network allows the designers the easy realisation of a simulator using an “object-oriented”, dedicated programming, which is a useful tool for developing what-if analyses.     

New approach for air traffic management based on control theory

Air traffic management aims to provide solutions to congestion problems in air traffic networks (ATNs) which in turn are mainly generated by the variation in the capacity of air sectors or airports due to adverse weather conditions. Most of the existing approaches to dealing with these problems are based on mathematical programming techniques and inherit its computational difficulty. In this paper, we introduce a control scientist point of view to this topic by proposing an approach to solve the ground-holding problem based on discrete event systems control theory. An ATN can effectively be considered as a timed discrete event system and can be efficiently modelled based on a Time Petri net tool. The main advantage is an explicit representation of the position of each aircraft in the ATN at each time instant. The state space is modelled by a Discrete Time Reachability Graph and the capacity constraints on the air sectors are modelled by time floating general mutual exclusion constraints. Feasible flight plans can be constructed based on control synthesis techniques, while an algorithm to compute the optimal flight plan is proposed assuming a realistic cost function.     

具有非负困难度的符号几何规划的一种分解方法

本文针对具有非负困难度的符号几何规划问题提出了一种新的分解方法.该方法首先利用指数变换及矩阵理论,将原问题等价地转化为一个非线性程度较低的町分离规划,然后,将所得等价问题分解成一系列易于求解的子问题,并且当困难度为零时,文中给出了求解子问题精确解的方法.最后,通过数值实例验证了新方法的有效性和可行性.     

Cost optimization for series–parallel execution of a collection of intersecting operation sets

A collection of intersecting sets of operations is considered. These sets of operations are performed successively. The operations of each set are activated simultaneously. Operation durations can be modified. The cost of each operation decreases with the increase in operation duration. In contrast, the additional expenses for each set of operations are proportional to its time. The problem of selecting the durations of all operations that minimize the total cost under constraint on completion time for the whole collection of operation sets is studied. The mathematical model and method to solve this problem are presented. The proposed method is based on a combination of Lagrangian relaxation and dynamic programming. The results of numerical experiments that illustrate the performance of the proposed method are presented. This approach was used for optimization multi-spindle machines and machining lines, but the problem is common in engineering optimization and thus the techniques developed could be useful for other applications.     

Assembly/disassembly task planning and simulation using expert Petri nets

Automatic assembly/disassembly planning is recognized as an important tool for reducing the manufacturing costs in concurrent product and process development. This paper developed a knowledge-based expert Petri net model by incorporating expert system techniques in artificial intelligence into ordinary Petri nets for an analytical framework of understanding, representing and reasoning the assembly/disassembly tasks. Substantial extensions have been made to ordinary Petri nets by adding control places, time constraints, and place and transition knowledge annotations. The proposed expert Petri net model can be considered as the hybrid of expert systems and ordinary Petri nets. Through these extensions, the capacities of modelling and representation of ordinary Petri net models are largely enhanced, and thus the expert Petri net models are more powerful than ordinary Petri nets. Such intelligent Petri net models can combine the abilities of modelling, planning, and performance evaluation for assembly/disassembly tasks in an integrated and intuitive way, and can therefore be applied to either linear/non-linear, static/dynamic, or on-line/off-line assembly/disassembly tasks at both high and low levels. The developed assembly/disassembly planning system can generate the best strategies and plans for assembly/disassembly. The research findings are exemplified with a real assembly to show the effectiveness of the method.     

A deadlock prevention policy for a class of Petri net models of flexible manufacturing systems

This paper focuses on the problem of deadlocks in automated flexible manufacturing systems (FMS). Based on Petri nets, a deadlock prevention policy is proposed for a special class of Petri nets, S³PR. We embed the deadlock avoidance policy (DAP) of conjunctive/disjunctive resources upstream neighbourhood (C/D RUN) into the deadlock prevention policy (DPP), and allocate the underlying (sequential) resources reasonably to guarantee the absence of deadlock states and processes. First, siphons in a net model are distinguished by elementary and dependent ones. From the set of elementary siphons, a set of linear inequality constraints expressed by the state vector can be formalised. After being modified by the proposed policy, a set of generalised mutual exclusion constraints (GMEC) expressed by the marking vector can be found. Then monitors based on the GMEC are added to the plant model such that the elementary siphons in the S³PR net are all invariant-controlled and no emptiable siphon is generated due to the addition of the monitors. This novel deadlock prevention policy can usually lead to a more permissive supervisor by adding a smaller number of monitors and arcs than the existing methods for the design of liveness-enforcing Petri net supervisors. Two manufacturing examples are utilised to illustrate the proposed method and compared with the existing ones.