Զѧ
ACTA AUTOMATICA SINICA
2000Vol.26No.3P.430-432



ƽʱ
˫Ŀ
˾꿡֣Ӧƽ
ؼʡȣĿ꣬ƽʱ䣬ڹ.
BICRITERION PROBLEM IN SINGLE-MACHINE SCHEDULING WITH
MEAN FLOW TIME AND NUMBER OF TARDY JOBS
SI XinZHENG YingpingAN Xienan
(Institute of Automation, Chinese Academy of Sciences, Beijing100080)
Key wordsSingle-machine scheduling, bicriterion, mean flow time, number of tardy jobs.
1
ھƽʱڹĿ¶ԵĿооĵȻΪ蹤Nnһ̨Ͻжϵļӹÿļӹʱ䡢ʱͽڷֱΪpiridiÿʱ̵ri=0깤ʱΪCiʱFi=Ci-ri=CiƽʱÿӳTi=max0,ci-diiӳٵ(Ti>0)Ui=1Ui=0.ڹΪ
Ҫ۵(P)Ȼ£ȷһӹʹƽʱڹnT˫ĿﵽţGraham˵ʾ2ݣΪ1//,nT.
ڵе˫ĿоĿǰҪʽ
1)1//21ڱ֤Ŀ1Ϊŵ£ʹĿ2ﵽţ
2)Ч㼯ʽ1//1,2ʹĿ1,2ﵽţóĽһϵЧʽǵһĵ㣻
3)Ȩʽ1//f(1,2)Ŀ1,2ĺʽһΪ1,2ԼȨʽ.
оĿΪЧ㼯ʽ1//1,2.
mĿĵУ⼯ΪRÿһrRһmά(r1,r2,,rm)rjʾjĿֵ.ȸйЧĶ.
.rΪ˶ĿһЧ⣬sһs䣬ʹ
(i)rj(s)rj(s),j=1,2,m
(ii)rj(s)<rj(s)ĳЩj.
2NP-hard
Уǽ֤1//,nTһNP-hard.
1.1//21NP⣬1//1,2ҲNP.
ʵϣ1//21õĽض1//12һЧ.ˣ˶֤.
2.1//nTΪNP-hard.
һNP-ȫ⣬3(3-partition problem)ĶʽɣӶ֤ô˶(֤).
3.1//nTΪNP-hard(ݶ1Ͷ2Ƶô˶).
3㷨
1//,nTNP-hard⣬˵nܴʱľȷ⽫Ƿǳѵ.ڽļʣEmmonsһ5ݽչӶʹܹö̬滮ķ.
ڹNУڹڹֱΪETN=ET.ע⵽УETеĹܻύ.
1.TйSPT򣬶EйSmith6ݽ򣬼Ti=0Լ£ʹСiE.
2.Сƽ̽ڹnTӶ٣nT=TʱȡСֵTΪSPTõڹ.
3.ھйͬ깤(di=d,iN)£(ET)ʽEеԪؾTԪ֮ǰETԪؾSPT.
ΪܸЧػ1//,nTеЧ⣬ǽEmmonsһչ5ݣӶʹܹö̬滮ķ.
4.1//,nTһiڣiEn0Tʱ(n0TݪT)йϵiE(֤).
Emmonsͬʱһȹ5ݣǽչʹڱ۵.
ȹ.1//nTijֻһڣ(i)pipj(ii)pi-pjdi-djjEiT.
ݶ2ȹ1//nTĶ̬滮㲽£
step 1.ֱSPTMooreڹϡ½TTL=T-T+1LΪ̬滮еĽ׶
step 2.m=1,E1=SPTõķڵĹ1(E1)
step 3.Tm=N-EmȹTmеõйIm;
step 4.m=m+1;
step 5.For i:=1,,Tm-Im
do Emi=Em-1ȣJi
ʽJiΪTmImеһ
step 6.ȡEm=ʹ
step 7.m=L?ǣֹͣתstep 3.
󣬾͵õLЧ(T,1(E1)),(T-1,2(E2)),,(T,L(EL)).
Ȼѧ(69635030)Ŀ.
˾꿡1968.1995ڱѧ˶ʿѧλΪйѧԺԶоʿ.ҪоΪ˹DSSCIMSеӦáȡDEDSԼӶ̬ϵͳ.
֣Ӧƽ196.
ϡ1936.1959ҵϺͨѧ.ΪйѧԺԶооԱʿʦ.ҪоΪҵԶ˹ܵ.
˾꿣йѧԺԶо100080
֣ӦƽйѧԺԶо100080
ϣйѧԺԶо100080
ο
1ݡPanwalkar S S, Dudek R K, Smith M L. Sequencing research and the industrial scheduling problem. In:Elmaghraby S E(ed). Symposium on the theory of scheduling and its application, New York:Springer-Verlag, 1973:2938
2ݡGraham R L, Lawler B L, Lenstra J K et al. Optimization and approximation in deterministic sequencing and scheduling:a survery. Annal Discrete Math. 1979,5:287326
3ݡMoore J M. An n job, one machine sequencing algorithm for minimizing the number of late jobs. Management sci., 1968,15(1):102109
4ݡTanaev V S, Gordon V S, Shafransky Y M. Scheduling Theory:Single Stage Systems. Kluwer Academic Publishers, 1994
5ݡEmmons H. One machine scheduling to minimize men a flow time with minimized number tardy. Naval Res. Logist.Quart., 1975,22(3):585592
6ݡSmith W E. Various optimizers for single stage production. Naval Res.Logist.Quart., 1956,3(1):5966
ոڡ1998-07-21
޸ڡ1999-01-08
