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



ԼӦЧʽ
㷨Job-shop*
ʥ顡ΰ
ժҪһԼӦЧʽ㷨Job-shop⣮ڻ㷨УӦйԪƫúȨֵӦȡֵԣõĿн⣬ʽ㷨ֱǿܡȷŽ߿н˱Ļ㷨ĿЧԣ
ؼʡԼӦ磬ʽ㷨Job-shopȣԹ滮
USING CONSTRAINT SATISFACTION ADAPTIVE NEURAL NETWORK
AND EFFICENT HEURISITICS FOR JOB-SHOP SCHEDULING
YANG ShengxiamgWANG Dingwei
(Department of Systems Engineering,Northeastern University,Shenyang110006)
AbstractBased on constraint satisfaction this paper proposes a new adaptive neural network,and an efficient heuristics hybrid algorithm for Job-shop scheduling. The neural network has the property of adapting its connection weights and biases of neural units while solving feasible solution. Heuristics are used to improve he property of neural network and to obtain local optimal solution from solved feasible solution by neural network with orders of operations determined and unchanged. Computer simulations have shown that the proposed hybrid algorithm is of high speed and excellent efficiency. 
Key wordsconstraint satisfaction adaptive neural network,heuristics,Job-shop scheduling,integer linear programming
1
ǰʱԴ1ݣJob-shopһิҼߴԵ⣺m̨ӹnÿضļӹ˳·ߣĿȷÿ̨ϸļӹ˳򼰿ʱ䣬ʹĳָ꣨ڣС2ݣFoo S.Y.Job-shop3ݣһЩԴо4,5,6ݣЩ϶ǷӦģǰȷԪƫúԪ֮ȨֵĲûԼϵӦ磨CSANNصʽ㷨Job-shop⣮CSANNԪƫúȨֵйӦȡֵԣõĿн⣬ʽ㷨ֱǿܡȷŽ߿нʵ˻㷨ĿЧԣ
2Job-shopѧģ
N={1,,n}M={1,m}niǹiĹOikqʾikڵq̨ϼӹĹ俪ʼӹʱͼӹʱ䣨ӹʱ֪ΪSikqTikq,SieiqTieiqֱǹiһĿʼӹʱͼӹʱ䣬ridiֱǹiͶʱͽޣPiǹ\ϣOikpOikqRqʹûqйOikqļϣС깤ʱΪָ꣬Job-shopѧģͿɲԹ滮

s.t.
(1)
(2)
(3)
УĿ꺯Eȡйһ깤ʱֵڣʽ1ʾͬһĲͬͬʱӹұ㹤˳Լʽ(2)ʾÿ̨ͬһʱֻܼӹһԴԼʽ3ʾͶʱͽԼ
3ԼӦ
CSANNͨԪͼ1ϣֱıʾ򿪹ʱSTࣨStarting TimeԪ˳ԼǷSCSequence ConstraintԪԴԼǷRCResource ConstraintԪɣԪͨ໥ɹ˳ԼSCģԴԼRCģ飮SCģÿԪһSCSTԪɣͼ2жͬһĹ˳ԼǷõ㣬RCģÿԪһRCSTԪɣͼ3жԴԼǷõ㣬˳ԼԴԼʱͨʵķԼͻ


ͼ1ͨԪģ

ͼ2SCģ鵥Ԫ

ͼ3RCģ鵥Ԫ
ͨԪɶźŵԼȨͺԺf(.)ɣͼ1ͼ1УSTԪԼĹӹʼʱ䣬
(4)
(5)
У4ʽұߵĵһ͵ڶֱصSCRCԪķãSTԪSTiһʱ̵5ʽTSTiSTiӦļӹʱ䣮
SCࡢRCԪɼSTԪֱжϣ1ʽʾĹ˳Լ2ʽʾĻԴԼǷ㣬ʽͬʾ
(6)
(7)
УCi=SCiRCiBCiԪSCiRCiƫ趨ͼ2ͼ3ͼ2\PiȨֵƫȡֵ磨8ʽʾͼ3OikqOjlqRqȨֵƫȡֵtʱ̾Sikq(t)Sjlq(t)ɣ9ʽȷSikq(t)Sjlq(t)ɣ10ʽȷ
(8)
(9)
(10)
ʽУWĿɵ
Job-shop⣬CSANNĽģ裺ȷnͻmiĹniȷSTԪĿΪÿSTԪӦOikqΪSTikqݹҪȷPiRqϣSCģRCģ飮
4㷨
Job-shopĻ㷨CSANNʽ㷨ɣCSANNԼͻõеȽ⣬ʽ㷨ֱǿܡȷŽ߿н
4.1ʽ㷨
㷨1ڹ򻥻㷨йtʱ̣ͬһڹ򡡡Pi(iN)Sikp(t)SilqʱOikpOilqĿʱԻӹ˳Լ˳ͻɵķڴУ㷨
(11)
һ棬йУڹ˳ԼͻķںԴԼͻķܴ֮ìܣӶɡ󣬼ѭӦнȶ״̬ʱͨͬһϵڹһʱʱԻӹ˳򣬴Ӷпֵܳġȷõн⣬㷨£OikpOjlqRq(qM),Tqikjl(t)Tʱ
(12)
УTqikjl(t)tʱ̣qϼӹĹOikqOjlqѾҪĴT趨ĳ5
㷨2ȷ㷨CSANNõĿеȽ⣬ڲıϹ£лѹеȴͬʱйɼӹʱ䣬̿нڣõȷŵĿеȽ⣮㷨ǰʱС˳򣬽йĿʱ޸
(13)
УSjlp㷨ǰOjlpĿʱ䣬Sikp㷨кõȷŽOikpĿʱ䣬Oik-lqOikpͬһiĽǰOjlpǻpOikpĽǰ򣮣13ʽʾOikpĿʱǰOik-lq깤ʱSjlp깤ʱ䣮
4.2㷨
㷨Job-shopΪ
(1 CSANNģͣ趨TWֵ趨д
(2 ͳһʼӹʱISTikpΪӦSTԪĳʼ
(3 SCģԪ678ʽOSCikp(t)OSCikp(t)0ʾ1ʽӦĹ˳Լ㣬򰴣14ʽ11ʽ㷨(1ͣ5ʽ޸Sikp(t+1)Silq(t+1)
(14)
(4 RCģԪ67910ʽORCqikjl(t)ORCqikjl(t)0ʾ2ʽӦԴԼ㣬򰴣15ʽ12ʽ㷨1ͣ5޸Sik1(t+1)Sjlq(t+1)ظ3Ͳ4ֱõн⣮㷨2
(15)
(5 㷨2ã㷨2õȷŽ⣻
(6 дδﵽ趨дز2ֹͣУý⣮
5ʵ
1һ66 Job-shopԭʼ[5]s,m,tʾĵsڵm̨ϼӹӹʱΪtʾȺ˳ֵСڣ55
166Job-shopԭʼ

11,3,12,1,3(3,2,64,4,7(5,6,36,5,6
21,2,82,3,53,5,10)4,6,10)(5,1,10)6,4,4
31,3,52,4,43,6,84,1,95,2,16,5,7
41,2,52,1,5(3,3,54,4,35,5,86,6,9
51,3,92,2,33,5,54,6,45,1,36,4,1
61,2,32,4,33,6,94,1,10)5,5,46,3,1

⣬ַзʵ飺1=CSANN+㷨12=CSANN+㷨1+㷨2ʵиΪT=5W=0.5иͶʱΪ00ʱйͷŻɼӹ깤ʱԼ趨ڣйĽԼÿַºͲͬ깤ʱԼ100ʵ飬Уһʵʼ½еģеĹʼʱ䶼Ϊ㣬99ʵУгʼиʼʱȡ[0100]֮ľȷֲõͳƽֵ2ʱΪ0ʾ1룩ͼ4ͼ5ֱǲ÷1ͷ2깤ʱԼΪ100ʱͬһĳʼĽͼ[i,j]ʾiĵj򣩣

ͼ41

ͼ52
ͼ4ͼ5ɼ㷨2ãĽָõԵߣ100Ϊ66ͼ6ǲ÷2깤ʱԼΪ58ֵʱʼĽ

ͼ62õŽ
266ʵ

ⷽ깤ʱԼʼ
ʱ趨ָE
ƽ/С/ʱ䣨룩
ƽ/С/
12000711
1200106.56/99/1210.10/0/1
22000691
220076/61/940.17/0/1
11000711
110099.50/99/1000.18/0/1
21000691
210075/60/930.21/0/1
158ֵ05820
158ֵ58/58/585.53/0/43
258ֵ05625
258ֵ57/55/586.6/0/44

6
ʵ(1깤ʱΪָʱʼӹʱ俪ʼڸ깤ʱԼ÷1ͷ2һ㶼ܿٵõϺõĿн⣻(2ʵ깤ʱԼ÷1ܹٵõϺõĿеȽ⣬ָûڵ趨(3÷2Բͬ깤ʱԼ͸ʼʱ䣬ܵõϺõĿеȽ⡢ŽŽ⣮ʵJob-shopĻ㷨ǿЧģ
*Ȼѧ(No.69684005)͹863ƻCIMS(No.863-511-9069-003)ͬ.
߼飺ʥ飬У26꣬ʿоΪ磬Żܵȵȣ
ΰУ50꣬ڣʿʦоΪƻۣģߣŻ
ߵλѧϢѧ빤ѧԺϵͳϵ110006
ο
1Baker,K. R.,Introduction to Sequence and Scheduling,John Wiley & Sons,New York,1974
2Conway,R. W.,Theory of Scheduling,Reading Mass: Addison-Wesley ,1967
3Foo,S. Y. and Takefuji,Y.,Integer-linear Programming Neural Networks for Job-shop Scheduling,Proc. IEEE IJCNN'88,San Diago,1988,341348
4Zhou D. N.,Charkassky,V.,Baldwin,T. R. and Hong,D. W.,Scaling Neural Network for Job-shop Scheduling,Proceedings IEEE Int. Joint Conference on Neural Networks,1989,889894
5ںȷӦоѧʿģ1997
6Willems,T. M. and Brandts,L. E. M. W.,Implementing Heuristics as an Optimization Criterion in Neural Networks for Job-shop Scheduling. Journal of Intelligent Manufacturing,1995,6,377387
1998-03-23ո
