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.     

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)     

Parallel machine scheduling with tool loading: a constraint programming approach

This paper presents constraint programming models that aim to solve scheduling and tool assignment problems in parallel machine environments. There are a number of jobs to be processed on parallel machines. Each job requires a set of tools, but limited number of tools are available in the system due to economic restrictions. The problem is to assign the jobs and the required tools to machines and to determine the schedule so that the makespan is minimised. Three constraint programming models are developed and compared with existing methods described in the literature.     

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.     

Real-time deadlock-free scheduling for semiconductor track systems based on colored timed Petri nets

This paper addresses the problem of real-time deadlock-free scheduling for a semiconductor track system. The system is required to process wafers continuously, cassette by cassette. The process is not necessarily a repeated one. In addition, the system is deadlock-prone and its modules are failure-prone. Thus, real-time scheduling approaches are required to achieve high-performance. The problem can be solved in a hierarchical way. A deadlock avoidance policy is developed for the system as a lower-layer controller. With the support of the deadlock avoidance policy, heuristic rules are proposed to schedule the system in real-time. An effective modeling tool, colored–timed resource-oriented Petri net, is presented. It is shown that with this model we can schedule a system to achieve satisfactory results in real-time. This method is tolerant to module failures.     

Scheduling of flexible manufacturing systems based on Petri nets and hybrid heuristic search

This paper proposes and evaluates a hybrid search strategy and its application to flexible manufacturing system (FMS) scheduling in a Petri net framework. Petri nets can concisely model multiple lot sizes for each job, the strict precedence constraint, multiple kinds of resources, and concurrent activities. To cope with the complexities for FMS scheduling, this paper presents a hybrid heuristic search strategy, which combines the heuristic A* strategy with the DF strategy based on the execution of the Petri nets. The search scheme can invoke quicker termination conditions, and the quality of the search result is controllable. To demonstrate this, the scheduling results are derived and evaluated through a simple FMS with multiple lot sizes for each job. The algorithm is also applied to a set of randomly generated more complex FMSs with such characteristics as limited buffer sizes, multiple resources, and alternative routings.     

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.     

基于随机Petri网的铜带拉弯矫直机可用度分析

为了合理确定铜带拉弯矫直机的校验周期,提高其生产效率,确保其矫直精度,根据某铜板带公司拉弯矫直机9个月的维修数据,对拉弯矫直机的失效模式进行随机Petri网建模,将系统失效模式转换成相应的随机Petri网;基于马尔科夫过程对随机Petri网进行瞬态概率求解,并得到该拉弯矫直机失效模式的稳态概率;利用或门对应的随机Petri网模型分析,计算不同校验周期下拉弯矫直机的可用度.综合考虑设备可用度和经济效益,确定了合理的校验周期,为拉弯矫直机的长周期运行提供了依据.     

Deadlock-free genetic scheduling for flexible manufacturing systems using Petri nets and deadlock controllers

In this paper, a new deadlock-free scheduling method based on genetic algorithm and Petri net models of flexible manufacturing systems is proposed. The optimisation criterion is to minimise the makespan. In the proposed genetic scheduling algorithm, a candidate schedule is represented by a chromosome that consists of two sections: route selection and operation sequence. With the support of a deadlock controller, a repairing algorithm is proposed to check the feasibility of each chromosome and fix infeasible chromosomes to feasible ones. A feasible chromosome can be easily decoded to a deadlock-free schedule, which is a sequence of transitions without deadlocks. Different kinds of crossover and mutation operations are performed on two sections of the chromosome, respectively, to improve the performance of the presented algorithm. Computational results show that the proposed algorithm can get better schedules. Furthermore, the proposed scheduling method provides a new approach to evaluate the performance of different deadlock controllers.     

Modeling of system reliability Petri nets with aging tokens

The paper addresses the dynamic modeling of degrading and repairable complex systems. Emphasis is placed on the convenience of modeling for the end user, with special attention being paid to the modeling part of a problem, which is considered to be decoupled from the choice of solution algorithms. Depending on the nature of the problem, these solution algorithms can include discrete event simulation or numerical solution of the differential equations that govern underlying stochastic processes. Such modularity allows a focus on the needs of system reliability modeling and tailoring of the modeling formalism accordingly. To this end, several salient features are chosen from the multitude of existing extensions of Petri nets, and a new concept of aging tokens (tokens with memory) is introduced. The resulting framework provides for flexible and transparent graphical modeling with excellent representational power that is particularly suited for system reliability modeling with non-exponentially distributed firing times. The new framework is compared with existing Petri-net approaches and other system reliability modeling techniques such as reliability block diagrams and fault trees. The relative differences are emphasized and illustrated with several examples, including modeling of load sharing, imperfect repair of pooled items, multiphase missions, and damage-tolerant maintenance. Finally, a simple implementation of the framework using discrete event simulation is described.     

A coloured Petri net-based hybrid heuristic search approach to simultaneous scheduling of machines and automated guided vehicles

To achieve a significant improvement in the overall performance of a flexible manufacturing system, the scheduling process must consider the interdependencies that exist between the machining and transport systems. However, most works have addressed the scheduling problem as two independent decision making problems, assuming sufficient capacity in the transport system. In this paper, we study the simultaneous scheduling (SS) problem of machines and automated guided vehicles using a timed coloured Petri net (TCPN) approach under two performance objectives; makespan and exit time of the last job. The modelling approach allows the evaluation of all the feasible vehicle assignments as opposed to the traditional dispatching rules and demonstrates the benefits of vehicle-controlled assignments over machine-controlled for certain production scenarios. In contrast with the hierarchical decomposition technique of existing approaches, TCPN is capable of describing the dynamics and evaluating the performance of the SS problem in a single model. Based on TCPN modelling, SS is performed using a hybrid heuristic search algorithm to find optimal or near-optimal schedules by searching through the reachability graph of the TCPN with heuristic functions. Large-sized instances are solved in relatively short computation times, which were a priori unsolvable with conventional search algorithms. The algorithm’s performance is evaluated on a benchmark of 82 test problems. Experimental results indicate that the proposed algorithm performs better than the conventional ones and compares favourably with other approaches.     

Modelling and simulation of a bottling plant using hybrid Petri nets

In this paper we use First–Order Hybrid Petri nets (FOHPN), an hybrid model that combines fluid and discrete event dynamics, to model the concurrent activities of manufacturing systems. In particular we consider an existing mineral water bottling plant and we show how the FOHPN model is extremely suited to describe the high-throughput production lines, that are one of the main components in the considered plant. Some variations with respect to the previous definition of the FOHPN model are also introduced here to better describe the behavior of the conveyor lines. Finally, we show that, thanks to the fluid approximation of some discrete-event dynamics, the considered plant may also be efficiently simulated using FOHPN. This also enabled us to identify, among the most commonly used configurations of the plant, which are the optimal working conditions in terms of maximal throughput and net profit.     

Supply chain configuration with co-ordinated product,process and logistics decisions: an approach based on Petri nets

Supply chain configuration lends itself to be an effective means to deal with product differentiation and customisation throughout a supply chain network. It essentially entails the instantiation of a generic supply chain network to specific supply chains in accordance with diverse customer requirements. The lynchpin of supply chain configuration lies in the co-ordination of product, process and logistics decisions in relation to a variety of customer orders. This paper aims to provide modelling support to supply chain configuration. The ultimate goal is to assist companies to form appropriate supply chains with the most added-value to customer order fulfillment. A formalism based on coloured Petri nets is developed for configuring supply chains. System models are built upon the coloured Petri nets and used to incorporate product and process concerns into the supply chain configuration process. An industrial case study is reported to illustrate the potential of the coloured Petri net modelling formalism and the built system models for supply chain configuration.     

Batch versus cyclic scheduling of flexible flow shops by mixed-integer programming

New mixed-integer programming models are proposed for deterministic batch or cyclic scheduling in flow shops with parallel machines and finite in-process buffers. Models for scheduling with all machines continuously available for processing throughout the entire scheduling horizon as well as for scheduling with an arbitrary pattern of machine availability due to pre-scheduled downtime events are provided. Numerical examples modelled after real-world flexible flow shop scheduling in electronics manufacturing are presented, and to compare the batch and cyclic schedules with continuous or with limited machine availability, results of computational experiments are reported.     

Evaluation of the logistic model of the reconfigurable manufacturing system based on generalised stochastic Petri nets

To reveal the influence on system performance by the logistic model of reconfigurable manufacturing system (RMS), the generalised stochastic Petri nets (GSPN) modular modelling approach is presented in this paper. It is based upon the characteristics of a bottleneck service. According to this approach, the bottleneck service in the production process is found first. By corresponding different resources in the service to different modules of the GSPN, the module is reconfigured. The analysis of the model using the Markov chain is hereby presented, as is the average utilisation factor of RMS. Following this, the production capacity of different products and the average productivity of reconfigurable manufacturing cells (RMCs) are discussed.     

Mixed-integer linear programming method for multi-degree and multi-hoist cyclic scheduling with time windows

Multi-degree cyclic hoist scheduling and multi-hoist cyclic scheduling are both capable of improving the throughput in an automatic electroplating line. However, previous research on integrated multi-degree and multi-hoist cyclic scheduling is rather limited. This article develops an optimal mixed-integer linear programming model for the integrated multi-degree and multi-hoist cyclic scheduling with time window constraints. This model permits overlap on hoist coverage ranges, and it proposes new formulations to avoid hoist collisions, by which time window constraints and tank capacity constraints are also formulated. A set of available benchmark instances and newly generated instances are solved using the CPLEX solver to test the performance of the proposed method. Computational results demonstrate that the proposed method outperforms the zone partition heuristic without overlapping, and the throughputs are improved by a significant margin using the proposed method, especially for large-size instances.     

考虑资源成本的Petri网在FMS调度中的应用

本文针对目前基于petri网的调度方法中调度目标单一的缺点，通过在petri网的结构中引入资源成本元素的方法，使得在调度计划产生的过程中可以同时考虑时间和资源成本优化，为企业作出更为科学合理的生产决策提供依据．最后通过一个实例来验证了提出的算法。     

Deadlock modeling and control of semiconductor track systems using resource-oriented Petri nets

This paper addresses the deadlock avoidance problem in track systems in semiconductor fabrication. For the system without buffer space in it, the existing deadlock avoidance policies tend to be too conservative. Routing flexibility provides a chance to develop better ones, but makes their computation more complex. This paper models a track system using coloured resource-oriented Petri net (CROPN). Based on the model, a sufficient condition for deadlock-free operation and the corresponding control law are presented. This proposed policy is shown computationally efficient and less conservative than existing methods. An example is presented to demonstrate its application.     

Production scheduling with outsourcing scenarios: a mixed integer programming and efficient solution procedure

When market demand exceeds the company's capacity to manufacture, outsourcing is commonly considered as an effective alternative option. In traditional scheduling problems, processing of received orders is just possible via in-house resources, while in practice, outsourcing is frequently found in various manufacturing industries, especially in electronics, motor and printing companies. This paper deals with the scheduling problem, minimising the cost of outsourcing and a scheduling measure represented by weighted mean flow time, in which outsourcing of manufacturing operations is allowed through subcontracts. Each order can be either scheduled for in-house production or outsourced to an outside supplier in order to meet customer due dates. In this problem, not only should the sequence of orders be determined, but also decision on picking the jobs for outsourcing, selecting the appropriate subcontractor, and scheduling of the outsourced orders are considered as new variables. To formulate the given problem, four different outsourcing scenarios are derived and mixed integer programming models are developed for each one separately. Furthermore, to solve the suggested problem, a computationally effective team process algorithm is devised and then a constraint handling technique is embedded into the main algorithm in order to ensure satisfaction of customer due dates. Numerical results show that the suggested approach possesses high global solution rates as well as fast convergence.