基于Petri网与遗传算法的半导体生产线建模与优化调度

针对半导体生产线调度复杂、难以优化的问题,本文提出了一种基于层次有色赋时Petri网技术和遗传算法相结合的优化调度方法。该方法利用层次化的方法结合自顶向下建模方法对半导体生产线进行模块化建模,模型不仅能够反映生产线的待加工产品的多条加工路径及其资源约束,还可以对系统的设备维护、各种优先级等特性进行描述,得到对生产系统更完善更精确的刻画。通过在遗传算法编码中同时考虑投料策略、工件选设备规则、批加工调度规则和单件加工设备规则等因素得到更加有效的调度方案,提高了模型的优化程度。在此基础上,对实际半导体生产线的不同调度方案分别进行了仿真,并对仿真结果进行了比较,从而验证了建模方法的正确性及调度策略的有效性。     

SMT产品制造企业车间调度系统的建模与分析

有效的调度方法与优化技术的研究和应用，已成为先进制造技术实践的基础和关键。本文就车间调度问题的研究状况，探讨了SMT产品制造企业车间调度建模的研究方法，在面向对象的Petri网基础上，引入依赖消息，提出了一种扩充的面向对象Petri网（EOPN）模型，并建立了一台贴片机系统的完整的EOPN模型。     

基于蚁群优化的时间Petri网及其在柔性制造系统调度优化中的应用

Petri网的优化调度求解主要采用基于状态空间的智能搜索方法,执行效率往往不高.提出基于蚁群优化的时间Petri网,通过在Petri网的变迁和进化规则中引入蚁群优化机制,改变Petri网原有的非确定性选择行为,使之具备蚁群寻优选择智能行为,克服了需要基于状态空间进行启发式搜索的缺陷,提高了调度优化的计算效率.最后应用蚁群优化时间Petri网模型,对柔性制造系统的区间Job Shop调度问题进行建模和优化求解.实验结果进一步验证了所提模型和方法的有效性.     

基于赋时层次有色Petri网的Multi-Agent调度系统建模

介绍了基于Multi-Agent的分布式环境扫描系统的结构模型.依据赋时层次有色Petri网(HTCP-net)的理论,应用建模、仿真工具CPN Tools建立了基于优先级的任务调度算法和最短等待队列动态负载均衡调度算法的系统调度模型.仿真结果表明,该调度模型有效满足了系统周期性重复访问网站的任务需求.     

同步时序电路的增广Petri网分析

本文应用带抑制弧的增广Petri网建立了基本门电路和常用触发器的Petri网模型;并运用该模型描述了同步时序电路;提出了增广Petri网的授权矩阵、状态转移方程和触发器次态与变迁授权条件的关系。在此基础上可对同步时序电路描述和分析,并用实例证明了该方法的有效性。     

同步Petri网的仿真及硬件实现

基于现有的EDA技术,针对同步Petri网和硬件描述语言的关联性,提出了用VHDL语言对同步Petri网进行描述并实现.首先使用同步Petri网对控制器进行建模,然后使用VHDL语言对同步Petri网控制模型进行描述,最终在EDA软件Max+ PlusII中进行编译、仿真和适配,并下栽到FPGA中,通过实验开发系统GW...     

基于DFA-Petri网模型的桥式起重车辆IWD优化调度

为了提高车间桥式起重车辆(OTC)运行的有效调度,实现最短运输时间目标,提出基于DFA-Petri网模型的OTC系统车辆IWD优化调度算法。首先,对OTC系统车辆的时间-序列模型进行描述,并利用Petri网模型方法来简化优化约束,利用有限自动机(DFA)方法实现OTC系统状态空间二进制输入的降维,降低模型复杂度;其次,构建基于DFA-Petri网的OTC系统车辆优化调度模型,并利用智能水滴算法(IWD)进行调度优化;最后,通过仿真实验,验证了所提模型在调度时间指标上的优势,体现了所提方法的车辆调度实时性。     

基于Petri网的两阶段网格任务调度模型与分析

首先给出了一种集成P2P模式的网格资源管理模型,针对此模型,提出了两阶段的网格任务调度方法,并分别利用层次颜色Petri网和颜色时延Petri网来进行建模.最后,分析了网格可达任务图,给出了集成P2P模式的网格任务最佳调度方案.     

基于Agent的协同生产调度软件构架研究

本文以协同生产管理(CPM)软件开发项目为背景.针对协同生产调度管理软件模型的设计与实现方法进行讨论,提出一个全新的基于多Agent的协同生产调度软件构架,并对构架模型进行描述说明.进而对软件构架如何体现Agent特性和协同特性的技术方法进行描述.随后重点描述软件构架中的合同网结构.并引入规则树与角色协同技术进行模型优化.最后运用KQML语言对部分内容进行可实现性描述.所研究的生产调度模型在实际应用中取得良好效果.     

基于UML-OOPN的武器装备体系可靠性建模方法

针对传统可靠性模型在武器装备体系建模中存在的描述能力不足和Petri网建模存在的模型爆炸和模型构建困难问题,引入面向对象建模思想,利用UML模型便于描述系统和对象Petri网模型易于动态仿真的优点,提出了基于UML-OOPN的武器装备体系任务可靠性建模方法,通过建立UML到对象Petri网的映射规则,完成了由任务描述模型向任务可靠性对象Petri网模型的转化,从而实现了两者有效结合,并以某野战防空反导体系为例验证了该方法的可行性和有效性,为解决武器装备体系任务可靠性模型构建和高效输入问题提供了一种新的方法.     

Integrated scheduling of flexible manufacturing systems employingautomated guided vehicles

Centralized and distributed automated guided vehicle system (AGVS) models for materials handling, and the model for part processing are integrated into a single coherent model. This formulation can be used to collectively schedule and control the entire flexible manufacturing system (FMS) as opposed to the traditional separate scheduling of part processing and material handling. The two AGVS models are based on Petri nets and can be directly used in the scheduling method that uses Petri nets for formulation and heuristic search for solution. This method employs a global search to seek the optimal operation of an entire FMS. Scheduling examples are presented and the method compares favorably with the results simulated using heuristic dispatch rules     

A Petri net based approach to modeling and scheduling for an FMSand a case study

In this paper, a timed-place Petri net (TPPN) model for flexible manufacturing systems (FMSs) is constructed, which contains two major submodels: the stationary transportation model; and the variable process flow model. For multiple automated guided vehicle (AGV) systems, the authors embed a simple rule and introduce a push-AGV strategy in a TPPN model to solve the collision and traffic jam problems of such vehicles. Since a firing sequence of the TPPN from the initial marking to the final marking can be seen as a schedule of the modeled FMS, by using an A^* based search algorithm, namely, the limited-expansion A algorithm, an effective schedule of the part processing can be obtained. To show the promising potential of the proposed work, a prototype FMS is used as a target system for implementation. The experiment results assert that the job-shop scheduling problem can always be satisfactorily solved     

Scheduling single-armed cluster tools with reentrant wafer flows

A cluster tool for semiconductor manufacturing consists of several single-wafer processing chambers and a wafer-handling robot in a closed environment. The use of cluster tools is extended to reentrant processes such as atomic layer deposition, where a wafer visits a processing chamber more than once. Such a reentrant wafer How complicates scheduling and control of the cluster tool and often causes deadlocks. We examine the scheduling problem for a single-armed cluster tool with various reentrant wafer flows. We develop a convenient method of modeling tool operational behavior with reentrant wafer flows using Petri nets. By examining the net model, we then develop a necessary and sufficient condition for preventing a deadlock. We also show that the cycle time for the asymmetric choice Petri net model for a reentrant wafer How can be easily computed by using the equivalent event graph model. From the results, we systematically develop a mixed integer programming model for determining the optimal tool operation sequence, schedule, and cycle time. We also extend a workload measure for cluster tools with reentrant wafer flows. Finally, we discuss how our results can be used for engineering a cluster tool. We compare two proposed strategies, sharing and dedicating, of operating the parallel processing chambers for identical process steps.     

Formal Approach of FMS Cyclic Scheduling

This correspondence is related to the determination of both control and scheduling of flexible manufacturing systems under cyclic command. Different approaches can be found in the literature, but we focus on those which respect the optimal throughput while minimizing the work in process. So, we recall methods of performance evaluation developed during the last 20 years. The last part is devoted to a new approach of cyclic scheduling using a Petri net. This method uses algebraic tools (dioids) developed for the study of marked graphs. In this way, the problem of the scheduling is progressively transformed into a problem of the search of solution(s) on a system of equations     

Scheduling of semiconductor test facility via Petri nets and hybridheuristic search

This paper proposes and evaluates two Petri net-based hybrid heuristic search strategies and their applications to semiconductor test facility scheduling. To reduce the setup time, such as the time spent to bring the test facilities to the required temperatures, scheduling multiple lots for each job type together is desirable. Petri nets can concisely model multiple lot sizes for each job, the strict precedence constraints, multiple kinds of resources, concurrent activities and flexible routes. To cope with the complexities for multiple lots scheduling, this paper presents two Petri net-based hybrid heuristic search strategies. They combine the heuristic best-first strategy with the controlled back tracking strategy based on the execution of the Petri nets. The obtained scheduling results are compared and analyzed through a small-size test facility. The better algorithm is also applied to a more sizable facility containing types of resources with a total of 79 pieces and 30 jobs. The future work includes the real-time implementation of the proposed method and scheduling results in real industrial settings     

Scheduling of mask shop E-beam writers

Reducing wafer fabrication cycle time and providing on-time wafer deliveries are among the top priorities of semiconductor companies. Mask manufacturing is essential to the overall wafer fabrication process since on-time delivery of masks significantly affects wafer fabrication cycle times. Moreover, delivering wafers on time means deliveries of masks must be on time as well. This research studies the scheduling problem of the bottleneck machine-the Electrical Beam (E-beam) Writer-of a mask shop. The criterion of minimum total tardiness is used as our performance measure to schedule this bottleneck operation. Using a predetermined Earliest-Due-Date (EDD) dispatch policy set by management, this study first addresses the problem of scheduling batches of a single mask size on a single machine. The approach is extended to the problem of scheduling batches of two mask sizes on a single machine; finally, a heuristic for a multiple-machine problem is developed. For the problem of a single machine under EDD dispatching policy, the problem can be formulated as a Dynamic Program (DP). Thus, it can be solved for an optimal solution in polynomial time. For the multiple machines problem, we heuristically allocate the masks to each machine. Each machine with allocated masks can then be solved by the DP formulation designed for the single machine problem. Based on the computational experiments in this study, the proposed DP approach reduces total tardiness by an average of 55% from the method currently in use at a major IC manufacturing foundry. Furthermore, in the case that due dates are set realistically, the DP approach reduces the tardiness about 95% from the shop's current method and about 88% from a simple full-batch method of scheduling     

A Petri Net Method for Schedulability and Scheduling Problems in Single-Arm Cluster Tools With Wafer Residency Time Constraints

With wafer residency time constraints for some wafer fabrication processes, such as low pressure chemical–vapor deposition, the schedulability and scheduling problems are still open. This paper aims to solve both problems. A Petri net (PN) model is developed for the system. This model describes when the robot should wait and a robot wait is modeled as an event in an explicit way. Thus, to schedule a single-arm cluster tool with wafer residency time constraint is to decide how long a robot wait should be. Based on this model, for the first time, we present the necessary and sufficient conditions under which a single-arm cluster tool with residency time constraints is schedulable, which can be checked analytically. Meanwhile, a closed form scheduling algorithm is developed to find an optimal periodic schedule if it is schedulable. Also, a simple method is presented for the implementation of the periodic schedule for steady state, which is not seen in any previous work.      

Modeling, analysis, simulation, scheduling, and control ofsemiconductor manufacturing systems: A Petri net approach

This paper presents a Petri net approach to modeling, analysis, simulation, scheduling, and control of semiconductor manufacturing systems. These systems can be characterized as discrete event systems that exhibit sequential, concurrent, and conflicting relations among the events and operations. Their evolution is dynamic over time. The system complexity is tremendous owing to the complex semiconductor manufacturing processes and test procedures. A formal approach such as Petri nets enables one to describe such complex discrete event systems precisely and thus allows one to perform both qualitative and quantitative analysis, scheduling and discrete-event control of them. This paper also serves as a tutorial paper. It briefly reviews applications of Petri nets in semiconductor manufacturing automation. It then introduces definitions and concepts of Petri nets. It proceeds with a discussion of basic Petri net modules in system modeling, a modeling method and a practical system's modeling example. Next, the paper presents their properties and their implications in manufacturing systems, as well as their analysis methods. Timed Petri nets are introduced for system simulation, performance evaluation, and scheduling purposes. An application-oriented case study is presented. Finally, the paper concludes with the active research areas in applying Petri nets to design of semiconductor manufacturing systems     

Multiobjective scheduling for IC sort and test with a simulationtestbed

In manufacturing environments such as an integrated circuit (IC) sort and test floor, typically more than one objective, such as cycle time and on-time delivery, needs to be simultaneously considered. With multiple objectives, a good solution is called Pareto optimal if it is not inferior to any other feasible solutions in terms of all objectives. The Pareto boundary is the set of all Pareto optimal solutions, which indicates the tradeoff of all good solutions. In this paper, a multiobjective model for IC sort and test is formulated, based upon the current information at any given instant. An approximate Pareto boundary can then be found using the Lagrangian relaxation method for the model. New algorithms are used to solve the dual problem and obtain feasible solutions from the associated subproblem solutions. The impact of the new scheduling approach on performance is illustrated through numerical examples by comparing it with corresponding single-objective problems and various heuristic dispatching rules. Its performance in dynamic and stochastic environments for real world applications is evaluated by using a simulation testbed. Simulation results definitely indicate a high potential for our approach