快速平衡技术

系统工程与电子技术91104日资源系统系统工程与电子技术，数字化期刊WANFANG DATA ( CHINAINFO)SYST EMS ENGINEERING AND ELECT RONICSDIGI1999 V ol.21No.11P.11-17,22快速平衡技术熊中楷里奇曼摘要存储管理是工业工程的一个重要研究领域。在国际上首先对单机器生产系统循环投放的特性进行研究,给出快速进入最优轨线的方法和步骤,以及储存空间任意一点快速进入最优轨线时间的计算公式。主题词存储管理最优设计系统稳定性Quickly Balance T echnologyXiong ZhongkaiCollege of Business,Chongqing University, 515063LeachmanIndustrial Engineering and Operation Research Department, UC Berkeley, CA 94720,USAAbstract T his paper discusses the characteristic 0 f round- Brobin policy for the single machine, multi-item production system. We find and provea real optimal buffer trajectory (corresponds minimum cost)whic h is independent on initial inventory. We have a formula to caclulate the time f rom any initial point tothe optimal buffer trajectory. .Keywords BallanceStableOptimal trajectory Fac tory automation1引言存贮管理是工业工程的一个重要研究领域。存储控制的运筹模型可以追溯到本世纪初[8],到目前为止发表的有关论文已有数千篇,根据美国总统1995年经济报告,美国的存储总值超过万亿美元[7]。近年来,许多研究人员对从制造系统的稳定性来研究存储很有兴趣,例如在文献[1~6]中,特别是Perkins和Kumar [ 4]对几种策略的特性进行了深入的研究(由美国国家科学基金会和美国军方资助) ,给出了-系列可靠的结果。在国际上本文首次对单机器生产系统循环投放的特性和最优轨线进行了研究,并给出存储空间任意- -点到达最优轨线的时间计算公式。粗略地讲,对一个给定单机器多产品生产系统(见图1所示) ,给定加工零件供给率、生产率,从一个零件转换为另-个零件的转换时间、转换费用及存储费用,对应于给定的循环策略可以求出最优周期,它对应于最低费用。本文要回答的问题是:当最优生产周期等于平衡生产周期时,什么是对应最少费用的最优存储水平?对存储空间的任何一点,如何快速控制系统进入最优轨线?如果-个干扰出现,如机器故障等使系统偏离最优轨线,如何快速控制系统?如何使系统稳定地运行于最优轨线,从而节省费用?中国煤化工MHCNMH G头MCINE]--一年fle:/// Vqkx99991104.htom(第1/ 18页) 2010-3-23 12:01:49系统工程与电子技术991104图1单机器多产品生产系统2符号与主要结论我们定义如下符号:i--零件标号, i∈N={,2... ,n};Cδ ir-在采用循环策略δ j时转换机器,以加工第1种零件所需时间, i∈Nj∈M={1,2, .. ,m}, .m=n!,Cδ ji=C;;p8 i--采用循环策略δ j时,第i种零件的生产率, Pδ ji=P;i∈Nj∈M ;Sδ i--采用循环策略δ时,第i种零件的平均供给率, Sδ ji= S;i∈N,j∈M ;I(G,8 }(t)--采用循环策略δ ;时,第G周期第i种零件在时刻的存储水平10.)(1)= (19092)(1)Iδ i()--采用循环策略δ j时,第i种零件在时刻的存储水平, *()= (p(r)(2(,../(1)”.1，V i∈N .(t)=r'(t);F(G,8 }()--采用循环策略δ ;时,在第G周期完成零件1到零件i所用的累计时间,本文假定零件不间断加工, i∈Nj∈M ;Fδ j-采用循环策略δ ;时,完成零件1倒零件i所用的累计时间;T*-最优生产时间;T*S jir采用循环策略δ ;时,第i种零件的最优加工时间;Bn--n维存储空间;t*--采用循环策略j时,对给定的初始存储状态到达最优轨线的最快时间;t--对给定初始存储状态到达最优轨线的最快时间1" = min{t; )h--第i种零件单位时间的存储费用;A--转换加工零件i所需时间;m:--两次加工零件i相隔的基本周期数。在给出本文的定理前,我们还给出一些定义。定义1对一 一个制造系统,如果存在常数，整数m≥0,使得.I:(Ts+mTJ)=I(T),i∈N (1)我们称这个制造系统是平衡的(从时刻T起) ,称T是平衡生产周期(如图2所示)。中国煤化工MHCNM HGfle:/// Vqkxcg9919991104.htm(第2/ 18页) 2010-3-23 12:01:49系统工程与电子技术991104图2理解平衡生产周期定义定义2如果制造系统是平衡的,并且有最低存储水平,我们称这个制造系统处于理想平衡,称点I*∈B^理想存储点。现在我们给出本文的一些主要结论。定理1对一个多产品单机器生产系统,采用循环策略的理想平衡条件是习异+2骨=1 (2)其中T*=T*,vi∈N,T*=Tc,并且gj∈M,使得1(0)= 1=Ix-[B,+C]S，i∈N(3)其中...=尚)Ti(P-S/)=则.+C/+[/*(0)+(F 1+C;9S9]/(4)(P%- S°),i∈N阶=0证明首先 ,我们证明1≥0oT.(P%-S))-=TSp-2c>+ 2r.JS)=[2c+ 2兴T.JS, -六S2.t20+2 r]Sy≥0在时间[0,Tc] , 零件i的总投入量为TSδj,i∈N。其中生产时间为S1m加果机器中国煤化工不饥饿,则产品量应为TYHCNM HGfle:/// Vqkxcg9919991104.htim(第3/ 18页) 2010-3-23 12:01:49系统工程与电子技术991104(哥T"PI=S!T"这里假设机器不饥饿,并且19(T)=1<0)= Py,i∈N。.在时刻附，+C/..开始加工零件i ,这-时刻总的零件存储应该为P:+(P.+C)Si=1m=(尚T:(PI,-S%).Sδi在时刻刊9.,零件i的总存储量正好为0 ,如果不生产,则零件i总存储量为|T:s=())T:(Pl,- S%>) +(器)rT:Sp= S;T:因此系统平衡处于最少存储水平,如图3所示。(b)图3理解定理1及其证明由定理1可得如下推论。Sc,(5)1--注:对于循环策略,理想平衡系统的平均存储量不依赖于循环方式的选择，因为在时间区[0,Tc]内,零件i的平均存储_ 17 T这个量不依赖于δ的选择。定义3我们称一个周期为T的生 产系统是平衡的,当且仅当tP;≥TS.这里t是生产时间。中国煤化工定理2对于一个循环策略,设T是周期MHCNMH G .fle:/// Vqkxcg9919991104.htm(第4/ 18页) 2010-3-23 12:01:49系统工程与电子技术991104Sc+实(分)r其中a)r.是零件i的加工时间,则这个周期为T的生产系统是平衡的必要条件是T0≥Tc证明由于该生产 系统是平衡的,则有S)TP2T"Sa2元_Tr-2c+名(号)r.=1r-之c，.r°T斗(务)r因此1-2(部定理2的推论:对于循环策略, T0定义同定理2, a(头T是零件i的加工时间,则a≥1。定义4我们称一 一个点集Q(δ )C B"为一个理想点集(如图4所示) ,对给定的循环策略,任何一个点Iδ(t)∈∩(δ ) , 存在一个时刻O t,T c2O t≥0,使得Iδ (t+O t)=I*。设Q'= {1∈B*|I≤j9,i∈N}对于n种零件,令m=n!,Q=0; U∪.∪mCBn中国煤化工MHCNM HGfle:/// Vqkxcg9919991104.htm(第5/ 18页) 2010-3-23 12:01:49系统工程与电子技术991104图4理想点集定义3低速方法(低速技术)如果存在δ j∈M ,使得*<0)≤79.ie N.(R,= o)即是说每种零件初始存储不大于理想存储量,则从前一种零件生产结束时刻起,转换生产这种产品,加工完这批零件的时间将不大于理想的累记结束时间，即附+C/+19<0)+(附:+C)SY刷，門-Si∈N在时间区[P2:+C>+1,/+ (FiL +C%)S%,F门Pis-Sp使生产率正好等于需求率Sδ j(Sδ j●Fm_ -0,)-1= min {F. -0e,)-1 | 19 (0)∈02.j∈”。中国煤化工定理6.2<24Q的充分必要条件是Fn 402+<2cx习号)<2in)a-2号)事实上I,(F,)= 1,<0)-1P.+ (,)S,+ SC,)S,1(0)- 10) -n+,>+2o<公部2=4-ra-2升>+如果F.-2+ 2c>".Z>r.- Eccr.- SC)(1-2)根据r-8c+乙r<0(1-部>20公部因此2<24P中国煤化工假设MHCNM HGfle:// Vqkxcg9919991104.htm(第7/ 18页) 2010-3-23 12:01:49系统工程与电子技术9911042印<2P即201- 2>>Q02舟由于Sc1-公头于是Sc.2><- -5公为=1-2兴因此2+ Ec>T.推论2 1.(F2> 214.0)的充分必要条件是Fn T.表示存储量太多 ，需要更 多生产时间,从而在 周期结束时,待加工零件存储减少。定义5我们把满足下式的点集称为循环策略δ的理想轨迹Iraj'(l)|eco.对= (I"(1)| T!(1)[7?(0) + tS{， 1∈[0,F1十C;]m- (P- S)(-M1-C9)(6)1∈[NLI +C9,F9] .(-那)S9， 1∈[R9,F%]中国煤化工MYHCNMH G我们称上述公式中1(t)le 1o,巧为循环策略零件i的理想轨迹;称IBo*()=(1' l0≤1≤T9≤i(0<(7))(0).i∈N}1(0(8,))(0) +iS/.I∈[O,F-.(Qr(0))+C]Tej0u2(l)le., sw,= {7 (<8)0)1(<0<(8,)(1)(1i(0<(8))<0) + (F-(0(8)) + C%)S%- (P%- S$)(- P-.(0r(8))- C%)，t∈[(F_ :(Or(6,)) + C%,F(r(8))](- F(Q(.))S/， I∈[(F.(Ol(8)),F.(0r(8,))]Box/(1) = (1(0(,))()|0≤1,(0r(8)>(1)≤i,(0(8,))(1),i∈N),0≤1≤F,(Or(8,))万(a8,)Boxa()=° U Box8}(l)1=0定义0)￥.0,则有I(Fn)≠I*。证明假设I*=I(Tc+O t),由于I*:=( Fn~ pi)S;=(Tc p;Si;I(Tc+O t)=(Fn-Fj)S;=(Tc+O t-F)>S;i∈N ,有F;=F;+O ti∈N。另一方面,在时刻pn-1+O t+Cn,开始生产零件n ,这时,存储应有In(0)+( Fn-1+O t+Cn)Sn, 因此F.=F。:+O +C.+4.60)+-.+4+C25>F.+r+P。- S.OiS.P.- S.T。+Ot从而有I(Fn)≠I*。根据定理9得到如下定理。定理10 (1) Iδ j(0)∈Box0 tδ })(0)的充分必要条件是max[1(0)-动|≤0r(δ)≤了- 1%0) .1-2,-1SP- Sp(2)如果12(0)-12| 12(0)- T允,则选择.k-2,-四S2Or°(8,)乃- 1P(0) .PSt;=T。了- 1(0)P-S(3)如果, 1门(0)-19112(0)-7元, 则选择中国煤化工0-2,四MHCNM HGxcg9919991104.htim(第11/ 18页) 2010-3-23 12:01:50系统工程与电子技术991104Ar°(8) =. max片一7(0)4- 2-由P”- Sp1 ,(0)-，_max[1(0)-卫S2,R-.2-Spi= 01.2...k(8,)k(6) = max{k。9，0)- P。SpL11(0)-卫V 0≤L≤ko}1-21-1j = min{F,e(8j) 1-. max1'(0) -4- 2.-了一1/(0)，Ti-所-了证明(1) 如果/'(0)∈B<0.>(0)，则r/(0>≤i(0 (?))=?- (75(>(>/(/(0>/<(())=72++S8 rjO t(δ j).(k-2...n). ,则有( 1/(0)-。了- 1/(0)S2 |≤Sr(δ)≤P-S2(r'<0>-1 )9-1/(0)另-方面,如果’S2」≤Qu(δ)≤P-S!?书(0)≤i,(O())=1}-(P/- S?)O(8)，(0)>≤i(0(;))=7:+S:/0r(8).k=2,... ,n有I8 i(O) ∈Box o )(0)。(2)如果上(0)-1，11(0)-1k- -2,-5SSy则对任何0t(δ,)∈[, max.(B(0)-公\了- 1/:(0)-}P-S:零件n到达乃时刻为TcO [WTBX 8 ),因此t=Tc “-?0}。中国煤化工MYHCNMH G注:(1)如果Iδ ;(0)=jδjyi∈N ,则0 (δ )=0,反之不成立,即如O (δ )=0则不能推x99991104.htom(第12/ 18页) 2010-3-23 12:01:50系统工程与电子技术91104出19<0)= I9Vi∈N°(2)如果1(0)= i,(Qr())V i∈N.0r(6)=Q(8)= 19=7(0r(8,)) Vi∈N.定理11如果Iδ j(0)∈Box0 tδ })(0)C Box ,那么采用低速技术,达到理想轨线的时间是(1)如果gjo∈M,使得Iδ io(0)=.jδ a,则t*;=0,t*=0。(2)如果Iδ j(0)∈Qδ y,但gio∈N满足Iδ io(0)* pδ ij,假如IS ni(0)=j; n-1mi=0,1,2, ... ,k(δ j) ,这里k(δ j)=max{ko[S n-L(0)= δ n-Li, v 0≤L≤kg},则有t)=min{Tc-- 1,<0),F._ xe)-1}.1* = min{t;' }。P-S(3)如果1I°。(0)∈Jscig，,进一步假定1°0(0)=1(Nt (8,),则:;=F(0(8,))。(4如果r"'。(0)∈ Duce ,但3io∈N ,满足户(0)≠1, (or(o,),12(0)-12max(2(0)-12},则SStg- I*(0)9-1*<0)。1:<0)-1..1(0)-2;则选.我们选择Ar<(8;)=-,t; =T。,如= maxP-SS一2.*.择△l°(8;) =. max = max|中(0)-2\-2...n - ..S，假定1,(0)- 1,m. (1(0)-2i = 0,1,2,.,k(8,)k(8;)= max{k([(0)-。。S2。=max12(0) - I$}V 0≤L≤ko}2≤k≤n则有tj; = F_k(0,>-1一max上(0)一型2≤4≤m4快速控制轨线于最优轨道的控制步骤中国煤化工MYHCNM HG设δ下的低速生产的时间和为TLT(δ ) ,现给出快速控制轨线于最优轨道的控制步骤如下:第1步用公式(5)计算平衡生产周期 ;fe// vqkx有的x99991104.htom(第13/ 18页) 2010-3-23 12:01:50系统工程与电子技术91104第2步用公式(3)和(4)计算 ;第3步对给定策略δ ,用公式(6)计算理想轨线 Itraj;(t)le∈0.,8j,令G:=1第4步对于I(G,6 )(0)∈Bn ,如果gj∈M满足FG,8 n≤Tc,转第5步;否则,即F(G,8 in>Tc,,vj∈M ,转第6步;第5步如果I(G.B)(0)∈ Box(0j)(0)CBox ,进一步有(1)如果gjo∈M,满足p.eg (0)= i%。. ,则。=O,TLT(δ j)=0,t=0,δ j。是最佳策略,停止;否则，即Vj∈M,I<0)≠ig。, 假定INC-9%'(0)= , , i=0,1,2k(δ，这里k(0,)= max(<0122)(0)=12un,V 0≤L≤k)'则t.=min{户1u)-. ,t.-.1%o- 19io(0)假定i* =min{; )。假定t*=minj{苛j}P°o-S°oi90- 1%0(0)=min{; }=%●ti=T.--P1fo- Sa则对h-=....n,在区间[T21 -Po- T960) +n+P所一SPo1%- 1%o(0)%(0) + (F2:-pnS+ C2S%0P°0o- S%o那一-”-1%0(02- .P%-S%o1go- 1I%o(0) + (的一岛)S%o低速生产零件h。有P°io一S%o”停止。TLT(8,) =P%- S%o如:= F_ko, ,-，那么,对h=1,2, ... ,n-k(δ j,)-1在区间[臨+ C%。+5o60)+(PstG)-S.]低速生产零件h , 低速生产时间为P-S1-t(6; )-90-1%(0) , 停止;否则i.e VjEM,I(G.6 j2{0)0), ,转第3步;- Po-Sfo-S%中国煤化工(3)如果r19.*%'(0)∈Qwe, ,进一-步10.%'(0)= 1<0(8,MHCNMHGCNMHS),TLT(δ i)=0,xcg9919991104.htm(第14/ 18页) 2010-3- 2312:01:50系统工程与电子技术91104t*=minj{t]},停止;否则,即vj∈M,IG,8 })(0)≠j(O t(δ ),则转第4步;(4)如果19.30 (0)∈2asa,但gio∈N ,满足0)=i(0<1,)),如1%(0)-19%-< max2(0)-12，则选SS%o择Ot*(8,)l;= T。%- 1%(0)P%o-So1%6(0)-7%0-. 少(0)-%、如-=max .k-2...mS2io5(0)-0，则选择Q*(8;)=, max (广为一2.**.月S20假定1s,(0)- Ts,= maxI20(0) -k一2,*,用S2oi= 0,,2,.,k(0,)k(0,) = max{ko|2(0)- sL, 1p%0(0)- p。、F-2,"刀S2foW 0≤L≤ko}则i = min{F. -0,)-1- max[出(0)-五，。-2.*.*SoT. -- 19%6(0)},l° = min{1; }_Pe Sio中国煤化工MHCNM HGxcg9919991104.htm(第15/ 18页) 2010-3-23 12:01:50系统工程与电子技术91104假定!=min(t;}=tj，如1%6(0)-1%+(mon,- B-Tr(0+C%5t%际-0(0)-对h=2,3,... ,在区间%一节(0)+ C%+P/o-S%P-S%P%-S%]低速生[路一 P-st1%o- 1%6(0) +出-%(0).)S%o产零件h。且有TLT(8, )=P%s-S%。停止。h-2P21o一S%o如果(0)-1.......高(0)-0、 且，.r.- 1-19%(0) ,那么,对1于h1.2.. ,nk(8 小maxS%ok-2**.mP%o-S2%01o- 1p%(0)1.在区间[P21-19o-. 19o(0)+C%0+.<0>+(gn--P9o-Si%2 +C%6)S%一196<0)-P%o-SpoPi-SYoP0-S%”-10j)-1 go- 1%o(0)+一19%o(O).-)S%低速生产零件h,且有Pin- S°%o,停止。TLT(8,)=P2io- S%0o如果1o(0)- i,则对于1h-1,2.... ,n-k(δ :)-1低速生产 零件h的区间为ti=F。_ 16..>-1- max .S20[ir,-. max西(0)-型,FC%o+I%0(0) + (一max_1%0(0)- P%o,+ C%o)S%o着一2.**.P°2o - S,opo-. max,1%(0)- %k- 2,.四520且有η-k(@ig)-1To- 1%o<0) + ( maxI%(0)S%。| 中国煤化工TYHCNM HGP%io- Spoxcg9919991104.htm(第16/ 18页) 2010-3- 23 12:01:50系统工程与电子技术91104停止。否则,即1C)(0)东Box*(<8,>(0),V j∈M ,Vj∈M ,转第6步;第6步选择最快到达理 想轨线的策略δ i,并 计算G+ 1周期零件K的生产结束时刻的存储量I9c+1.3g)(F%o) =[(i=k(F(C+1.。)' - F:(C+1.4.)S;/。k> i(1(+1.02 + F(C+1.4,S。k< i对i∈N,k∈N ,检查如有ko∈N ,并且，j(ko) ∈M满足1](6+1.0%})(F%)=]J(G+13so2>(0)∈BoxMeiuo,)(0)则G :=G+1转第5步;否则,即V k∈N,V j(k)∈M,19+16) (F% = ]c+.3jxe)<0)氏BoxWijxe>(0),G:=G+ 1转第6步。5结论和进一步的研究，本文对多产品单机器生产系统的循环策略的特性进行初步研究,给出快速进入最优轨线的方法和步骤。以及储存空间任意-点快速进入最优轨线时间的计算公式。当然这只是我们一系列结论之一,是考虑最优生产周期正好等于平衡生产周期情况下得到的，通常的情况是最优生产周期大于平衡生产周期,我们将陆续发表有关结果。致谢中国国家 自然科学基金会;美国加州大学伯克利分校,美国加州政府MICRO项目;美国著名电子公司Intel Corporation, H arris C orporation, Advanced Micro Devices InC., Cypress Semiconductor DigitalEquipment C orporation, IBM, NC R Semiconductor, SGS- Thomson, Microelectronics提供部分资助。基金项目:国家自然科学基金资助课题( 79670104)作者单位:熊中楷(重庆大学工商管理学院，400044 )里奇曼(美国加州大学伯克利分校I业I程与运筹学系，94720)参考文献[ 1 ] Leachman R C, Park K. Real-Time Scheduling of Setups of a Multi-Item, Single Machine Based on Forecast ofFultureW ork Amivals. 1992, Preprint, Engineering System Research C enter,U C Berkeley,1992.[2] Gershwin S B. A Hierarchical Framework for Discrele Event Scheduling in Manufacture Systems. Proceeding ofIEEE, 1989,77(1):195~ 209.[ 3] SharifniaA, Aramanis M. Gershwin S.B. Dynamic Setup Scheduling and Flow C ontrol in ManufacturingSystems. T heory and A pplications 11991: 149 ~ 175.[ 4] PerkinsJ R, Kumar P R. Stable, Distributed, Real-Time Scheduling of Flexible Manufacturing/Assembly/Disasscmble Systems. IEEE TRans. Automatic C ontr, 1989,AC-34(2).[ 5]Kumar P R, Seidman T I. Dynamic Instabilities and Stabilization Methods in Distributed Real-Time Schedulingof Mannfacturing Systems. IEEE Trans. on Automatic C ontrol, 1990,35:289 ~[6]Lou S, Sethi S Sorger G. Stabling of Real- Time UnreliableMachine.中国煤化工nagement,U niversity ofT aronto, 1989.YHCNMHG[ 7]YuG. Robust Economic Order Quantity Models. European Journal of Operational Research, 1997:482 ~ 493.[ 8] H arisR S. How Many Part to Makeat Once. Faccory, the Management, 1993:135 ~ 136.<99919114.9(第17/ 18页) 2010-3 23 12:01:50系统工程与电子技术91104收稿日期: 1998-3-18中国煤化工MYHCNMHG .it 00911041101第18/ 18页) 20103-23 12:01:50fle//E/ Vqkxtgdjsx