基于Petri网和基因表达式编程的作业车间调度研究

发布时间：2019-06-04 09:51

【摘要】：随着制造业发展，作业车间调度问题的实现过程也变得越来越复杂化。车间调度问题是一类集各约束条件的组合优化问题，对于该问题具有很实际的一个应用背景，因此该领域也一直是研究的热点，自上世纪80年以来，随着各学科领域之间的相互渗透，也出现了许多研究方法，并涌现了大量有价值的文献。可是该问题被证明是一个NP难问题，所以至今没有一个确定可行的解决方案，这也吸引了越来越多的学者对此进行研究，近几年也提出了很多具有重要意义的调度算法，这也激发了学者对调度问题研究的热情。在如此的背景下，车间调度问题的研究就成了更加具有意义的事情。就目前对调度问题的研究已经有十多种，其中对作业车间进行仿真建模有Petri网、控制等方法，本文选用了Petri作为作业车间调度问题研究建模工具，因为Petri网发展至今已有60多年的历史，是一个非常成熟的基于数学化的建模工具，基于Petri网的模型可以对调度系统进行实时的仿真。目前Petri网常对离散的事件进行分析和建模，根据Petri网功能选择可以对系统网集成建模。从此可以看出本文选用Petri网为车间调度的建模设计提供了便利。文中首先根据调度问题的描述利用时延Petri网对简单的车间调度问题进行建模，并随之提出了时间有色Petri网对复杂的调度问题进行了建模分析，通过本文提出的建模方法可以直观的看出复杂调度问题的调度情况，也验证了本文提出的建模理论是可行的。根据Petri建模后对基因表达式编程的编码进行设计，本文提出了不同于传统的基因表达式编程编码，，在本文算法中，基因表达式编程根据时延Petri网模型中的变迁序列来确立染色体的尾部，每条染色体尾部可以确立一种车间调度方案。本文选用了基因表达式的选择、交叉、变异三种类型进行遗传操作。其中交叉、变异操作也不同于原型Petri网，本文根据调度问题设计了特定的遗传操作。最后本文根据Petri网对车间调度问题的仿真，通过变迁的时延时间获得每条染色体的相应的时间，结合基因表达式编程具有较好的寻优能力和Petri网对动态的离散事件的过程能进行很好的描述的优点对仿真实例进行实验，最后通过实验数据的比较来验证本文所提出的算法的可行性。
[Abstract]:With the development of manufacturing industry, the realization process of job shop scheduling problem has become more and more complex. Job shop scheduling problem is a kind of combinatorial optimization problem with various constraints. It has a very practical application background for this problem, so this field has been a hot research topic since 80 years of last century. With the mutual penetration of various disciplines, there are also many research methods, and a large number of valuable literature has emerged. However, this problem has been proved to be a difficult NP problem, so far there is no definite and feasible solution, which has attracted more and more scholars to study it, and a lot of important scheduling algorithms have been proposed in recent years. This also arouses the enthusiasm of scholars for the research of scheduling problem. In this context, the research of job shop scheduling problem has become more meaningful. At present, there are more than ten kinds of research on scheduling problem, among which there are Petri net, control and other methods for the simulation modeling of job shop. In this paper, Petri is selected as the modeling tool for job shop scheduling problem research. Because Petri net has been developed for more than 60 years, it is a very mature modeling tool based on mathematics. The model based on Petri net can simulate the scheduling system in real time. At present, Petri net often analyzes and models discrete events, and the system network integration can be modeled according to the function selection of Petri net. It can be seen that Petri net is selected to facilitate the modeling and design of job shop scheduling. In this paper, according to the description of scheduling problem, the delay Petri net is used to model the simple job shop scheduling problem, and then the time colored Petri net is proposed to model and analyze the complex scheduling problem. Through the modeling method proposed in this paper, we can intuitively see the scheduling of complex scheduling problems, and verify that the modeling theory proposed in this paper is feasible. According to the design of gene expression programming after Petri modeling, this paper proposes a gene expression programming coding which is different from the traditional gene expression programming coding. In this algorithm, Gene expression programming establishes the tail of chromosome according to the transition sequence in delay Petri net model, and a job shop scheduling scheme can be established at the tail of each chromosome. In this paper, three types of genetic expression, crossing and variation, were selected for genetic operation. The crossing and mutation operations are different from the prototype Petri net. In this paper, a specific genetic operation is designed according to the scheduling problem. Finally, according to the simulation of job shop scheduling problem by Petri net, the corresponding time of each chromosome is obtained by the transition delay time. Combined with the advantages of gene expression programming, which has good optimization ability and Petri net can describe the process of dynamic discrete events, the simulation example is tested. Finally, the feasibility of the proposed algorithm is verified by comparing the experimental data.
【学位授予单位】：广西师范学院
【学位级别】：硕士
【学位授予年份】：2014
【分类号】：TP301.1;TB49

【共引文献】