Ϣ
INFORMATION AND CONTROL
1999 28 2 Vol.28 No.2 1999



Job-shopĻģ˻滮

ժҪûģ˻滮(SAEP)Job-shop.ȽSAEPͽ滮(EP)Ĳͬѡ񷽷Լǵı,˷ʵ,Ƚ㷨.
ؼʡģ˻𷨣滮
SAEP ALGORITHM OF SOLVING JOB-SHOP SCHEDULING PROBLEM
WENG Miaofeng
(East China Shipbuilding Institute,Zhenjiang,212003)
AbstractIn this paper,a combined evolutionary programming (SAEP) with simulated annealing is presented to solve Job-shop scheduling problem.Two different selected methods between SAEP and EP and their mutation operators are discussed,and simulation results are given to illustrate the efficiency of the presented algorithm,and a comparison between the two algorithms is also presented.
Key wordssimulated annealing algorithm,evolutionary programming,scheduling problem
1
оJob-shop(ΪJSSP)Ϊ(1)nΪrࣺJ={J1,J2,,Jn},Ji[1,r]ÿ๤иضĲɸıĲ˳(2)m̨M={M1,M2,,Mm}ÿ̨ɼӹɲ,ͬĻܼӹĲȫͬͬļӹʱҲͬ;(3)ӹİװʱ˻ӹǰһй.еİװʱָ߸ʱ䣻(4)ͼӹڿеȴ״̬ʱ,Ϊ0еȴʱȻߣ(5)ÿ๤иԵĽҪ(6)ʱ̶ɵҵÿһӹûԶ.
 ؽĸ䵽ɼӹĻ,Ĳ˳ͽ޵Լ£ʹnļӹʱ.
2JSSPģ˻滮ʵ
2.1ʾ
öάS=[sij]mLʾ,sij[0,L],mʾ,Lʾnܲ.Ԫ(Ԫ),һԪֵ,ÿһԪ(ƷԪ)ֵʾnйͳһ.еķʵ,1033ͳһ(1).
11033ͳһ

123456789101112131415161718192021222324252627282930313233
A1C1B1D1A2C2B2D2A3C3B3D3B4D4E4B5D5E5B6D6E6B7A7F7B8A8F8B9A9F9B10A10F10

(עĸAFʾͣϽֱʾ)
ھS,Ԫض,siki0,siu=0(i=1,2,,mu=ki+1,,L),=L(diΪSеiϷԪظ).
нԼΪ ٻԼÿһڿɹʹõĻϼӹԪԼ(κλϼӹ).ڲ˳Լһ,1ھекСڵ2к,м乤кŴǰһкŶСںһк,кŴǰһк(,ָͬһ).
sij,skt(jt)Ϊһ.sij-1=0ʱ,sijпеȴskt=sij-1t<jʱ,sktΪsijǰһ򣻵skt=sij+1t>jʱ,sktΪsijĺһ.
2.2ʼȺ趨
(1)ȸһS,Ȼ²LԪòͬ(1L)ֵ,нԼ
for p:=1 to Ldo
(1)pڹеĹif pǵ1 then {pĲ,ɹʹõк() i(1,10)кj,sij:=p}
else (pΪм乤) {pĲ,ɹʹõк()k,Sҵpǰһкg,[g+1,L]һкt(g+1tL),skt:=p}.
endfor
ڽʼȺʱ,˳1LĻóֵ,ÿĺһضڸù֮,ʲҺһк.
(2)ͨǰƸеķԪ
ԸS(кi1(i+1) mod m)(кj1ϵ㵽L)ɨԪsij,sijǵ1ǰƵеĵ1Ԫش()ǰƱ־,{йsijǰһ(sij-1)Ƿǰƹ,ǰƹj(sij-1)кt(t<j),sijǰƵitкĵ1Ԫش()(sij-1)δǰƹsijϵ,ɨһ}ֱSеLԪȫǰ,Ƶ.
2.3Ӧֵļ
ͨ,ǰƸķԪعӦֵ.a(sij-1,sij),t(sij)L(sij)ֱΪSйsijڻiϵİװʱ,ʱ깤ʱ䣻sij-2,sij-1sijֱΪsij-2,sij-1sijĲͣa(A,B)ΪAΪBİװʱ(ʱ)j-1=0ʱ,sij-1=0,L(sij-1)=0j-2=0ʱ,sij-2=0,sij-2=0,L(sij-2)= 0.
(1)һsij깤ʱL(sij)
sijΪ1L(sij)=L(sij-1)+a(sij-1,sij)+t(sij)sijΪǵ1(a)sij-1=0(пеȴ)ʱ,L(sij-2)+min[a(sij-2,0)+a(0,sij),a(sij-2,sij)]>L(sij-1)sij-20L(sij)=L(sij-2)+min[a(sij-2,0)+a(0,sij),a(sij-2,sij)]+t(sij),L(sij)=L(sij-1)+t(sij)(b) sij-10(޿еȴ)ʱ,L(sij)=max[Lsij-1+a(sij-1,sij),sij-1]+t(sij).
(2)һi()һ(Ԫ)깤ʱTiһk깤ʱLL(k)

ɹͳһűвһkһx,x깤ʱL(x),LL(k)=L(x).
(3)SӦֵf

ЦΪʵĳͷϵ,D(k)ΪkĽʱ.ȺõĸСӦֵ,Ϊnļӹʱ.
2.4EPѡ
óʼȺģΪż,ÿȺ尴Ӧֵ.ȡǰ50%()ĸ帴Ƶһ,µĸб,첻ɹ,Ϊһ,򽫲Ӹ徭,ǰƷԪغ󱣴浽һ.
2.5SAEPѡ
ģ˻(SA),ؽĳЩӻ,нǿȫ,ֲܹС㣻EPѸ屣ѡӻᵼ¾ֲŸ弱,пܹ,ֲŽ⣻лʹSAEP(SAEP)EPѡ.еķʵУʼ¶T0=1,Tt+1=0.9Tt,(ÿΪ0.9),оΪ1000,ûֹ¶.ܸMetrolis׼:y2<y1exp(-(y2-y1)/T)>ʱӸ滻丸(y1ǸӦֵ,y2ӸӦֵ,T¶ϵ,01֮ȷֲ).ڱ,i1Ϊi2,i2Ӧֵi1ӦֵС,i2滻i1,i2滻i1.
滻ĸ,ǰƷԪ,Ȼȫ屣浽һ.
2.6
滮ֻбӶûý.SAEPEPͬ6ֱ.Ϊʹ徭˳ԼҪ,ҪƶĹ֮ƶ.
(1)зԪƶȷ
SԪsijƶΪ(wt,wr)wtΪsijǰһ(sij-1)Sек,wrΪsijĺһ(sij+1)Sек.ֻwr-wt>2ʱܶԸøб,ѡƶķԪ,ֱ÷Ԫƶĳ>2ʱΪֹ.sij=0ʱ,sijƶΪ(0,L+1),ʲԪصƶ.
(2)
Ҫĸ壬ѡ6ֱеһֽб
win(ͬϵԪ)
ڸS,ѡһԪsijsijƶ(a1,a2).(a1,a2)һкk(a1<k<a2),sijƶ(a3,a4)sij(a3<j<a4),ɻsijsik(sikֵΪ0).
Wbt(ͬϵľԪ)
(a)ڸS,һԪsij(b)ƶ(a1,a2),(a1,a2)һкt,һɼӹsijĲ֮к()k(ki.k=i²k,ֻk=i,sij,ת(b).sktƶ(a3,a4)sij(a3<j<a4),к()iɼӹsktĲ,ɻsijskt(sktֵΪ).
 Sin(еһԪƶͬԪػ,(WinSin).
 Sbt(вϵһԪƶڵһɼӹϵԪػ).
Tin(ĳһпеȴǰһƵƶͬеԪش).
ڸS,һкi.iһпеȴĹsij=0,sij-1=0.ҵsijǰһ(sij-1)кk,кt,ƶ(a1,a2)sktǰƵkϵ(a1,t)ڵĵһԪش().
Tbt(ĳһпеȴǰһƵƶڲɼӹһϵĵһԪش().
ӲӸнԼ.
3
10̨ϼӹJ1J3Ϊ1๤,J4J6Ϊ2๤,J7J10Ϊ3๤.๤ĲΪ1ࣺA,C,B,D2ࣺB,D,E3ࣺB,A,F.3๤Ľ޷ֱΪ190,95,181.10ĹΪ33ͳһż1.4̨ӹ谲װʱ2,ڻϵʱ3.3ӳ̨ܼӹĲ.
2̨ӹ谲װʱ

M1M2M3M4
0ABCF0BCDE0BDF0EF
002.52.01.82.101.51.41.82.201.31.71.201.92.1
A1.400.41.51.8
B1.31.700.60.91.701.82.00.81.801.51.8
C1.81.62.101.91.31.901.51.2
D0.41.01.801.51.62.001.5
E1.51.51.41.301.802.1
F2.21.61.31.100.41.61.701.41.60

3ڻϵʱ

ABCDEF
M117.2524.4518.6813.88
M218.9515.7217.4518.67
M317.5421.4519.76
M415.4319.45

ʵȺģ=100,о=1000ͷϵ=2000(ʵõ).SAEPEP㷨ĵȽͼ1ͼ2.㷨ķȽϼ4(CPUʱ=㷨õŽ(ʱ)ڱ586ʱ(s)).

ͼ1SAEPõȽ

ͼ2EPõȽ
4SAEPEPĽȽ

SAEPEP
Ӧֵ180.72187.01
869772 
CPUʱ260(S)150(S)

ע2ͱ3ֵıΪ塢Ƿ
ӷ,SAEPõļӹʱΪ180.72,EPõļӹʱΪ187.01.㷨ҵΪĵȽ,Ҹ깤ʱ㽻Ҫ.֮SAEPĽEP,EP97,CPUʱ(ٶ)EPö,SAEPCPUʱΪEP1.73.
4
(1) SAEPEP㷨JSSPЧе.
(2)SAһĸʽܽϲĸ,ĽGAѡ,SAEPռ,ֲŽ,ռԼԼ,Ż庯,˷EPġ,EPٶȱSAEPö.
(3)㷨,óͷ˹ĽԼнⷨ˻ԼͲ˳Լ,ȻһнⷨЧʽϵ,㷨ڸбʱ,ʹҪƶľԪֻƶƶ,Ի,ؼ˲нĿ,Ӷ㷨ƵĸʾͱڽJSSPǳɹЧ.
߼飺Ů58꣬ڣоΪ˹ܣ
ߵλҵѧԺ򽭡212003
ο
1Yip P,Yoh-han Pao.Combinatorial Optimization With Use of Guided Evolutionary Simulated Annealing.IEEE Trans.Neural Networks,1995,6(2) : 290295
2Ҧ£¹.㷨оչ.ѧ,1995,18(9),694705
3.¼Job-Shopϵͳ.ϵͳѧ,1997,9(4) : 4250
1998-08-18ո
