Զѧ
ACTA AUTOMATICA SINICA
1997 23 1 Vol.23 No.1 1997



ͬȲд϶ĵ
һ÷֣Ӧƽ
ժҪnmͬȲдϴʹʱСķȵȷԵ۵һ. һ㷨Bound Fit㷨ٺMULTIFIT㷨һãʱȴMULTIFIT㷨. 
ؼʡͬȲд ȵȣʽ㷨.
INDEPENDENT TASKS SCHEDULING ON IDENTICAL
PARALLEL PROCESSORS
KANG YIMEI
(Beijing Institute of Computer & Electronics Application Beijing 100080)
ZHENG YINGPING
(Institute of Automation, The Chinese Acadamy of Seiences Beijing 100080)
AbstractThe problem of nonpreemtively scheduling n independent tasks on m identical parallel processors in order to minimize the makespan is one of the fundamental problems of deterministic scheduling theory. In this paper, an algorithm called Bound Fit is presented. This algorithm has the same or better worst case performance with shorter running time.
Key wordsIdentical parallel processor, nonpreemptive scheduling, heuristic.
1
nmͬȲдϴʹʱСķȵȷԵ۵һ. ֪nT={T1,T2,,Tn}ʾ񼯣mM={M1,M2,,Mm}ʾĴʱΪpipiΪi=1,2,,n. 񰴴ʱ˳Уp1p2ݡpn. Ci(i=1,2,,m)ʾiʱ䣬Cmaxʾʱ䣬ʾŵȵʱ. 
һNP1ݣҵһʽʱ㷨. ˣֻ˶ΣȥѰЧĴ㷨. ⷽʽ㷨LPT㷨2ݺMULTIFIT㷨3. MULTIFIT㷨ܱLPT㷨. 
MULTIFIT㷨Coffmanף3ģһֻbin-packingFFD(First Fit Decreasing)ĵ㷨. ʱѰʹmϵСʱ. FFDǶÿһ̶Ŀ˳򽫰ʱ˳еԼСĴ. 
Donald K. Freisen ף4֤MULTIFIT㷨Ϊ(1.20+(1/2)k)C*maxkǵ. MULTIFIT㷨ʱ临ΪO(n log n+kn log m),Ĵʱʱ. 
C.Y.Leeף5һֽLPT㷨MULTIFIT㷨ķԴﵽʱĿģЩ±Bound Fit㷨ʡʱ䣬ܴﵽܺõ.
2Ԥ㷨
塡MiѰŵʱΪMiĵȳȣΪLi.
Ȼŵ
(2.1)
ʽȺųʱԤ㷨Ϳҵŵ. 
Ԥ㷨
1. B=
2. Lj=0(j=1,2,,m),i=1.
3. ٴһj(1jm)ʹLj+piBTiʹLj+piBСĴ. 򣬽TiʹLj+pi(j=1,2,,m)СĴ. 
4. in,i=i+1ת3.ͣ.
ֻҪŵȵʱΪmax,Ԥ㷨ͿɵõŵȣԤ㷨һܵõŵ. 
1.k-1Ԥ㷨õȵʱC(k-1)maxmax(B(k)=C(k-1)max,kԤ㷨õȵʱC(k)max=C(k-1)max,k3. 
֤A=max,C(k-1)max=Aʱҵŵ. 
k=2ʱk-1=11Ԥ㷨ʱB(1)=A,ֻҪC(1)maxAһڵʱʹдĳȶB(1). kΣ2Ԥ㷨ʱB(2)=C(1)maxԤ㷨ɵõϴȫͬĵȣC(2)maxC(1)max.
ˣk3ʱB(k)=C(k-1)maxԤ㷨k-1ȫͬC(k)max=C(k-1)max. 
֤. 
3Bound Fit 㷨
2.k3ʱԤ㷨ʱC(k)maxC(k-1)max-1ĵȣB(k)=C(k-1)max-1һɵõC(k)maxC(k-1)max-1ĵ. 
֤ɶ1֪k3ʱB(k)=C(k-1)maxõC(k)max=C(k-1)max. ڼٶʱΪ˵õõĽB(k)=C(k-1)max-1Ԥ㷨ȴC(k)maxC(k-1)max-1ĵʱͿɵõ˵. ֮B(k)Ϊֵ޷õC(k)maxC(k-1)max-1ĵȣõȵʱC(k)maxC(k-1)max-1.
֤. 
Ϸõ㷨. 
Bound Fit㷨
1. B(1)=max,k=1.
2. Lj=0(j=1,2,,m),i=1.
3. ٴһj(1jm)ʹLj+piB(k), TiʹLj+piB(k)СĴ. 򣬽TiʹLj+pi(j=1,2,,m)СĴ. ıӦLj.
4. in,i=i+1ת3. 
5. k3,ͣ. k=k+1k3B(k)=,ת2k3B(k)=,ת2. 
k3B(k-1)Ԥ㷨ȣõȼΪBound Fit 㷨Ľ. 
Bound Fit㷨ɵõMULTIFIT㷨ͬõĽ. 
.£m=3, n=8, p1=100,p2=p3=90,p4=42, p5=41, p6=30, p7=20, p8=7.
1Bound Fit㷨MULTIFIT㷨Ƚ

kCmax
Bound FitMULTIFIT
1150210
2142172
3141151
4142
5141

ŵȵʱ141. Bound Fit 㷨MULTIFIT㷨õŵȣMULTIFIT㷨5εõŵȣBound Fit㷨ֻ3ε1ʾ. 
Ƕ100ӽз棬Bound Fit㷨ĵܱMULTIFIT㷨ĵ. 
4ܷ
CBFmaxʾBound Fit㷨õȵʱ䣬ǿ֤Ķ. 
3.CmaxFFDmϰһȵʱ䣬
CBFmaxCmax
֤÷֤֤. 
һFFDmϰõȵʱCmaxCBFmax. CmaxFFDmϽȫõĵȵʱ䣬FFDC=BܽnȫmʱŷȫͬôB=CmaxBound Fit㷨һɵõFFDͬĵ. ɶ2֪B=Cmax-1ɵCBF'maxCmax-1ʱСڻCmax-1ĵʱBound Fit㷨ٿɵCBFmax=Cmax. ìܣ֤. 
ɶ3 ɵ. 
1.Bound Fit㷨õĵMULTIFIT㷨k=ʱýͬ. 
Rm(BF)ʾBound Fit㷨ľܣ4Bound Fit㷨. 
4.TRm(BF)1.20.
֤ף4֤MULTIFIT㷨ľRm(MUL)1.20+()k,1֪



ʽĿĵõȻѧ.
ߵλһ÷Ӧüо100081֣ӦƽйѧԺԶо100080
ο
[1]J.D Ullman. Complexity of sequencing problems. Computer and Job/shop scheduling Theory. New York, 1976. 
[2]Graham R L. Bounds on multiprocessing timing anomalies. SIAM J. Appl. Math., 1969, (17)416-429. 
[3]F G Coffman Jr., Garey M R, Johnson D S. An application of bin-packing to multiprocessor scheduling. SIAM J. Compt., 1978, (7)1-17.
[4]Freisen D K. Tighter bounds for the MULTIFIT processor scheduling algorithm. SIAM J. compt., 1984, (13)170-181. 
[5]C Y Lee, David Massey J. Multiprocessor scheduling: combining LPT and MULTIFIT. Discrete Appl. Math., 1988, (20)233-242.
ոڡ1994-04-20


