ѧ
JOURN AL OF SOFTWARE
1999ꡡ1010ڡVol.10No.101999



һҵĿٵ㷨
 桡

ժҪҵĵ(job oriented scheduling,JOS)ʵҵ(job shop)еõձӦ,Ļ˼ǽҵһذŵ.һֻڼJOSϵͳĿٵ㷨,㷨ָҵĿеʼͽʱŹŹʽǰŵĹ.ͨ¼޸ÿһЧʱ۵İ취ٲÿһʱ۵ʱ,Ӷ˼Ч.ʵϵͳӦñ,㷨ڴģȾкǿԽ.
ؼʡJob oriented scheduling(JOS),ʽ㷨,ʱ,Job Shop.
ͼšTP393
A Fast Job Oriented Scheduling Algorithm
HUANG Qi-chun CHEN Qi YU Rui-zhao
(Institute of Artificial Intelligence Zhejiang University Hangzhou 310027)
Abstract Job oriented scheduling (JOS) has been the most commonly used technique in actual job shop scheduling. It loads jobs one by one onto machines. In this paper, the authors present a fast scheduling algorithm of computer-based JOS system, the algorithm assigns feasible schedule start and finish times to the operations of a job by loading them forward or backward onto the capacity constrained machines. The computation time to find the feasible time slot on the machine is reduced by log and modify each machines feasible time slot. Thus, the computational efficiency is substantially improved. Experimental testing shows that the algorithm has significant merits for large size problems.
Key words Job oriented scheduling (JOS), heuristics algorithm, time slot, job shop scheduling.
ЧؽӦõҪ,Job Shopһ͵.ĵо,ʽ㷨ǽʵӦҵȵΨһЧķ.Ŵ㷨[1]н㷨[2]㷨в,Щн϶о,Ҳȡ˽ϺõЧ,δʵʵеõӦ.ʽоǲʽ[3,4],ԭ,ÿ̨ϵĵͨѡʺڸ̨ϼӹһ,Ϊϸȼƻ,һ÷淽.ڷϵͳʵĶ̬,Ҫ,ʱķѡģͷԼûԷĽ̶ܳȵ.
ʽͬ,һʽҵĵ(job oriented scheduling,JOS)[5,6],ҵķʽе,ֻĳһҵвѾ֮ſһҵ.JOS÷ģ,ϸȼƻͨҵһһذŵͬĻ.һͬһ㹤ҵʵӦõֹȷõĸͼǳ.ͼЧ.Ȼֹɸͼǳķʱ,رǶЩģ,ֹ޷Ӧʱ,ڼJOSϵͳȴܺܺõؽһ.
ĽһҵJOSģȴ,һֻʱ۵ҵ㷨.
1ҵĵģ
1.1 JOSģ
һӳJob Shopһģ:
.ÿжӹģ
.ÿӹಢеĻ
.ÿӹı봦ҵ
.ͬĻвͬԼ
.ÿһҵһ()ɣ
.ÿֲҪԴ,ǻ
.ÿ̨ڲͬ͵Ĳ,ÿֲ̨
.ÿֲռĳһʱ䣻
.֮ͬʱ䣻
.ͬҵвͬĵȽʱԼ
ĳЩܻԼ,ǾÿһҵĲָϵĿܵʼʱͽʱ.ȵĿ,Ըҵ,Ҫô,Ҫôʹָʱ.
1.2 ȴ
ȹǸҵϵҵĵ˳,ϵȼʱȺɳʱ䡢ҵԼװϵĴ.ȷһʽ,Ź򷨺Ź.Ź򷨶ÿһҵĵȴӵ1ʼǵȵʼʱ,ݲ̼໥ϵ,ÿһŵмӹʱĻ.Ź򷨵Ŀʹҵ.Ź򷨶ÿһҵĵȴһʼǵȵĽʱ,ҵʱҪ󼰲̵Լ,ÿһŵмӹʱٵĻ.Ź򷨵Ŀʹҵʱӽָҵʱ.
ɴ˿Կ,JOS㷨ĹؼڽͬĲŻԼĻ.ÿһڲͬϵĵʼʱͽʱͨڸĻѰ(Ź)(Ź)Чʱɵ.ĳһ,ҪʹϵʱЧ,:(a) ʱδĲռ;(b) ʱ۵ĴСڻڸòʱ;(c) ʱ۱Լ.,ȹ̵ļʱЧʱ۵Ĳ,һ,ĳһϵȵĲԽ,ȵԽ.
Ϊ˼ʱ۵ʱ,Ƕÿһ̨һʱۻ,ڻд洢Щ϶0ʱֵ,ȹ̾ǲʱۻ,ҵʵʱۺԻ޸ĵĹ.ʱ۵޸Ĺ̴3:(a) ʼʱͽʱʱ۵ʼʱ,ʱ,ʱ1;(b) ʼʱͽʱʱ۵ʼʱһǶӦȵ,ʱ۵ıֻʱֵı;(c) ʼʱͽʱʱ۵ʼʱӦ,ʱӦʱ۽ʧ.Ȼ,ʱ۵ŵ,˵Խ,㷨ʡʱԽ.
2 
һҵ,IҵҪ,ÿһҵi(i=1,2,,I)Ji,ҵiÿһ(i,j)(j=1,2,,Ji)ҪŵԼӹòļӹkĵl(l=1,2,,Lk)̨,LkΪüӹĵĻ.ȵ㷨ڻѰٵЧʱ.i,j,k֮Ĺϵڵ֮ǰѾȷ,(i,j)ָļӹkϽмӹ,i,j,klĹϵͨȹ̼ȷ.
ȸŹ㷨,(i,j)ȵ(k,l)ϵĵʼͽʱͨʱʵֵ.
(1) (i,j)ܵʼʱ(Psti,j,k,l).ʩ(i,j)ϵԼ,Ҫ:(a) (i,j)Ϊĳһҵĵ1,Psti,j,k,lΪҵʼʱ;(b) (i,j)ĳһҵĵ1,Psti,j,k,lΪһĽʱ;(c) ǰһĽʱ俼ȼԼʱ;(d) (k,l)Ŀʱ.
(2) (i,j)ܵĽʱ(Pfti,j,k,l).Psti,j,k,lϲ(i,j)(k,l)ϵļӹʱõ.
(3) (i,j)ڻ(k,l)(l=1,2,,Lk)ϼӹĿʼͽʱ(Fsti,j,k,l,Ffti,j,k,l).Ǹʱ(Psti,j,k,l,Pfti,j,k,l)(k,l)ϵʱ۽бȽϺȷ.
(4) (i,j)ĵȽʱ(SFTi,j,k,l)ϲͬϵļȡСĿнʱ.(i,j)ĵʼʱ(SSTi,j,k,l)ȽʱӦСʼʱ,⽫֤.̨̨,˳ȡǰһ̨.
㷨ЧʾѰҿеʼͽʱ(Fsti,j,k,l,Ffti,j,k,l),ҵ(Psti,j,k,l,Pfti,j,k,l)ƥʱ,Ϊ,Ǹÿһ̨(k,l)һʱۻ洢ͬʱֵ.Tssk,l,mʾ(k,l)ϵmʱ۵ʼʱ,Tfsk,l,mʾ(k,l)ϵmʱ۵Ľʱ,m=1,2,,n,nΪʱ.
,ȸŹ򷨵Ȳ(i,j)(k,l)ϵ㷨.
ʼ: Psti,j,k,l= Pfti,j,k,l= Fsti,j,k,l= Ffti,j,k,l= SFTi,j,k,l= SSTi,j,k,l= 0
Tssk,l,m = 0, Tfsk,l,m = tmax (tmaxΪһ㹻ֵ,ϵͳȹģ
ȷ)
S1. (k,l)(l=1,2,,Lk)һ˳.
S2. ݲ(i,j)ԼȷPsti,j,k,l.
S3. ͨ²Fsti,j,k,lFfti,j,k,l.
S3.1. Pfti,j,k,l,Psti,j,k,lϲ(i,j)ڻ(k,l)ϵĲʱȷ.
S3.2. l>1Pfti,j,k,l3 Ffti,j,k,l(l{1,2,,(l- 1)}),˵ò
̨ϼӹ,S1,ȡһ̨¼,ֱL=Lk,ִS3.3.
S3.3. ѰҺʵʱ.
S3.3.1. ʱ(Tssk,l,m Tfsk,l,m)m(1,2,,n)ʱ˳С.
S3.3.2. Pfti,j,k,l>Tfsk,l,mPfti,j,k,l- Psti,j,k,l >Tfsk,l,m- Tssk,l,m,
˵ʱ۲,ȡm=m+1,S3.3.1.
S3.3.3. Psti,j,k,lTssk,l,m,
Psti,j,k,l=Tssk,l,m,
Pfti,j,k,l=Psti,j,k,l+(i,j)Ĳʱ,
S4. ȡFsti,j,k,l =Psti,j,k,l,Ffti,j,k,l =Pfti,j,k,l.
S5. ظִS1S4ֱl=Lk.
S6. (i,j)ĵʼʱ͵Ƚʱʽ:
SFTi,j =SFTi,j,k,p =min{Ffti,j,k,l}, l=1,2,,Lk,
SSTi,j =SSTi,j,k,p =Fsti,j,k,p.
в(i,j)ȵ(k,p), p{1,2,,Lk}
S7. 4޸ʱֵ:
(1) Tssk,l,m=Fsti,j,k,pTfsk,l,m=Ffti,j,k,p,ɾʱ(Tssk,p,m Tfsk,p,m);
(2) Tssk,l,m=Fsti,j,k,p,ʱ(Tssk,p,m Tfsk,p,m)Ϊ(Ffti,j,k,p Tfsk,p,m);
(3) Tfsk,l,m=Ffti,j,k,p,ʱ(Tssk,p,m Tfsk,p,m)Ϊ(Tssk,p,m Fsti,j,k,p);
(4) ,Ƚʱ(Tssk,p,m Tfsk,p,m)Ϊ(Tssk,p,m Fsti,j,k,p),
һʱ(Ffti,j,k,p Tfsk,p,m).
Ź㷨Ź㷨Ļ˼һ,ֻǼǴӹ.,ȹȷPfti,j,k,l,¼ȷ:(a) (i,j)Ϊһ,Pfti,j,k,lΪҵĽʱ;(b) (i,j)һ,Pfti,j,k,lΪһʼӹʱ;(c) ݺһʼӹʱ俼ȼʱõ;(d) Ĺʱ.Fsti,j,k,lFfti,j,k,lÿ̨ٵĿʱ(Psti,j,k,l,Pfti,j,k,l)ʵʱ̱Ϊ:
S3.3.1. ʱ(Tssk,l,m Tfsk,l,m)(m(1,2,,n))ʱ˳ӴС.
S3.3.2. Psti,j,k,l<Tssk,l,mPfti,j,k,l- Psti,j,k,l >Tfsk,l,m- Tssk,l,m,˵ʱ
۲,ȡm=m- 1,S3.3.1.
S3.3.3. Pfti,j,k,l3 Tfsk,l,m,
Pfti,j,k,l=Tfsk,l,m,
Psti,j,k,l=Pfti,j,k,l- (i,j)Ĳʱ.
(i,j)ĵʼͽʱʽ:
SFTi,j =SFTi,j,k,p=max{Ffti,j,k,l}, l=1,2,,Lk,
SSTi,j =SSTi,j,k,p=Fsti,j,k,p.
,(i,j)ȵ(k,p), p{1,2,,Lk}.
3ӦʵȽϷ
ҵĵ㷨,Chung-HsingYehĻڲĿ㷨Ч(¼Ʋ㷨)[6].˼ǽͬһʱ϶Ϊ0Ĳʽ洢Ϊһ,,Чʱʱ,ͨ˶0ʱ۵ıȽж,Ӷʱ.ʵַʽͨ¼ÿһĽǰ(dfok,l(i,j))ͽ(dpok,l(i,j))ﵽ.㷨Ų,ʱȻһ㷨ʼ,Ҳķѽ϶ʱ.
Ļʱ۵Ŀ㷨(¼ʱ㷨)ֱӵķʽ¼ÿһ̨ϵЧʱֵ,Ӷʱ.㷨ѾʵMRP-ϵͳӦ.ĳ𹤳ȹΪ,һ㷨㷨ʱ㷨ЧʽбȽ,ȽϳԹϵݿ洢Ϣ,ǰ˿ΪPowerbuilder,ݿSybase,ڱ200,ڴΪ32׵΢.ý𹤳ҵΪ99,ܲΪ1 084,Ϊ26,ֱȡ6ֲͬ,3ַмȽ,1.
1 һ㷨㷨ʱۻ㷨ЧʵıȽ

ҵ()һ㷽ʱ(s)㷨ʱ(s)ʱ㷨ʱ(s)
131001316.78113.42326.762
222002034.31626.39733.851
414002382.26660.93868.748
5660023138.202102.372101.739
7180025234.130161.469135.576
99108426391.604261.069181.197

 
ɱ1Կ,ҵ13,100ʱ,㷨ʱΪ13.423s,Ϊһ㷨,ķʱΪ16.718s,ʱ㷨ķʱΪ26.762s,200~600֮ʱ,㷨ʱ㷨һ㷨Ҫ,ߵò.㷨ʱ㷨Ч,8001 084ʱ,㷨Чʱһ㷨ֱ45%50%,ʱ㷨Чʱһ㷨ֱ73%116%.˵ʱ㷨ԴģĵȾкǿԽ.ͼ1ǵȹĳʱۻ仯,óϵȵܲΪ330,ʱֵΪ10,ɴ˿ɼ,ȹЧʱ۵ʱŵ̫.

ͼ1ʱҵ
ϱ,ʾʱۻĿ㷨ӱһJOS㷨Ч.Ȼŵȹģ,㷨ķѵʱ֮,ǳʼʽ,һ㷨ȫӦʱȻʹģĵϵͳ.
4 
ҵļ㸴ԷչʵʹҵȵЧ,ŵȹģԼҵ价Ķ̬ԼȳΪȻ.ڼJOS㷨ܹṩġеĵȼƻʵеõӦ.ĿJOS㷨˼㴦ʱ,ԴģĵиԵЧ.
עͣоõȻѧ
߼飺1972,ʿ,ҪоΪ˹ܣERP.
棺1963,,ҪоΪ˹,IDSS,ERP.
ȣ1937,,ʿʦ,ҪоΪ˹,ݲֿ,ھ
ߵλ:㽭ѧ˹о  310027
ο
1 ¶,ȫ,.Ŵ㷨Job-Shop ⷽ.ѧ,1998,9(2):
39143
(Chen En-hong, Liu Gui-quan, Cai Qing-sheng. A genetic algorithm based job-shop 
scheduling problem solving method. Journal of Software, 1998,9(2):139143)
2,ϯԣ.Ӧòн滮Job-Shop.ģʽʶ˹,1997,10
(4):344350
(Fang Jian, Xi Yu-geng. Using parallel evolutionary programming to solve the 
job-shop scheduling problem. Pattern Recognition and Artificial Intelligence, 
1997,10(4):344350)
3Sun D, Batta R, Lin L. Effective job shop scheduling through active chain 
manipulation. Computers and Operations Research, 1995,22(2):159172
4Kim Y D. A backward approach in list scheduling algorithms for multi-machine 
tardiness problems. Computers and Operations Research, 1995,22(3):307319
5Hastings N A J, Marshall P H, Willis R J. Scheduled based MRP: an integrated 
approach to production scheduling and material requirements planning. Journal 
of the Operational Research Society, 1982,33(11):10211029
6Yeah Chung-Hosing. A fast finite loading algorithm for job oriented scheduling. 
Computers and Operations Research, 1997, 24(2):193198
ոڣ1998-07-06޸ڣ1998-11-10
