Զѧ
ACTA AUTOMATICA SINICA
1997 23 3 vol.23 No.3 1997



ȵѧģ
ʢ⡡
ժҪͨ롰Դ亯ĸ̼ӹʱΪĿ꺯ϵͳȵѧģͣ ˸ģŽ㷨ͶĿн㷨. 
ؼʡȣ ϵͳ. 
MATHEMATICAL MODELING AND SOLUTION OF SCHEDULING
FOR DEADLOCK AVOIDANCE
YANG SHENG WU CHENG
(Department of Automation, Tsinghua University, Beijing 100084)
Abstract This paper presents the mathematical model of optimal scheduling for deadlock avoidance in manufacturing ysstems based on the conception of resource allocation function, aimed at reducing the system total processing time. Two algorithms are proposed for the optimal solution in the case of two processes and the feasible solution in the case of multi-processes, respectively.
Key words Deadlock, scheduling, manufacturing system.
1
㷺ڼϵͳ1ݡϵͳ2ݡϵͳ34ݵȶ̡ҵĸϵͳ. ԭϵͳԴ޺ͽƽ˳Ĳ. Ĳϵͳܣ˴ǶϵͳһҪ. 
ģ1˼ϵͳвĳҪҪ. ϵͳϵͳص㣬ߵΪԼŻĿ궼ͬ. ϵͳΪоȵѧģ. 
2ѧģ
ڸӵϵͳͬʱڶԴͶ. һһʵֳΪһ. 
1.ϵͳдnԴ еiԴĿΪki i=1,2,,n. ϵͳԴk=[k1,k2,,kn]T. ϵͳöԪ(,k)ʾ. 
2. ֪ϵͳ(,k). ʱtĳpԵiԴռΪri(t),i=1,2,,n. ý̵Դ亯r(t)=[r1(t),r2(t),,rn(t)]T,r(t)k.
pԴ亯(RAF)ԷΪ֣ ӳԴ亯(NRAF)ͿӳԴ亯(DRAF). ǰǽpȴӳµԴ亯ϵͳдڶḶ̌pԴҪȴµԴ亯.ǰǺһ. 
嵥λԾu(t0)=1,u(t0)=0. ڽpԴռúͷžһϵɢʱϽеģ .
1. ֪ϵͳ(,k). Խp״ռԴʱΪʱ㣬pӳԴ亯r(t)ԱʾΪt0=0, tjtj-1, j=1,2,,m;aj0
2. ֪pӳԴ亯ĿӳԴ亯s(t)ԱʾΪt00,ti-ti-1ti-ti-1,i=1,2,,m.
3. s1(t)+s2(t)ԱʾΪs1(t)+s2(t)=,min(m1,m2)m3m1+m2+1.
3.֪Դ亯,s(t)ĵjԴ״̬Ϊ ʱ䦤j(s(t))=tj+1-tj, j=0,1,2,,m-1. s(t)ܵĳʱ䶨Ϊ
ϵͳܵļӹʱΪĿ꺯ıȵѧģΪϵͳ(,k)дṇеjpjӳԴ亯rj(t)=a(j)ku(t-(j)k),j=1,2,,n. ҪpjĿӳԴ亯,ʹ֮(н)(Ž).
n=2ͨµ㷨ϵͳŽ.
㷨.
1) ƽֱϵкt1r1(t)ĸԴ״̬aiĳʱ䣬t2r2(t)ĸԴ״̬biĳʱ. ͬı.
2) r1(t)r2(t)ĳͻConflict(r1(t),r2(t))={P(t1,t2)P,r1(t1)+r2(t2)k}. ǣr1(t)ĵiԴ״̬akr2(t)ĵjԴ״̬biϵжӦСUij,ak+bkk, Uij(r1(t),r2(t)).
3) ɳͻDeadlock(r1(t),r2(t)). ϵڽӳͻ½򹹳ͼ1еD1D2.

ͼ1㷨
4) ̵ļӹϵпˮƽߡֱߺ45߶αʾ (00)ʼ(a(1)m1,a(2)m2). ˮƽ߱ʾp1Уp2ȴֱ߱ʾp2Уp1ȴ45߱ʾp1p2ͬʱ. ּӹ߶ζýͻ. ȣŽӦļӹ·45ռı. ԭֻҪпܣ45(a(1)m1,a(2)m2)ƽ. ͻΪسͻ»߽ˮƽֱƽ. 
5) ݲ4)·Žs1(t)s2(t).
̵ ָp1Ͻp2ԴȨԲ谭Уs1(t)=r1(t)Խһ㷨Ϊһά㷨ˮ㷨˼ǣڱ֤p1ӳ£p2ÿԴ״̬ʱ[0,a(1)m1+a(2)m2)ϵ伯. p2ܹӵһԴ״̬عɵһԴ״̬ÿԴ״̬ĳʱܹҪϵͳڿн⣬ȹɵһԴ״̬·ӦϵͳŽ. ñm2ˮƽϷֲɸˮ. ÿˮܹһˮƽ֮ڵˮˮ. ϲˮؾмˮ²ˮеˮγɵ·Ӧн. 
ˮ㷨.
1) ʱ[0,a(1)m1+a(2)m2)p2ĵjԴ״̬bk伯Fj={[a,b)b-aj(r2(t))t[a,b),k-r1(t)bk},j=0,1,2,,m2-1. ָFjеԪشС.
2) 伯FjЧ伯Vj, j=0,1,2,,m2-1. Cαʽĵ㷨.
룺 伯С {F0,F1,,Fm2-1};
ʱ{0,1,,m2-1}.
Ч伯{V0,V1,,Vm2-1}.
{ Let set V0=F0;
for (i=1; im2-1; i++)
{ let set Vi=;
for (j=1,k=1; jVi-1;j++)
{ get the j-th element [a,b) of set Vi-1; 
while (kFi)
{ get the k-th element [c,d) of set Fi;
if( [c,d)[a+i-1,b)) {k++; continue;}
if ( [c,d)[a+i-1,b)) break;
let [p,q)=[c,d)[a+i-1,b);
if (q-pŦi)Vi=Vi{[p,q)};
k++; } } }
return the sequence of valid-interval sets {V0,V1,,Vm2-1}
3) Vm2-1ʼŽs2(t). Ч伯Vm2-1еÿԪضӦһн⣬ еһԪ[a,b)ӦŽ.ϵͳ̳ʱ䦤(r1(t)+s2(t))=a+m2-1. V0, V1,,Vm2-1ÿһڿн·ϵ䶼ضӦһ״̬.
n2һ⣬ڼ㸴ӶΪNPѵģŽڻ. һнķ.
ȶr1(t)r2(t) 㷨Žs1(t)s2(t). Ȼr2(t)=s1(t)+s2(t). r2(t)r3(t) 㷨Žs2(t)s3(t). r3(t)=s2(t)+s3(t)ֱrn-1(t)rn(t) 㷨Žsn-1(t)sn(t). ݺsn(t), sn-1(t), sn-1(t), sn-2(t),,s2(t),s2(t), s1(t)Թϵͳһн.
. ֪ϵͳ(, k),k=[1,1,1]T. p1p2ӳԴ亯ֱΪ

ͼ1㷨· ʽֱΪ
(1)
(2)
ϵͳ̳ʱ䦤(s1(t)+s2(t))=min=7. ͼ2ˮ㷨·ʽͬ(1)ʽ. 

ͼ2ˮ㷨
ߵλ廪ѧԶϵ100084
ο
[1] Peterson J L, silberschatz A. Operating System Concepts, second edition, Addison-Wesley Publishing Company, Inc., 1985:271-306.
[2] Diaz M. Modelling and analysis of communication and cooperation protocols using petri net based models. Computer Networks, 1982, 6(6):419-441.
[3] Banaszak Z A, Krogh B H. Deadlock avoidance in flexible manufacturing systems with concurrently competing process flows. IEEE Trans. Robotics Automat., 1990, 6(6):724-734.
[4] Viswanadham N, Narahari Y, Johnson T L. Deadlock prevention and deadlock avoidance in flexible manufacturing systems using petri net models. IEEE Trans. Robotics & Automat., 1990, 6(6):713-723.
ո 1994-06-03
