CN109902403A - 一种基于Petri网和启发式值的综合调度方法 - Google Patents

Abstract

本发明提出一种基于Petri网和启发式值的综合调度方法。所述方法将加工产品的设备对应Petri网结构中的库所，产品的工序对应Petri网结构中的变迁，将启发式值赋予token，完成触发变迁，从而实现综合调度。所述方法在遵循复杂产品调度问题中层优先原则的前提下，充分兼顾了产品工艺树中横纵的并行问题，通过优先调度同级叶节点和加工用时短工序的策略，进一步充分利用了设备的空闲时间，为解决一般复杂产品的综合调度提供了一种新的方法。

Description

一种基于Petri网和启发式值的综合调度方法

技术领域

本发明属于计算机集成制造技术领域，特别是涉及一种基于Petri网和启发式值的综合调度方法。

背景技术

产品制造的调度问题是影响制造业生产效率的重要因素，在企业设备、资源等条件固定的前提下，调度的效率直接决定了企业的生产效率。为了更好的解决小批量、多品种生产的调度问题，有专家学者提出了将产品的加工和装配一同处理的综合调度，并开展了一系列的研究，产生了诸多调度算法，也拓展出很多新的研究领域。比较有代表性的诸如基于拟关键路径的综合调度算法、可动态生产具有优先级的算法、考虑后续工序择时算法等。但是基于拟关键路径的综合调度算法只注重产品树状结构的纵向忽略横向影响调度结果的问题；可动态生产具有优先级的算法，在纵横兼顾的基础上进一步优化了纵向调度，但是采用动态思想的算法忽略了由于设备空闲等制约因素导致的紧前紧后工序之间衔接较差的细节问题；考虑后续工序择时算法，虽然考虑了工序间紧前紧后工序的制约关系，也考虑到了串行和并行工序对调度工序的整体影响，但同样忽略了对空闲设备的充分利用。

发明内容

本发明目的是为了解决现有技术中的技术问题，提出了一种基于Petri网和启发式值的综合调度方法。

本发明是通过以下技术方案实现的，本发明提出一种基于Petri网和启发式值的综合调度方法，具体包括以下步骤：

步骤一、将加工产品的设备对应Petri网结构中的库所，产品的工序对应Petri网结构中的变迁，将启发式值赋予token以完成触发变迁；

步骤二、绘制包含加工产品的设备、产品的工序和该工序的加工时长信息的工艺树；

步骤三、计算工艺树中各个节点的优先级；

步骤四、根据启发式值的设定规则和各个节点的优先级完成产品调度。

进一步地，所述工艺树中的各个节点即为产品的各个工序。

进一步地，设产品加工工艺树有n层，则将根节点工序的优先级定义为1，其所有子节点工序的优先级定义为2，以此类推，直到第n层的所有节点的优先级定义为n。

进一步地，所述步骤四具体为：

步骤a、规定工艺树中根节点工序的优先级最低，第n层上工序的优先级最高；判断优先级最高的层中的节点是否唯一，如果唯一，则认为该节点优先级最高，且优先调度，之后进行优先级次之的工序调度，重复步骤a；如果不是唯一，则转入步骤b；

步骤b、确定了各工序的优先级之后，如果存在优先级相同的工序，则判断工序序列中是否存在叶节点，如果存在且唯一，则优先调度，同层中其他工序的调度重复步骤b；如果存在但叶节点不唯一或不存在，则转入步骤c，同层中其他工序的调度重复步骤b；

步骤c、如果工序优先级相同，则优先调度自身加工用时短的工序；

步骤d、重复步骤a-步骤c直至所有加工工序调度完毕。

本发明有益效果：本发明所述方法不仅继承了Petri网高效仿真、复杂度小的优点，而且以层优先原则为主导，在尽早开始调度复杂产品的前提下，充分兼顾了产品工艺树中横纵的并行问题，最大限度的利用了设备的空闲时间，从而缩短了产品加工的总工时，从而在企业设备、资源等条件有限的前提下提高了生产效率。因此本发明所述方法为解决一般复杂产品的综合调度提供了一种新的方法，并为进一步深入研究综合调度拓展了思路，具有一定的理论和实际意义。

附图说明

附图1为本发明所述基于Petri网和启发式值的综合调度方法的流程图。

附图2为产品A加工工艺树图。

附图3为产品A的Petri网建模图。

附图4为产品A的Petri网仿真结果图。

具体实施方式

下面将结合本发明实施例中的附图对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例仅仅是本发明一部分实施例，而不是全部的实施例。基于本发明中的实施例，本领域普通技术人员在没有做出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。

结合附图1，本发明提出一种基于Petri网和启发式值的综合调度方法，具体包括以下步骤：

步骤一、将加工产品的设备对应Petri网结构中的库所，产品的工序对应Petri网结构中的变迁，将启发式值赋予token以完成触发变迁；

步骤二、绘制包含加工产品的设备、产品的工序和该工序的加工时长信息的工艺树；

步骤三、计算工艺树中各个节点的优先级；

步骤四、根据启发式值的设定规则和各个节点的优先级完成产品调度。

所述工艺树中的各个节点即为产品的各个工序。

设产品加工工艺树有n层，则将根节点工序的优先级定义为1，其所有子节点工序的优先级定义为2，以此类推，直到第n层的所有节点的优先级定义为n。

所述步骤四具体为：

步骤a、规定工艺树中根节点工序的优先级最低，第n层上工序的优先级最高；判断优先级最高的层中的节点是否唯一，如果唯一，则认为该节点优先级最高，且优先调度，之后进行优先级次之的工序调度，重复步骤a；如果不是唯一，则转入步骤b；在产品实际调度过程中调度优先级最高的工序，就意味着最早开始加工约束力强的紧前工序。

步骤b、确定了各工序的优先级之后，如果存在优先级相同的工序，则判断工序序列中是否存在叶节点，如果存在且唯一，则优先调度，其目的是提高设备的利用率，同层中其他工序的调度重复步骤b；如果存在但叶节点不唯一或不存在，则转入步骤c，同层中其他工序的调度重复步骤b；无论工序节点在哪一层，只要没有紧前工序的节点，均视为叶节点。

步骤c、如果工序优先级相同，为了提高工序间的紧密度，则优先调度自身加工用时短的工序；

步骤d、重复步骤a-步骤c直至所有加工工序调度完毕。

本发明提出了一种基于Petri网和启发式值的综合调度方法，将加工产品的设备对应Petri网结构中的库所，产品的工序对应Petri网结构中的变迁，将启发式值赋予token，完成触发变迁，从而实现综合调度。所述方法在遵循复杂产品调度问题中层优先原则的前提下，充分兼顾了产品工艺树中横纵的并行问题，通过优先调度同级叶节点和加工用时短工序的策略，进一步充分利用了设备的空闲时间，为解决一般复杂产品的综合调度提供了一种新的方法。

以附图2所示复杂产品A为具体实例，本发明所述方法的调度过程如表1所示。

表1 本发明所述方法调度过程

上述调度具体过程为：

步骤1.按照附图2所示的产品A工艺图，确定产品A的各个工序的优先级，共有6级，其中工序A11的优先级为6，级别最高；工序A7、A8、A9、A10的优先级同为5，排在第二位；工序A5、A6的优先级同为4，排在第三位；工序A3、A4的优先级同为3，排在第四位；工序A2的优先级为2，排在第五位；根节点工序A1的优先级最低，为1，排在第六位；

步骤2.遍历产品A之后，优先级最高的6级工序只有A11，所以调度A11；

步骤3.优先级次之的5级工序有4个，所以判断这些工序是否存在叶节点；

步骤4.同为5级的A8、A9、A10均为叶节点，所以根据加工用时最短的原则确定调度工序顺序为A8、A9、A10，至此产品A的调度顺序为A11、A8、A9、A10、A7；

步骤5.同理确定优先级为4的工序调度顺序为A6、A5；优先级为3的工序调度顺序为A3、A4；

步骤6.最终确定产品A的调度顺序为A11、A8、A9、A10、A7、A6、A5、A3、A4、A2、A1。

与前文中所述的拟关键路径算法、可动态生产具有优先级的算法、考虑后续工序择时算法相比较，本发明所述方法有明显提高，如表2所示。

表2 四种方法的调度过程时间对比

根据Petri网的基本性质和上述分析可得产品A的Petri网模型，在PlatformIndependent Petri Net Editor V4.3上建模结果如附图3所示、仿真结果如附图4所示。

网建模中，库所P1对应三个变迁：T7、T10、T2，具体作用分别是为T10的起始库所、T7和T2的加工库所。库所P2对应五个变迁：T11、T9、T5、T4、T1，具体作用分别是T11的起始库所、T9、T5、T4的加工库所和T1的结束库所。库所P3对应三个变迁：T8、T6、T3，具体作用分别是为T8的起始库所、T3和T6的加工库所。各库所、变迁的对应关系如表3所示。

表3 Petri网模型各库所与变迁对应关系

以上对本发明所提供的一种基于Petri网和启发式值的综合调度方法，进行了详细介绍，本文中应用了具体个例对本发明的原理及实施方式进行了阐述，以上实施例的说明只是用于帮助理解本发明的方法及其核心思想；同时，对于本领域的一般技术人员，依据本发明的思想，在具体实施方式及应用范围上均会有改变之处，综上所述，本说明书内容不应理解为对本发明的限制。

Claims (4)

1.一种基于Petri网和启发式值的综合调度方法，其特征在于：具体包括以下步骤：

步骤一、将加工产品的设备对应Petri网结构中的库所，产品的工序对应Petri网结构中的变迁，将启发式值赋予token以完成触发变迁；

步骤二、绘制包含加工产品的设备、产品的工序和该工序的加工时长信息的工艺树；

步骤三、计算工艺树中各个节点的优先级；

步骤四、根据启发式值的设定规则和各个节点的优先级完成产品调度。

2.根据权利要求1所述的方法，其特征在于：所述工艺树中的各个节点即为产品的各个工序。

3.根据权利要求2所述的方法，其特征在于：设产品加工工艺树有n层，则将根节点工序的优先级定义为1，其所有子节点工序的优先级定义为2，以此类推，直到第n层的所有节点的优先级定义为n。

4.根据权利要求3所述的方法，其特征在于：所述步骤四具体为：

步骤a、规定工艺树中根节点工序的优先级最低，第n层上工序的优先级最高；判断优先级最高的层中的节点是否唯一，如果唯一，则认为该节点优先级最高，且优先调度，之后进行优先级次之的工序调度，重复步骤a；如果不是唯一，则转入步骤b；

步骤b、确定了各工序的优先级之后，如果存在优先级相同的工序，则判断工序序列中是否存在叶节点，如果存在且唯一，则优先调度，同层中其他工序的调度重复步骤b；如果存在但叶节点不唯一或不存在，则转入步骤c，同层中其他工序的调度重复步骤b；

步骤c、如果工序优先级相同，则优先调度自身加工用时短的工序；

步骤d、重复步骤a-步骤c直至所有加工工序调度完毕。