文档库

最新最全的文档下载
当前位置:文档库 > 基于Petri网的多工艺方案优化

基于Petri网的多工艺方案优化

基于Petri网的多工艺方案优化

吴 忠

 

文章编号:1003-8728(2000)05-0767-03

基于Petri网的多工艺方案优化

吴 忠,郭 蕾,孙树栋

(西北工业大学CIM S研究所,西安 710072)

摘 要:以扩展的Pet ri网模型PP-net为工具确定可行工艺方案的制造成本,P P-net的

每个变迁中含有加工时间、准备时间、搬运时间和更换刀具时间,由此可以得到工序

制造成本评价函数。利用启发式搜索算法对PP-net的可达树进行搜索,得到制造成

本最低的工艺方案。

关 键 词:Petr i网;CAP P;制造成本;优化

中图分类号:T H391.72 文献标识码:A

1 工艺规划Petr i网(PP-net)[1]

定义:一个Petr i网N=[P,T,F,M0]是一个P P-net

(P ro cess P lanning net)iff:

(1)P是网中库所的集合,库所代表了零件特征之间的

几何约束和可选择的加工方法。

(2)T是变迁的集合,变迁代表了加工操作。

(3)F是连接库所和变迁的有向弧的集合。

(4)N是一个具有两个特殊库所(P start和P s to p)和两个

特殊变迁(T start和T stop)的安全PET R I网,P start是源库所,

它没有输入变迁,且t start是其唯一的输出变迁。库所t stop是

一个终止(sink)库所,它没有输出变迁,且t s to p是其仅有的

输入变迁。

(5)F∩F-1= ,即网是非闭环的或部分有序的。

(6)m0是初始标识,P P-net运行之前只有一个to ken

在P start中,其它库所中无to ken。

(7)m f是终止标识,当仅有一个to ken在P stop中时,

PP-net的运行结束,它是网的唯一终止端。

PP-net的运行就是从初始标识m0到终止标识m f的变

迁顺序引发的过程,P P-net的可达树表示所有可行的工艺方

案,可达树的每一结点代表制造过程中工件所处的状态。上述

PP-net模型可以根据输入的工艺规划数据自动生成[2]。

2 用PP-net表示的工件制造成本模型

为了建立工艺规划的成本模型,不考虑刀具消耗,可以将工

件的制造成本分为四类:(1)纯加工成本,由独立的机加工操作

所消耗的时间决定;(2)工件从一台设备搬运到另一台设备的成

本;(3)设备的准备时间所需成本;(4)更换刀具的成本。

工件的制造成本信息存储于变迁中。设当前工序所在

的设备是M s,下一道工序O i将在设备M j上执行。设备M j

目前的准备时间是S j v,使用的刀具是T j w,工序O i在设备

M j上的准备时间为S j k,使用的刀具为T j r,则可以计算出

工序O i的总制造成本为

Co st[O i]:=op Cost[i]+m Co st[s,j]+

s Cost[j,v,k]+t Cost[j,w,r](1)

式中,op Co st[i]是工序的加工成本,m Co st[s,j]为把工件

从设备M s运送到设备M j的成本,s Cost[j,v,k]为将设备

M j的准备时间由S j v调整为S j k所消耗的时间,t Co st[j,w,

r]为设备M j上刀具由T j w变换为T j r的成本。

3 启发式搜索算法

3.1 估价函数

PP-net是对单个工件进行工艺方案优化的有力工具。K ir-

itsis[2]等首先建立工艺方案的PP-net模型,然后按宽度优先算

法对可达树进行搜索,再运用一定的方法选择制造成本最低的

工艺方案,当工件较为复杂时,庞大的可达树使算法的效率急剧

降低,因此需要利用启发式搜索技术提高算法的效率。

启发式算法用估价函数对P P-net可达树的结点进行

评价,选择全局最优的结点优先进行扩展。

可达树的每个结点no de与PP-net网的一个标识相对

应,估价函数f(m)评价结点node在求解问题的搜索过程

的代价,需要考虑两方面因素:即已经付出的代价g(m)和

将付出的代价h(m),则

f(m)=g(m)+h(m)(2)

式中,g(m)为从初始标识m0到标识m已经付出的代价,h

(m)为从标识m到终止标识m f的代价估计。g(m)过大,则

搜索过程倾向于宽度优先搜索,可提高搜索过程的完备性,

但降低了启发性,搜索效率降低;h(m)过大则搜索过程倾

向于深度优先搜索,能充分利用启发性知识,可提高搜索效第19卷 第5期

2000年 9月

机械科学与技术

M ECHA N ICAL SCIEN CE AN D T ECHN O L OG Y

V ol.19 N o.5

Sep 2000

收稿日期:19990518

 基金项目:航空科学基金(96H53105)和863计划(863-511-44-009-98)资助项目

作者简介:吴 忠(1968-),男(蒙族),陕西西安市人,西北工业大学博士研究生

率,但降低了搜索过程的完备性。

定义f(m)是从初始标识m0经过标识m到终止标识m f 的制造成本最低路径的代价,f*(m)是f(m)的估计值,即

f*(m)=g*(m)+h*(m)(3) 可证明,若h*(m)取h(m)的下界,即对于所有的结点m有h*(m)≤h(m),则利用A*算法一定能够找到由初始结点标识m0到终止标识m f的最优路径。

用{O1,O2,...,O m}表示制造过程当前已执行工序的集合,用{O(1)m+1/…/O(i)m+1,…,O(1)t/…O(j)t}表示可选择的尚未开始执行的工序集合(对应于未引发的变迁),其中“/”表示逻辑或关系,以h*(m)表示工件制造过程尚未执行的所

有工序的加工成本之和的最小值,即

g*(m)=Cost[O1]+…+Cost[O m](4)

h*(m)=min(Co st[O m+1/O′m+1/O″m+1]

+…+Co st[O t/O′t])(5) 如果Cost[O′m+1]≤Cost[O m+1]≤Cost[O″m+1]且Co st [O t]≤Cost[O′t],则

h*(m)=Cost[O′m+1]+…+Co st[O t](6)由式(6)得到的h*(m)是根据事先输入的工序序列得到的,而不是由于PP-net顺序引发而产生的,因此与式(5)对应的工序序列不一定是可行的,但h*(m)是实际最少剩余工序加工成本h(m)的一个下界,即满足

h*(m)≤h(m)(7) 因此估价函数f*(m)满足A*算法的要求,能够找到最优解。

3.2 启发式搜索算法

对于多工序的复杂零件,其P P-net的可达树很庞大,可以利用估价函数h*(m)构造一种启发式算法,该算法只产生部分可达树就可以找到成本最低的工序序列,以下是对该启发式算法的描述。

在P P-net运行之前,首先需要做如下的初始化:

current Stat e:=(ini t ialOperat i o nSta te,(i nitialMachine,(initialSetup[i], initialT oo l[i])))

initialOperationStat e:=NIL,初始化工序状态

initialMa chine i:=NIL,初始化设备状态

initialSetup[i]:=NIL,初始化设备准备时间

initialT oo l[i]:=NIL,初始化刀具集

Co st[c urrent St ate]:=0,将制造成本置为零

no de:=(currentSt ate,Cost[currentSta te]),可达树的结点

unpro cessedNo des:={(no de)},未加工结点集

pro c e ssedNodes:={},已加工结点集

算法如下:

step1建立两个表:unprocessedNodes表和processedN odes表,把初始标识m0和估价函数f(m0)放入unpro cessedNo des表,processedNodes表初始为空。

Step2若unprocessedN ode s表为空则退出。

Step3从unprocessedNo des表中移出一个未加工结点的标识m放入pro cessedNodes表。

Step4若m是终止标识m f,则建立由初始标识m0到终止标识m f的最

基于Petri网的多工艺方案优化

基于Petri网的多工艺方案优化

基于Petri网的多工艺方案优化

优路径然后退出,否则继续。

Step5找出标识m使能的变迁O i,并计算新的系统状态new St ate和Cost[O i]。

St ep6对每个使能的变迁产生后继标识m′。

St ep7对每个标识m′作以下的工作:

(1)按式(1)、(4)和(6)计算f*(m′)。

(2)如果m′既不在unprocessedNodes表中也不在pro cessedNo des表中,把它添入unpro cessedNo des表中,并建立从m′指向m的指针。

(3)如果m′在unprocessedNodes或processedN odes表中,则比较原来的f*(m)值和新计算的f*(m′),确定是否要修改指针,如果f*(m)>f* (m′),且m′已在pro cessedNo des表中,则将其移回unprocessedNodes表中,将unprocessedN odes表中的f*(m)修改为f*(m′)。

St ep8按f*(m)增大的顺序重排unprocessedN odes表。

St ep9转向Step2。

图1 示例零件

4 算例

以图1所示的零件来说明

PP-net的建立与多工艺方案的

优化过程。首先根据零件特征信

息建立特征关系表如表1所示。

表1 工序特征与加工方法

特征名

工序

代号

预加工

工序代号

加工

方法

设备

代号

刀具

代号

加工时间

(时间单元)

左端面01车M1T180

中心孔0101 01钻M1T220

圆柱面0201车M1T1200

键槽020102铣M2T3120

圆柱面0301and06车M1T1350

环槽0403车M1T490

端面030102and03车M1T170

端面030203and04车M1T170

圆柱面0506车M1T1150

右端面06车M1T1100

中心孔060106钻M1T220根据表1可以生成如图2所示的加工顺序与/或图。

图2 加工顺序与或图

由图2可以得到示例零件的PP-net模型如图3所示。

图3示例零件的PP-net模型

除表1列出的纯加工成本外,再定义如下类型的成本:

(1)改变加工设备的成本,工件从一台设备输送到另一台设备花费40时间单元。

(2)准备时间,改变加工工序将耗费准备时间5时间单元。

768机械科学与技术第19卷

(3)刀具更换时间,每次换刀耗费1时间单元。

对示例零件的PP-net可达树利用本文提出的启发式搜索算法,可以得到如表2所示的最优工艺方案。

表2 最优工艺方案

序号1234567891011

工序代号01060101060103020503010302040201

准备时间00505000005

换刀

时间

00101000001由表2可知加工过程共换过3次刀具,使用了两种型号的设备。通常,最优的工艺方案是使用最少的机床种类、准备时间和刀具类型。

5 结论

利用本文提出的启发式算法,对示例零件进行求解,得到了制造成本最低的工艺方案,这对于复杂零件的多工艺方案优化,降低制造成本有积极的意义。

[参考文献]

[1] Xirouch ak is P,et al.A Petri net T ech nique for Process

Plannin g C os t E stimation[A].Annals of the CIRP[C].

1998,47(1):427~430

[2] Kirits is D,et al.A Generic Petri Net M odel for Dynamic

Process Planning and S equence Optimisation[J].A dvances

in Engineer ing S oftw are,1996,25:61~71

[3] 董明等.基于时间Petri网和启发式搜索的FM S调度方法

[J].1997,10(2):167~170

[4] 邓超等.基于设备环境的多工艺方案决策[J].华中理工大学

学报,1997,25(3):11~13

[5] 郭蕾.基于Petri网的FM S建模和分析[D].西安:西北工业

大学,1998

Petri-Net-Based Cost Optimization for Alternative Process Planning WU Zhong,GUO Lei,SU N Shu-dong (N or thwester n Po ly technica l U niv ersity,Xi′an710072)

Abstract:I n pr ocess planning,it is im po rta nt to calculate ov era ll manufacturing co st o f each alter nativ es.A new method based on P etri net,w hich repr esents manufact ur ing co st in the for m of machining,setup, tr ansfer and to ol changing info rmat ion in each tr ansi-tio n,is pr esent ed.A Pet ri-net-based co st ev aluat ion function has also been pr esented.A heur istic algo-rithm has been ado pt ed to achieve pro cess planning w ith the low est cost.

Key words:Petr i net,CA P P,manufactur ing co st,o pt i-mizat ion

(上接第766页)

5 结束语

本文采用超磁致伸缩材料,设计出了机械加工微位移机构,可精确实现精密机床的微进给和定位;采用恒流源电路驱动,同时采用等速率双拍校正的控制思想,使功率脉冲幅度由最小节拍校正为稳态时的12.55倍减小到采用等速率双拍校正时的7.22倍。应用稀土超磁致伸缩材料设计的活塞非圆截面加工控制系统,在温州活塞机床厂从1996年2月起稳定运行至今。

研究结果表明,采用超磁致伸缩材料构成的微位移机构及其控制系统,有广阔的应用前景。

[参考文献]

[1] 刘金凌等.中凸变椭圆活塞数控车削技术[J].组合机床与加

工自动化,1994(4)

[2] 邓中亮等.用直线电机作刀具进给驱动车削变椭圆形活塞的

研究[J].内燃机学报,1994(2)

The Mechanism Design of Micro-displacement Actuator for Preci-sion Non-circular Cutting

L U Fu-zai,XIANG Zhan-qing,

QI Zong-jun,CHENG Yao-dong

(Zhejiang U niver sity,Hangzhou310027)

Abstract:T he design and implementatio n of the actuato r and its digit al co ntr o ller fo r milling w or kpieces w ith non-cir cular cr oss sect ion is presented.T he actuato r mechanism design,tr ansfer function and dy nam ic r e-spo nse char acterist ics w ere also discussed.Bo th the theor y and m ethod of dead-beat cor rection and mult i-ple-beat-same-v elo city co rr ectio n with the aid of co m-puter w er e inv est ig ated.T he computer aided clo sed loo p cor r ect ion system w as used in the exper iments of imitation tr acking the displa cement signal of a milling machine spindle.U sing the multiple-beat-same-veloc-ity co rr ectio n,which is put for w ard by us,t he mag ni-tude o f the pow er pulse is decr eased fro m12.55times of t he sta ble mag nitude(dead-beat cor r ect ion)to7.22 tim es.

Key words:N on circular cutt ing;D ynamic response char-acter istic;M agneto strict ive ma terial

769

第5期吴 忠等:基于P et ri网的多工艺方案优化