Ϣ
Information and Control
1999ꡡ281ڡVol.28No.11999



ģFlow-shop⼰ŴŻ
ܺơΡ

ժҪоģµFlow-shop⣮ʵмӹʱĲȷԣӦģӹʱͳʾһµģȽϷһֽģFlow-shopЧŴ㷨ʵ
ؼʡģģFlow-shop⣬ģʱ䣬Ŵ㷨
FUZZY FLOW-SHOP PROBLEMS AND ITS' GENETIC OPTIMAL
XIONG HongyunHE Yue
(Chang Sha Railway University, Chang Sha, 410075)(Xi'an JiaoTong University, Xi'an, 710049)
AbstractThis paper examines fuzzy flow shop scheduling prob lems with imprecision durations. Instead of exact number , fuzzy numbers are ide ally suited to represent these duartions. A new comparison method for fuzzy numb er is introduced, and a genetic algorithm is constructed for fuzzy flow shop opt imization. In the end, the simulated results are shown.
Key wordsfuzzy numbers, flow-shop scheduling problem, fuzzy m akespan, genetic algorithm

1ģFlow-shop
Դ1954꣬Johnsonһϵͳ̨˳ӹFlow-shop ۷ϵĸӻʵӦеձԺҪԣFlow- shopһֱΪоҪ֮һ
ǰоУеʱӹʱ䣩ǾȷģԼӹʱ䵯Կɱ о\ʵϣڸأϡ˲ ̶ȡȱڡȵӰ죬ȷļӹʱǺܻõģĹ ߻ṩǵҲֻһԼݵĿܱ仯Χ繤Aļ ʱԼΪ3040ӣ󲻳45ӣС25ӣ
ֲȷͳĴǣ
(1) ǾȷһȷʾȻý⾫ȷķ⣬ַ ȱ㣬һģͷ˱仯Ľƫһǻõʽϴͳı ﷽ʽֱۣһ򵥵ģFlow-shopΪģӹ1þȷģõĽ2
122ģ/ӹ

JobOp.Fuzzy Duration(TrFN)CrispMach.
AA12121212121M1
A21516242520M2
BB12121212121M1
B21919191919M2


222Ƚ

ScheduleObj(Crisp)Obj(Fuzzy)
S1A1B16162.75
A2B2
S2B1A16262
B2A2


ӱ2нɼ£S1ʱΪ61S262ģ£S2ȥģʱΪ62S162.75
(2) ʷֲʾķֲִҪʷǿ֪ ģʵҪЩǺѵģһŻڴҲѣ
ģķչӦģʾʹȷ˹㷺ע2,3ݣʾ޷ԽԺӦǰӦģ ʾȷļӹʱ䣬оģӹµFlow-shop⣮
ģFlow-shopУһξԣļӹ˳ȷģ깤ʱ䣬Լܵʱ(makespan)ģģʵеı﷽ʽһµģñʾģanļӹ˳ΪS=S1, S2,  , Sn SiΪӹλiĹţi,kʾSiMkϵģӹʱ i,kʾSiڻMkϵģ깤ʱ䣬i=1,2,,nk=1,2,,m i,kɰ¹ʽ㣺
(1)

ʽкmxֱʾģļӷȡֵFlow-shopĿʹܵ깤ʱ̣minn,m
(1)пԿģFlow-shopĹؼģȽϣ² ȼҪģ֪ʶȻģһֱ۱ȽϷ Flow-shopNP-걸ģŴ㷨ķģFlow-shop ⣮ֵʵ
2ģıȽϷ
ģģһʽ1ݣģһ÷ֱֶߵķʾ õģTFNģTrFN)һģTrFN ɱΪ=(a,b,c,d)е4ֱʾε4㣮TrFN ȺʾΪ
(2)
2.1ģıȽ
ģıȽģŻһؼ⣮ܶоģıȽϷ˸ Ƚָ4ݣָDudoisPrade5Ļڸ ĸָ꣨possibility of dominance, possibility of strict dominance, necessi ty of Dominica, and necessity of strict dominanceЩָ궼[0,1] ڽбȽϣ˲ȷһһ(С)٣⼸ַ ڲֱۣȱһԵȱ㣮
ForrempsRoubens6ģȽϷ ȺȷַԼģ֮ľ룬Ҿֱۡص Dempster-Shaferۣ6ݣģԿĳĸʷֲFģĸʷֲۻʷֲF*(cumulative possibilit y distribution)ۻȻֲF*(cumulative necessity distribution)
F*(x)=sup{(r)|rx}x; F*(x)inf{1-(r)|rx},x
F*F*ֱʾģĸʷֲϡ½磬x,F*(x) F(x)F*(x)ͼ1ʾ

ͼ1ģ()ĸʷֲ

ģȽϷһֻڡģƽֵķ5ݣģΪһڸʷֲļϣģƽֵͨģĸʷֲ㣺

A*ǺۻʷֲF*صƽֵA*ǺF*صƽֵ֪ģƽֵĸʷֲ[A*,A*]һȥģķǼƽֵģ(A*+A*)/2ַģһ£
ģF()ǡĦˮƽؼSL()ʾֹ߲ɵͬSR() ʾұֹ߲ɵ
(3)
(4)


ʾͼ2ʾģĳ̶ȱʾΪC()

ͼ2ģȽ
(5)
塡(6)
򡡡(7)
Ƶɵõ¶
1 ģ
ںg:F(R)RԿɼԣ,F(R)ڣ
(8)
g:F()ȡ(max)в
(9)
ʽпԵóһۣģʱȥģܴڻʱ䣮
2.2ģĲ
ģFlow-shopѧģ(1)ʽпԿĿ꺯ŻҪ漰ģıȽԼģȡϲֽ˻ģȽϷģȡ
TrFN÷ֶεԺʾTrFNĺΪһTrFN=( 1,5,9,10.5),=(2,3.5,7.5,13)=(3,8.5,16.5,23.5) ȡ(mx)вٳΪ˼򻯼㣬ýƲ(mx)ȡ(max)ֵΪmx(,)=(2,5,9,13), max(,)ֵͼ3

ͼ3max(A,B)mx(A,B)ıȽ

3ģFlow-shopŴŻʵ
Ŵ㷨John Holland1962һŻôĵĽ ˼룬һȺĽַΪ򴮣һϵеŴѡ񡢽桢ȣϽзܺͽյóŽ⣮GAڸŻ л˳ɹӦ[7]
湹ģFlow-shopŴ㷨
(1) ģFlow-shopȾɫ
ģFlow-shop⣬һξԣļӹ˳ȷģ һFlow-shopͬıʽ3 2 7 8 6 5 4 1ʾӹţ
(2) ӦȺѡȡ
ȾɫӦȰʽ㣺JΪĿ꺯Ŀ꺯ֵļ㣬ȸ2.2ṩģȡ(1)ʽõһģʱ䣬Ȼ(6)ʽ㣬õģʱֵ
(3) Ŵ
(a). ӣ һҪԭǱظͶʧű룬 Ľ淽Уƥ佻淨PMXŽ淨OXϽ淨E RԼŽ淨LOXȣPMXERУֻܻ ظͶʧѡLOXӣλA=2 8 4 5 6 7 1 3B=8 7 1 3 2 4 6 5ѡλr1=4r2=6ӦĻηֱΪ6 7 13 2 4ɾȾɫA 3 2 4򣬵ûƬ8 5 6 7 13 2 4 뵽ûƬr1=4λǰA'=8 5 6 3 2 4 7 1ͬԵõB'=8 1 3 5 6 7 2 4
(b). ӣó췽λA=2 8 4 5 6 7 1 3ѡ λãr1=3r2=6r1r2Ļ򻥻λΪA'=2 8 7 5 6 4 1 3
(c). Ⱥ·ʽӢԣElitistȺ
4㷨ֹ׼
趨ʱ㷨ֹͣ
4ʵ
Ϊ˵㷨Чԣȶ[2]еһ44ֵӽз㣨ľ[2]ԱȽ3ӱпɼ㷨õĿֵΪ38.5[2]е㷨Ľ39.8ʵϣ38.5ΪģŵȽ ӦģʱΪ(28, 34, 43.5, 53)ΪʱԼҪ3443.5ӣС28ӣ󲻴53ӣɼõĽкܺõԣҾ봫ͳһµı﷽ʽ
3Ƚ

ģʱȥģ
㷨22,3,1,4(28,34,43.5,53)39.8
GA2,4,1,3(25,33,42,54)38.5


Ϊ˽һ֤㷨ЧԣǶף8е86, 96, 1063Flow -shopļӹʱģȻñķ⣮ӹʱģΪ[0.8x,x]㣬ΪTrFNa, b㣬Ϊ˱֤ģΪxȡc, d㣺c-x=x-ad-x=x-b10Ľ4ʵɼŻкܺõӦԺ³ԣ
4ģԱ


ģCrispFuzzy Object
OptMinMeanMax
4438.538.538.538.5
86169169169169
96190190190.8191.7
106205205206.4215.3


5
˼ӹʱ䲻ȷµģFlow-shop⣬һµģȽ һֻŴ㷨ģŻõĽкܺõ³ϰ кܺõԣΪģµƻṩһµķ;
߼飺ܺƣУ30꣬ʿоΪƻ㷨Ż
ΡᣬУ67꣬ڣʿʦоΪ̿ƣCIMϵͳ
ȣ
ߵλܺƣɳѧԺɳ410075
Ρ᣺ͨѧ710049
ο
1. ģѧԶеӦ. 廪ѧ磬1997
2McCahon C S, Lee E S. Fuzzy Job Sequencing for Flow Shop. European Journa l of 
Operational Research, 1992, 62:294301
3Fortemps P. Jobshop Scheduling with Imprecise Durations: A Fuzzy Approach. IE EE 
Trans. on Fuzzy Systems, 1997, 5(4): 557569
4Bortolan G, and Degani R. A Review of Some Methods for Ranking Fuzzy Subsets, 
Fuzzy Sets and Systems., 1985,15:119
5Dubois D, and Prade H. The Mean Value of a Fuzzy Number, Fuzzy Sets and Syste ms., 
1987,24:279300
6Forremps P, Roubens M. Ranking and Defuzzification Methods Based Area Com 
pensation, Fuzzy Sets and Systems., 1996,82:319330
7Goldberg D. Genetic Algorithms in Search, Optimization and Machine Learning. 
Addision(Wesley, Reading, MA, 1989
8. ͬ˳(Flow-shop)ģ˻. Ϣ, 1994, 2 3(3):133
139



