Modelling,control and simulation of an IC wafer fabrication system: A generalized stochastic coloured timed Petri Net approach

This study presents a generalized stochastic coloured timed Petri net(GSCTPN) to model an IC wafer fabrication system. According to the GSCTPN, it models the dynamic behaviours of the IC fabrication system, such as loading, reentrant processing, unloading and machine failure. Furthermore, modular and synthesis techniques are used to construct a large and complex system model. The two major sub-models are the Process-Flow Model and the Transportation Model. The Transportation Model incorporates a simple motion-planning rule and a collision avoidance strategy to solve the variable speed and traffic jam problems of vehicles. This work also describes a simulation based performance analysis and schedule adjustment. To demonstrate the promise of the proposed work, this study makes actual Taiwanese IC wafer fabrication systems the target plant layout for implementation.     

Modelling of semiconductor wafer fabrication systems by extended object-oriented Petri nets

In this paper, extended object-oriented Petri nets (EOPNs) are proposed for the effective modelling of semiconductor wafer fabrication systems (SWFSs). To cope with their complexity in terms of the re-entrant process route and the mixed production mode, a special type of transition called main-bus gate is introduced, which may lead each kind of product to undergo every re-entrant processing stage. In addition, the hierarchical approach is also applied to cope with the complexity. An etching area that processes 0.25?µm logic IC products is taken as an illustration to present the detailed modelling procedures by EOPNs, and the resulting model validates that the EOPNs may cope well with complex SWFSs modelling.     

Setup planning using Hopfield net and simulated annealing

This paper reports a new approach to setup planning of prismatic parts using Hopfield neural net coupled with simulated annealing. The approach deals with setup planning in two stages, i.e.: (1) sequence all the features of a workpiece according to geometric and technological constraints; and (2) identify setups from the sequenced features. In the first stage, the task of feature sequencing is converted to a constraint optimization problem (COP) which is similar to the travelling salesman problem (TSP). The setup time due to setup and tool changes is incorporated into the 'distance' between features, while the precedence and critical tolerance relationships between features are treated as constraints. The Hopfield neural net approach for TSP, i.e. energy function, is adopted to model the COP mathematically where the constraints are attached as additional penalty functions. Simulated annealing is then used to search for the minimum energy state of the net while avoiding the local minima. The feature sequence obtained aims at minimizing the number of setups and tool changes while ensuring little or no violation of feature precedence relationship, thus keeping critical tolerance violation to a minimum. In the second stage, setups are generated from the sequenced features using a vector intersection approach based on common tool approach directions. A case study is presented to demonstrate the effectiveness of this approach. A comparison study between this approach and an existing integer programming setup planning system is also given which indicates the superior efficiency of the proposed approach when dealing with problems with large number of features.     

Unit commitment by heuristics and absolutely stochastic simulated annealing

A new approach to unit commitment problem is presented using absolutely stochastic simulated annealing method. In every iteration, a solution is taken with a certain probability. Typically in simulated annealing minimisation method, a higher cost feasible solution is accepted with temperature-dependent probability; however, other solutions are accepted deterministically. That may lead to the near optimisation slowly. However, all the solutions of both higher and lower costs, are associated with acceptance probabilities to make an early jump from one local minimum to other so that it can search and compare more local minima within the same time/iteration limit. Besides, the number of bits flipping is decided by the appropriate distribution. Excess units with system-dependent probability distribution handle constraints efficiently. Sensitivity of the distribution parameters is tolerable. To reduce economic load dispatch calculations, a sign bit vector is introduced as well. The proposed method is then tested using the reported problem data set. Simulation results are compared to previous reported results. Numerical results show an improvement in solution cost and time compared to the results obtained from powerful algorithms     

Genetic algorithms and simulated annealing for scheduling in agile manufacturing

In this paper, genetic algorithms and simulated annealing are applied to scheduling in agile manufacturing. The system addressed consists of a single flexible machine followed by multiple identical assembly stations, and the scheduling objective is to minimize the makespan. Both genetic algorithms and simulated annealing are investigated based on random starting solutions and based on starting solutions obtained from existing heuristics in the literature. Overall, four new algorithms are developed and their performance is compared to the existing heuristics. A 2³ factorial experiment, replicated twice, is used to compare the performance of the various approaches, and identify the significant factors that affect the frequency of resulting in the best solution and the average percentage deviation from a lower bound. The results show that both genetic algorithms and simulated annealing outperform the existing heuristics in many instances. In addition, simulated annealing outperforms genetic algorithms with a more robust performance. In some instances, existing heuristics provide comparable results to those of genetic algorithms and simulated annealing with the added advantage of being simpler. Significant factors and interactions affecting the performance of the various approaches are also investigated.     

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.     

Modelling and planning of the disassembly processes using an enhanced expert Petri net

A sound disassembly Petri net model for the effective planning of disassembly processes and tasks is outlined. Owing to the unmanageable complexity associated with modelling of the disassembly processes and tasks, it becomes essential to have a more powerful Petri net model developed by incorporating the concepts of expert system, knowledge representation techniques, etc. Disassembly task planning at high and low levels can easily be represented by proposed high- and low-level expert Petri net. An algorithmic approach is also suggested for evaluating the end-of-life values of a product. These values are used to determine an optimal disassembly sequence and it is incorporated in the expert disassembly Petri net. A proposed expert enhanced high-level coloured disassembly Petri net is empowered to express such details vividly. The application of the proposed expert enhanced high-level coloured disassembly Petri net model is demonstrated through the sample disassembly of a flashlight.     

Performance evaluation of tandem and conventional AGV systems using generalized stochastic Petri nets

This paper investigates the different policies and concepts followed in the traffic management of automated guided vehicle (AGV) systems, and develops the controls for automatically eliminating potential vehicle conflicts in an AGV system. The planning of the AGV system is performed in such a way that there are no conflicts or deadlocks for the vehicles using stochastic Petri nets (SPNs). The major effort is devoted to determining the benefits of the tandem AGV control in comparison with the conventional AGV control method. SPNs have been used to model the different designs of flexible manufacturing systems (FMSs) and with different policies for the movement of material, vehicle path control, inventory planning and tool control. The SPN model is solved and the performance of the system can be evaluated. In this study, the effort is directed to model an FMS with two different types of AGV traffic management methods, namely the conventional and tandem AGV control. A SPN program is used which takes the FMS Petri net model as the input and evaluates the different properties of the Petri net. Finally the performance measures are obtained, which helps in evaluating and comparing the two different AGV traffic management methods.     

医疗信息系统工作流的Petri网建模与化简分析

应用 Petri网建模与工作流技术,构建了基于医疗信息整合(IHE)规范的医疗信息系统工作流的Petri网模型,并对一个医疗信息系统工作流实例,给出了基于Petri网化简分析方法的模型化简与性质验证,表明该模型能够对医疗信息工作流进行有效的分析和验证,从而为医疗信息系统集成设计及其工作流分析提供了理论基础.     

Applying a hybrid simulated annealing and tabu search approach to non-permutation flowshop scheduling problems

Researchers have indicated that a permutation schedule can be improved by a non-permutation schedule in a flowshop with completion time-based criteria, such as makespan and total completion time. This study proposes a hybrid approach which draws on the advantages of simulated annealing and tabu search for the non-permutation flowshop scheduling problem, in which the objective function is the makespan of the schedule. To verify the effectiveness of the proposed hybrid approach, computational experiments are performed on a set of well-known non-permutation flowshop scheduling benchmark problems. The result shows that the performance of the hybrid approach is better than that of other approaches, including ant colony optimisation, simulated annealing, and tabu search. Further, the proposed approach found new upper bound values for all benchmark problems within a reasonable computational time.     

Fractional factorial analysis to the configuration of simulated annealing applied to the multi-objective optimization of master production scheduling problems

Searching for the global optimal solution in a Master Production Scheduling problem usually demands an effort most industries are not willing to pay. Therefore, the use of meta-heuristics that generates good solutions in reasonable computer time becomes an attractive alternative. However, such strategies are usually complex to implement and configuring their parameters is not a trivial task because of the number of usually conflicting objectives involved. The use of statistical methods that facilitate the set-up of the heuristic's parameters becomes therefore necessary. Knowing which parameters are more important, that is, the ones that really affect the solution quality, and those that are irrelevant, is very important for chosen technique performance. This work presents how fractional factorial analysis can be applied to the configuration of simulated annealing used for optimization of Master Production Scheduling problems. Two scheduling scenarios illustrate the use of the proposed method.     

Hybrid simulated annealing and reduced variable neighbourhood search for an aircraft scheduling and parking problem

Aircraft stands and runways at airports are critical airport resources for aircraft scheduling and parking. Making use of limited apron and runway resources to improve airport efficiency is becoming increasingly important. In this paper, we study a realistic Aircraft Scheduling and Parking Problem (ASPP) with the goal of simultaneously determining the takeoff and landing time of each aircraft with consideration for wake vortex effect constraints and parking positions in the limited parking apron at a target airport. The objective of the ASPP is to minimise the total service time for aircraft. We developed a mixed-integer linear programme formulation for the ASPP. A novel improved bottom-left/right strategy is applied to construct solutions and a Hybrid Simulated Annealing and Reduced Variable Neighborhood Search (HSARVNS) is proposed to identify near-optimal solutions. Numerical experiments on randomly generated ASPP instances and on a large set of benchmarks for a reduced version of the ASPP (i.e. the classical Two-Dimensional Strip-Packing Problem (2D-SPP)) demonstrate the effectiveness and efficiency of the proposed approach. For the ASPP, HSARVNS can find optimal solutions for small instances in a fraction of a second and can find high-quality solutions for instances with up to 250 aircraft within a reasonable timeframe. For the 2D-SPP, the HSARVNS can find optimal solutions for 32 of 38 tested benchmarks within 90 s on average.     

Probabilistic asymptotic analysis of stochastic online scheduling problems

In the stochastic online scheduling environment, jobs with unknown release times and weights arrive over time. Upon arrival, the information on the weight of the job is revealed but the processing requirement remains unknown until the job is finished. In this paper we consider the objective of minimizing the total weighted completion time. With the assumptions that job weights are bounded, machine capacity is adequate, and processing requirements are bounded and identical and independently distributed across the machines and jobs, we show that any nondelay algorithm is asymptotically optimal for the stochastic online single machine problem, flow shop problem, and uniform parallel machine problem. Our simulation studies of these stochastic online scheduling problems show that two generic nondelay algorithms perform very well as long as the number of jobs is larger than 100.     

Selection of dispatching rules on multiple dispatching decision points in real-time scheduling of a semiconductor wafer fabrication system

Semiconductor wafer fabrication involves one of the most complex manufacturing processes ever used. To control such complex systems, it is a challenge to determine appropriate dispatching strategies under various system conditions. Dispatching strategies are classified into two categories: a vehicle-initiated dispatching policy and a machine-initiated dispatching policy. Both policies are important to improve the system performance, especially for the real time control of the system. However, there has been little research focusing on combining them under various situations for the semiconductor manufacturing system. In addition, it is shown that no single dispatching strategy consistently dominates others in all situations. Therefore, the goal of this study is to develop a scheduler for selection of dispatching rules for dispatching decision variables in order to obtain the desired performance measures given by a user for each production interval. For the proposed methodology, simulation and competitive neural network approaches are used. The results of the study indicate that applying our methodology to obtaining a dispatching strategy is an effective method considering the complexity of semiconductor wafer fabrication systems.     

基于Petri网的可信连接架构的安全属性分析

为确保可信连接架构(TCA)自身的安全可靠,研究了其安全属性量化问题,分析了其双向用户身份认证和平台认证过程中存在的安全威胁.利用随机Petri网对带有攻击行为的TCA可信网络连接过程进行了建模,该模型用于描述攻击行为和TCA的双向认证过程.以该模型为基础构造了马尔科夫链,通过计算马尔科夫模型的稳定状态概率对TCA的稳定状态机密性和完整性等安全属性进行定量分析.最后给出了一个具体数值评估结果的实例.此研究给出的方法有理论和实用意义.     

Structural analysis of a Petri net model of oxidative stress in atherosclerosis

Atherosclerosis is a complex process of gathering sub‐endothelial plaques decreasing lumen of the blood vessels. This disorder affects people of all ages, but its progression is asymptomatic for many years. It is regulated by many typical and atypical factors including the immune system response, a chronic kidney disease, a diet rich in lipids, a local inflammatory process and a local oxidative stress that is here one of the key factors. In this study, a Petri net model of atherosclerosis regulation is presented. This model includes also some information about stoichiometric relationships between its components and covers all mentioned factors. For the model, a structural analysis based on invariants was made and biological conclusions are presented. Since the model contains inhibitor arcs, a heuristic method for analysis of such cases is presented. This method can be used to extend the concept of feasible t‐invariants.Inspec keywords: diseases, blood vessels, Petri nets, biochemistry, physiological models, oxidationOther keywords: structural analysis, Petri net model, oxidative stress, atherosclerosis, subendothelial plaques, blood vessels, immune system response, chronic kidney disease, t‐invariants     

A multi-objective optimisation model to integrating flexible process planning and scheduling based on hybrid multi-objective simulated annealing

Process planning and production scheduling play important roles in manufacturing systems. In this paper we present a mixed integer linear programming (MILP) scheduling model, that is to say a slot-based multi-objective multi-product, that readily accounts for sequence-dependent preparation times (transition and set up times or machine changeover time). The proposed scheduling model becomes computationally expensive to solve for long time horizons. The aim is to find a set of high-quality trade-off solutions. This is a combinatorial optimisation problem with substantially large solution space, suggesting that it is highly difficult to find the best solutions with the exact search method. To account for this, the hybrid multi-objective simulated annealing algorithm (MOHSA) is proposed by fully utilising the capability of the exploration search and fast convergence. Two numerical experiments have been performed to demonstrate the effectiveness and robustness of the proposed algorithm.     

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

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