信息物理融合生产系统动态任务调度研究

金 阳，蒋增强，鄂明成

(北京交通大学 机械与电子控制工程学院，北京 100044)



信息物理融合生产系统动态任务调度研究

金 阳，蒋增强，鄂明成

(北京交通大学 机械与电子控制工程学院，北京 100044)

为使制造系统适应当前多品种、小批量市场需求，有关CPPS的生产系统构架和运行优化技术成为当前研究热点。首先通过分析CPPS的研究背景和任务调度现状，研究了CPPS的动态任务调度方法。该方法首先利用Petri网，建立了系统运行的逻辑模型；其次设计了系统中任务的表达形式和匹配方法，使得系统能够自动接受、分析并执行任务；再次为保证分布式系统的整体运行效果，设计了一种基于动态决策中心的双层决策模式，并对其中的运行指标和调度规则进行了说明；最后通过实例验证，证明了所提出的策略不仅可以满足系统的生产需求，而且能够保证各项指标的优化。

信息物理融合生产系统；动态任务调度；Petri网；双层决策模式

随着当今科学技术的快速发展，制造业正在面临变革，其中以德国提出的“工业4.0”为代表。“工业4.0”是以智能制造为主导的第四次工业革命，通过充分利用信息通讯技术和网络空间虚拟系统——信息物理系统(cyber-physical systems, CPS)相结合的手段，实现新的生产组织系统[1]，即信息物理融合生产系统(cyber-physical production systems, CPPS)。CPPS是一种利用CPS相关技术，依赖不同设备上的嵌入式设备，不断通过计算通信而形成并发式网络，从而在复杂生产环境和需求多变的情况下增加工业生产系统的灵活性和自适应性，实现现代工业制造的个性化、高效化的生产系统[2-4]。CPPS中，制造资源的自主性、生产任务的多样性和制造环境的不确定性不断增加，CPPS的任务调度模式将由集中式控制向分散式增强型控制转变。CPPS的运行和调度过程可描述为：系统自动接受并分析任务，通过混杂环境感知数据的分析、融合与挖掘，结合系统自身运行状态，制定合理的调度策略并依靠分布式节点自治协同地实施；同时，通过计算进程与物理进程相互影响的实时反馈循环，自主地协调物理进程[5]。如何处理不同设备间的协同关系，在不同的任务和目标下，有效地对不同系统和机构进行调度，是该生产系统面临的一个重要的挑战。

关于生产系统的调度，传统研究主要为集中式调度，方法较为成熟。典型的方法包括数学规划方法、启发式搜索方法、系统仿真方法、人工智能方法等[6]。以上相关方法，可以对CPPS中任务调度提供有益的借鉴，但不能完全适用于分布式系统。而当前一些分布式调度策略的研究中[7-9]，存在任务规模小且静态、任务类别和相关数据已知、任务分配方式单一等问题，无法满足CPPS中任务调度的需求。鉴于此，笔者将从系统运行逻辑模型设计、任务的定义和匹配方式设计、设备间的组织形式和调度策略设计这3个方面，进行CPPS中动态任务调度研究。

1 基于Petri网的逻辑模型搭建

Petri网最早由德国学者CARL博士于1962年在其论文中提出，其具有描述异步并发的能力[10]。相关学者已成功将Petri网应用于不同领域[11-12]，如路径优化、生产调度、流水线平衡等优化问题。鉴于此，笔者将采用Petri网进行逻辑模型的构建。

制造系统的运行流程可描述为：制造系统接收任务后进行任务分析，获取参数，选取可加工的任务，然后进行任务匹配，通过分配机制，将任务分配给合适的设备，设备执行生产任务，如果正常完成，则继续进行下一步任务，如果不能完成，则需重新进行任务分析和分配，如此往复，直至全部任务完成。系统运行流程如图1所示，运行逻辑Petri网如图2所示。

图1 系统运行流程图

图2 系统运行逻辑Petri网示意图

2 任务定义和匹配机制设计

2.1 任务定义方式

为了使制造系统自动执行工作，需要对任务进行识别，因此需要设计规范的任务输入形式：(工序编号，工序分类，紧前工序)。以机加工为例，将加工特征分为24类[13]，即有24个工序分类，编号为MF1～MF24。假定零件及其加工任务如图3所示，其对应的任务描述如表1所示。

图3 加工任务示意图

2.2 任务匹配方式

任务匹配即建立任务需求参数和设备功能参数之间的映射关系，建立任务需求的参数集合A=(a1，a2,…,an)，设备的参数集合B=(b1，b2,…,bn)，并建立两者之间的关联向量C={f1(a1，b1),f2(a2,b2),…,fi(ai,bi)}。其中fi(ai,bi)(i=1,2,…，n)表示参数ai和bi之间的匹配函数。

表1 任务输入示意表

仍以机加工为例,设集合A=(2 800,400,400,0.21,1.60)。一个铣床集合B的部分示例如表2所示。则两者间的关联向量为：

C={(a1≤b1),(a2≤b2),(a3≤b3),

(a4≥b4),(a5≥b5)}

表2 铣床参数集合示例

通过计算，最终匹配结果为编号“XA2010”的设备能够完成该任务。

3 CPPS的调度策略

3.1 基于动态决策中心的双层决策模式设计

制造系统中的智能设备依靠分布式节点自治协同地实施工作，需要设计智能设备间的组织形式；同时，为了保证制造系统整体以优化的状态运行，系统中需要有一个上层的调控者来保证整体的运行效果。为此，笔者设计了一种“基于动态决策中心的双层决策模式”，其示意图如图4所示。该模式分为调控层和决策执行层两层。调控层负责收集和统计当前系统和任务的相关信息，并计算出对应的指标，为决策执行层在每次决策时提供依据。决策执行层为各智能设备。每个智能设备均存在一个信息决策中心，任意两者间可实现互相通讯。

图4 基于动态决策中心的双层决策模型示意图

当出现新的任务时，首先将任务信息输入任务接收设备并将其信息决策中心激活，该中心将信息发送到相关设备，组成一个临时的决策中心，根据调控层当前发布的状态指标、各设备相关参数，进行分配工作；分配完毕后，该中心关闭，领取任务的智能设备的信息决策中心激活，进行任务并执行和上一层同样的信息发布和决策工作，直到任务全部完成。这样，调度决策的实施便由传统的集中式转化为分布式，每个执行任务的设备均是决策者，自发完成决策任务。

3.2 系统运行状态和评价指标

3.2.1 调控层监测指标

(1)

(2)

(3)

式中：tkij为工序Aij(任务i的工序j)在设备k上的加工时间；u表示工序Aij可以选择的设备总数；ESij为每个工序的最早开始时间；LFij为每个工序的最迟结束时间；Cap为某类工序同一时间的最大进行数量；EXPi为任务i的交货期。

3.2.2 决策执行层指标

3.3 任务分配策略

3.3.1 分配目标

笔者选取最大化加工质量和最小化加工成本与延期成本为目标，进行任务分配。因此，目标函数可以表示为：

Z={minC1,minC2,maxQ}

(4)

(5)

(6)

(7)

式中：di为任务i的完工时间；Pi为完工利润;αi为延期惩罚系数。

3.3.2 调度策略

调度分配的执行过程按照合同网的基本模式进行，即决策中心将任务以竞标的方式下达，不同设备对可以进行的任务进行投标；决策中心从当前调控层获取数据指标，计算不同设备的标值，选取合适的设备，将任务分配；若一台设备同时得到不同的任务，则根据投标倾向度选择任务签约，并将其他任务返回。此时决策中心重新计算各设备标值并发送签约意向，直到签约完毕。具体流程如图5所示。标值BVkij和投标倾向值BIkij的计算公式为：

(8)

BIkij=γ1×pij-γ2×Ckij+γ3×TLt+γ4×LDij

(9)

其中，为了使不同参数量纲一致，需要进行归一化处理，如式(10)所示。参数β1～β4则与系统中设备繁忙度和任务宽松度相关，总体原则为：设备负载率越高，β1和β2越小；任务越宽松，β3和β4越小。

(10)

图5 任务竞标流程图

4 实例验证

为了验证笔者所提供策略的有效性，现通过实例进行验证。设共有3种工种，5台设备，每台设备可以接受的工种、加工质量和单位时间成本如表3所示，且各设备处于待工状态。

表3 各设备相关参数

现有3个任务同时到达系统，各任务的具体信息如表4所示。每个工序的相关信息如表5所示，各任务的工序按照串行顺序进行。

表4 各任务相关信息

按照笔者所采取的策略，各工序的分配和执行结果如表6所示，3个任务的结束时间分别为45、50和50，均在交货期前完成。

表5 各工序相关信息

表6 分配和执行结果

在时刻10，工序1.1和工序2.1完工后，均需进行工种2，但只有设备5可用。按照获利公式计算，工序1.2和工序2.2的获利归一化后分别为0.81和1.00。因此在传统的合同网中，设备5将进行工序2.2，从而使工序1.2的最早开始时间变为20，这将造成任务1延期交货；而加入宽松率这一指标后，由于任务1的宽松率为0.86，较任务2的0.64更为紧迫，经过加权计算接标倾向，设备5选择工序1.2进行加工，从而保证了所有任务在交货期前完成。同样，在时刻31，工序3.3需要在设备1和设备4间进行选择，两个设备的质量、成本、等待时间和加工时间的归一化参数分别为(0.8,1.0,1.0,1.0)和(1.0,0.8,1.0,1.0)，相差较小，对于不同的权重取值，可能会导致不同的选择结果，如果选中设备4进行加工，则会推迟工序2.3的进行，从而造成其延期交货；由于加入了负载率这一指标，使得设备4的负载率明显大于1，从而最终选择了设备1，也保证了后面任务2在交货期前完工。

从以上分析可知，笔者所采用的双层决策模式，保证了每次决策时各参数的局部优化；同时上层的运行指标，也能有效协调分布式系统中局部优化和全局优化间的关系，使系统整体在一个优化的状态下运行。

5 结论

笔者结合当前制造业的发展趋势和特点，提出分布式智能制造系统的优势和实施的必要性。然后从系统运行逻辑模型、任务表达与匹配方式、系统运行与调度策略3方面进行了设计。为了解决分布式制造系统追求局部优化而忽略整体优化的问题，提出了一种基于动态决策中心的双层决策模式，使得系统能够以分布式的方式，自动接收、分析并分配执行任务。最终通过实例验证，证明了笔者所提出策略的有效性和优越性。

[1] 郑贤玲.工业4.0:为客户创造价值的思维模式[J].今日工程机械, 2014 (11): 66-67.

[2] MONOSTORI L. Cyber-physical production systems: roots, expectations and R&D challenges[J]. Procedia Cirp,2014(17):9-13.

[3] ANIS A, SCHAFER W, NIGGEMANN O. A comparison of modeling approaches for planning in cyber physical production systems[C]∥Emerging Technology and Factory Automation.[S.L.]： IEEE,2014:1-8.

[4] 鲁川.面向信息物理融合系统的实时时空调度算法[D].广州:广东工业大学,2013.

[5] 伦永亮.信息物理融合系统优化调度理论与方法的研究[D].广州:广东工业大学,2012.

[6] 徐俊刚,戴国忠,王宏安.生产调度理论和方法研究综述[J].计算机研究与发展,2004,41(2):257-267.

[7] PANESCU D, PASCAL C. Holonic coordination obtained by joining the contract net protocol with constraint satisfaction[J]. Computers in Industry, 2016, 81(C):36-46.

[8] YIN X F, LI P K, CHEN C H. A distributed agent system for port planning and scheduling[J]. Advanced Engineering Informatics, 2011, 25(3):403-412.

[9] 任海英,邹艳蕊.基于多Agent的柔性作业车间预先/重调度系统[J].武汉理工大学学报(信息与管理工程版),2012,34(1):69-73.

[10] 袁崇义.Petri网应用[M].北京:科学出版社,2013:12-13.

[11] 徐剑,叶文华,杨斌,等.基于扩展Petri网的飞机装配线建模及平衡方法[J].计算机集成制造系统,2015,21(10):2596-2603.

[12] 朱伟,徐克林,孙禹,等.Petri网融合蚁群算法的物流配送路径规划[J].浙江大学学报(工学版),2011,45(12):2229-2234.

[13] CHEN L, MACWAN A, CHEN L, et al. Optimal module selection for preliminary design of reconfigurable machine tools[J]. Journal of Manufacturing Science & Engineering, 2005,127(1):104-115.

[14] 于付龙,仲梁维,李阳.基于BP神经网络的焊接工时定额模型研究[J].现代制造工程,2014(4):17-21.

JIN Yang:Postgraduate;School of Mechanical and Electronic Control Engineering, Beijing Jiaotong University, Beijing 100044, China.

Dynamic Task Scheduling for Cyber-Physical Production Systems

JIN Yang, JIANG Zengqiang, E Mingcheng

Today’s market demands are with features of multi-product and small batch, to make manufacturing system meet this trend, the system architecture and optimizing technology on the operation of cyber-physical production systems (CPPS) has become research focus. After analyzing the background of CPPS and the research status of task scheduling, dynamic task scheduling method for CPPS is studied. Firstly, the logical model for system operation is built using Petri net. Then, the expression form of tasks and matching method with devices are designed, the method make system accept, analyze and execute tasks automatically. Secondly, to guarantee the overall operation effect of the distributed systems, a two-level decision model that based on dynamic decision center is designed, and the performance indicators and scheduling rules are described. Finally, through the example verification, it proves that the strategy proposed in this paper can not only meet the production requirements of the system, but also can guarantee the optimization of each index.

cyber-physical production systems; dynamic task scheduling; Petri net; two-level decision model

2095-3852(2017)03-0324-06

A

2016-12-29.

金阳(1991-)，男，河北沧州人，北京交通大学机械与电子控制工程学院硕士研究生，主要研究方向为制造与服务系统运行优化理论与技术.

国家科技支撑计划基金项目(2015BAF08B02)；中央高校基本科研业务费专项资金项目(2015JBM078).

TH186

10.3963/j.issn.2095-3852.2017.03.016