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



㷨job-shopеӦо

 ֱ
ժҪоӦý㷨(Ŵ㷨(GA)ͽ滮(EP))Լģ˻㷨(SAGASAEP)job-shop⣮ʵ㷨ǿеģǵ˱Ƚϣ
ؼʣ㷨ģ˻𷨣
ͼţTP18ױʶ룺B
A STUDY ON APPLICATION OF EVOLUTIONARY ALGORITHMS TO
JOB-SHOP SCHEDULING PROBLEMS
WENG Miao-feng WANG Zhi
(East China Shipbuilding Institute, Zhenjiang 212003)
Abstract:The improved methods solving job-shop scheduling problems using evolutionary algorithms (GA and EP) and combined evolutionary algorithms with simulated annealing algorithm (SAGA and SAEP) are discribed in this paper. Comuputer simulated results show that the four methods are possible. In the end, a comparison for their efficiency is presented.
Key words:evolutionary algorithms, simulated annealing algorithm, scheduling problem
1
㷨(Ŵ㷨(GA)ͽ滮(EP))Լģ˻㷨(SAGASAEP)job-shop(JSP)Ч㷨ͳһ򵥵Ķά,ʹŴڻƶڽл򽻻,㷨ٶȷǳ()
2
JSPĿ,nm̨ϵļӹ·߲ͬ,ΰÿ̨Ϲļӹ˳,㲻ڽ,ʹnܵ깤ʱСJSPԼ£
(1)nֳrࣺJ={J1, J2,, Jn}, Ji[1, r]ÿ๤Ĳ˳ͬ(2) m̨M={M1, M2, , Mm}ܼӹĲȫͬͬļӹʱҲͬ(3)ӹİװʱ˻ǰһӹйأеİװʱָ߸ʱ䣮(4)ͼӹڿеȴ״̬ʱ,Ϊ0еȴʱȸߣ(5)ÿ๤иԵĽҪ(6)ʱ̶ɵ,Ҳǵӹ깤ÿһӦеʱ䣮
3JSPĽ㷨(GAEP)ʵ
3.1 Ⱦɫ()ıʾ
GAEPȾɫ()öάS=[sij]mlʾ,sij=0,1,,lmʾ, lʾnܲһԪ(ƷԪ)ֵ,ʾnйͳһţеķʵ,1033ͳһ(1), l33S,Ԫ(Ԫ)ңsiki0siu=0(i=1,2,,m;u=ki+1,,l),(diΪSеiϵķԪظ)
1 1033ͳһű

123456789101112131415161718192021222324252627282930313233
A1C1B1D1A2C2B2D2A3C3B3D3B4D4E4B5D5E5B6D6E6B7A7F7B8A8F8B9A9F9B10A10F10

(עĸAFʾͣϽֱʾ)
Ⱦɫ()нԼΪ ٻԼÿһ(Ԫ)ڿɹʹõĻϼӹڲ˳Լһ,1ھекСڵ2к,м乤кŴǰһкŶСںһк,кŴǰһк(,ָͬһ)
sij, skf(jf)ΪһĶ򣮵sij-1=0ʱ,sijпеȴskf=sij1fjʱ,skfΪsijǰһ򣻵skf=sij+1fjʱ,skfΪsijĺһ
3.2 GAEPĳʼȺ趨
(1)ȸһS,Ȼ²lԪòͬ(1l)ֵ,нԼ
for p:=1 to l do
{(1)pڹеĹpǵ1{pĲ,ɹʹõк()i(1, 10)кj,sij:=p},(pΪм乤){pĲ,ɹʹõк()k,Sҵpǰһкg,[g+1,l]һкf(g+1fl), skf:=p}}
ڽʼȺʱ,˳1lĻóֵ,ÿĺһضڸù֮,ʲҺһкţ
(2)ͨ,ǰƸеķԪ
ԸS(кi1(i+1) mod m)(кj1ϵ㵽l)ɨԪsij,sijǵ1ǰƵеĵ1Ԫش()ǰƱ־,{йsijǰһ(sij-1)Ƿǰƹǰƹj(sij-1) кf(fj),sijǰƵifкĵ1Ԫش()(sij1)δǰƹsijϵ,ɨһ},ֱSеlԪȫǰ,㶼Ƶң
3.3 GAEPĸӦֵ
ͨ,ǰƸķԪعӦֵa(sij-1, sij),t(sij)L(sij)ֱΪSйsijڻiϵİװʱ,ʱ깤ʱ䣻 sij-2,sij-1sijֱΪsij-2,sij-1sijĲͣa(A, B)ΪAΪBİװʱ(ʱ) j1=0sijΪһʱ,sij-1=0, L(sij-1)=0j2=0sijΪǵһʱ, 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Ϊǵ1i)sij-1=0 (пеȴ)ʱ,sij-20L(sij-2)+min[a(sij-2,0)+a(0,sij)a(sij-2,sij)]>L(sij1)L(sij)=L(sij-2)+min[a(sij-2,0) +a(0,sij), a(sij-2,sij)]+t(sij), L(sij)=L(sij1)+t(sij)ii) sij-10(޿еȴ)ʱ, L(sij)=max+t(sij)
(2)һi()һ(Ԫ)깤ʱTiһk깤ʱLL(k)Ti=L(sij), (sif0,fulʱsiu=0)ɹͳһűвһkһx,x깤ʱL(x), LL(k)=L(x)
(3)Ⱦɫ()SӦֵЦΪʵĳͷϵ, D(k)ΪkĽʱ䣮ȺõĸСӦֵ,Ϊnļӹʱ䣮
3.4 GAŴ
(1)ѡ(Ѹ屣)ÿȺ尴Ӧֵ,ȡǰ20%()ĸ帴Ƶһ , Ȼȡǰ80%ĸнͱ죮
Ϊʹ徭()˳ԼҪ,ҪƶĹ֮ƶSеԪsijƶΪ(Wl,Wr)WlΪsijǰһ(sij1)Sек, WrΪsijĺһ(sij+1)SекţֻWrWl>2ʱܶԸøн(),ѡƶ(Ԫ), ֱƶĳ>2ʱΪֹ
(2)(ʵԵĽ)ٸݽ(PC=1),ƥ伯ѡȡABAѡȡһaij,ƶ(a1,a2)BһaijֵȵĻbkf,bkfƶ(b1,b2)(b1,b2)һкe(b1eb2),ɼӹaij͵к()g,ҵbgeƶ(b3,b4)bkf(b3,b4)ڼb3fb4кkΪbgeĲͿɼӹĻ,flag1=1AbgeֵȵĻatv,atvƶ(a3,a4)i) aij(a3,a4)ڼa3ja4atv(a1,a2)ڼa1Va2,ii)кiΪatvĲͿɼӹĻкtΪaijĲͿɼӹĻ,flag2=1flag1flag2=1, aijbge,atvbkf
(3)ݱ(Pm=0.01),һ¸SSһsij, sijƶ(a1,a2),(a1,a2)һкf(a1fa3)һɼӹsijĲк()kskfƶ(a3,a4)sij(a3ja4)к()iɼӹskfĲͣsijskf
ϽӲ¸н,,ǰƸеķԪ,ʹЧƺ,ȻЩ¸Լͱ첻ɹĸһ
3.5 EPѡӺͱ
(1)ѡӣóʼȺģΪż,ÿȺ尴Ӧֵȡǰ50%()ĸ帴Ƶһ , µĸб죮
(2)ӣ滮ֻбӶûн,Ҫĸ,ѡ6ֱ([3],ֻƶƶ)еһ,б죺Win(ͬϵԪ)Wbt(ͬϵľԪ)Sin(еһԪƶͬԪػ,WinSin)Sbt(вϵһԪƶڵһɼӹϵԪػ)Tin(ĳһпеȴǰһǰƵƶͬеĵһԪش)Tbt(ĳһпеȴǰһƵƶڲɼӹ֮һϵĵһԪش)
Ӳ¸н,뽫Щ¸,ǰƸеķԪ,ȻЩ¸Լ첻ɹĸһ
4JSPĻģ˻㷨(SAGASAEP)ʵ
ģ˻(SA),ĳЩӻ,нǿȫ,ֲܹС㣮Ͻ㷨Ѹ屣ѡӻᵼ¾ֲŸ弱,пܹлʹSAͽ㷨,SAGASAEPGAEPŴѡ(SAGASAEPŴֱͬGAEA)еķʵ,ʼ¶T0=1,Tt+1=0.9Tt(ÿΪ0.9),оΪ1000,ûֹ¶ȣܸMetrolis׼y2y1exp(-(y2-y1)/T)ʱӸ滻丸(y1ǸӦֵ, y2ӸӦֵ,T¶ϵ,01֮ȷֲ)ڽ,i1i2i3i4,i3Ӧֵ,i1ӦֵС,i3滻i1,i3滻i1ͬ,i4Ӧֵi2ӦֵС,i4滻i2,i4滻i2ڱ,i1Ϊi2,i2Ӧֵi1ӦֵС,i2滻i1,i2滻i1滻ĸ,ǰƷԪ,Ȼȫ屣浽һȥ
5
10̨ϼӹJ1-J3Ϊ1๤, J4-J6Ϊ2๤, J7-J10Ϊ3๤๤ĲΪ1ࣺA, C, B, D2ࣺB, D, E3ࣺB, A, F3๤Ľ޷ֱΪ190, 95, 18110ĹΪ33,ͳһż1̨ӹ谲װʱ2,ڻϵʱ33ӳ̨ܼӹĲͣʵȺģ=100, о=1000,ͷϵ=2000(ʵõ)㷨ĵȽ(μ[3]),Ƚϼ4 (CPUʱ=㷨õŽ(ʱ)586ʱ(s))
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

4 㷨ĽȽ

GAEPSAGASAEP
Ӧֵ185.43187.01181.51180.72
976772668869
CPUʱ275(s)150(s)450(s)260(s)

(ע2ͱ3ֵıΪ塢Ƿ) 
ʵ,㷨ҵΪĵȽ,깤ʱ㽻Ҫɱ4֪SAEPõĽ,ļӹʱ(180.72)̣EPõĽ,ļӹʱ(187.01)EPCPUʱΪ150(S),,SAGACPUʱΪ450(S),ۻģ˻㷨(SAGASAEP)õĽڽ㷨(GAEP),ٶȾö,SAGACPUʱΪGA1.64,SAEPΪEP1.73ܽ滮(EPSAEP)ٶȱŴ㷨(GASAGA)ö,GACPUʱΪEP1.83,SAGAΪSAEP1.73ϱȽϽ,SAEP㷨,  , ҲϿ죮
6
(1)㷨JSPЧеģ(2)SAһĸʽܽϲĸ,Ľ˽㷨ѡ,˷GAEPġ,㷨Ȼģ˻㷨ٶȿö࣮(3)滮(EPSAEP)ٶȱŴ㷨(GASAGA)ö࣮(4)óͷ˹ĽԼнⷨ˻ԼͲ˳Լ㷨ڶԸ彻ͱʱ,ʹҪƶĻֻƶƶ,л򽻻,Ч,ӿŴٶ,Ӷʹ㷨ǳ(4),ɴ˵㷨JSPЧԣ
߼
(1941-),Ů,ڣоΪ˹ܣ
ֱ(1963-)УڣоΪԶƣ
ߵλҵѧԺ򽭡212003
ο
1Golding D E Genetic Algorithms in Search, Optimize and Machine Learning. New YorkAddiso Wesley, 1993372285
2 ȣ¼Job Shopϵͳϵͳѧ,1997, 9(4)4250
3 Job-shopĻģ˻滮Ϣ,1999, 28(2)
ո:1998-12-24
