Զѧ
ACTA AUTOMATICA SINICA
1997 23 5 Vol.23 No.5 1997



һDEDSŵĽⷨ1
ĵ
ժҪ˴洢ߵһµŵ⣬ŵĿ꺯ľʽָ͹һʱŵȵĹʽ⣬ڶʱõһѰŵ㷨
ؼʡɢ¼̬ϵͳ(DEDS)ŵȣ洢
SOLUTION TO A KIND OF OPTIMAL SCHEDULING PROBLEM OF
DISCRETE EVENT DYNAMIC SYSTEMS
CHEN WENDE
(Institute of Systems Science,Academia Sinica,Beijing100080)
(Complex Systems Engineering Lab.,
Institute of Automation,Academia Sinica,Beijing100080)
AbstractIn this paper we present a kind of new optimal scheduling problem for production lines with buffers.A concrete form of optimal scheduling objective function is given.We point out that it is not a convex function.Optimal formulation solution is given for one variable and an iterative algorithm is obtained for multivariables.
Key wordsDEDS,max-algebra,optimal scheduling,buffer.
1
һĵо12.ף3ݽ̫ԭ˾̨һµŵ(ҲΪƽ).ף4ݵnֹm̨..ѵµŵ.
.ж̨ɴ޴Ĵߣÿӹnֹ.ӹʱ֪nֹļӹŶһ̨ճʱͶһ.εÿֹĿMiʹÿλʱָ

(1)
ﵽ?һʱ䣬WiΪiֹӹ.
ĻϽ.
2ڦ˵Ĺʽ뺯ʽ
ΪRΪʵ򣬷ֱʾµĺͣ.贮еrǰдеbrɻBr.ÿӹʱΪOαĿ(br0)ܺΪm.xr(k)ʾkһJN뿪mrʱ䣬1rm.Pr(j)ʾjJjmrϼӹʱ.ף5ݵĽ
15.£m1ճʱͶһ״̬̿Dг

(2)


(3)

(4)

Ҵk0>0kk0ʱ

(5)


(6)
a1,,amΪĶԽԪ.
Եһ⣬ʱPr(j)ͬΪtr(i)ʾiֹmrϼӹʱ䣻A(j)ҲͬΪ

(7)
ĵrеsԪΪars(Mi).rsȡ󣬶AiԽԪصһֵ

(8)
rsʱj1=j1=0r>sʱj1=j1=r-s-1.
(9)


(10)
ֱtr-j(i)=t1(i)jv-1<j<jvʱ

(11)
ֱts+j(i)=tm(i),ֵrsй.
1.Ǻ붨£

(12)

(13)

(14)
Цijj(613)ʽ.
֤.trs(i)ȫΪtrsԱʹ֤.(7)ʽʾͼG(Ai)m㣬rsʱrsΪtrsr=s+1ʱrsĻΪ0r>s+1ʱrsûл.ars(Mi)ʾͼG(Ai)rsĳΪMi··.ͼ֪ʶ֪Mi㹻ʱ·ľصĻ·Ȧ.rsʱ2Mij2r<sĵ㵽s·УɵĶ壬֪ΪԻ·Ȧ·(0Ȧ
