包装箱生产瓶颈工序的优化调度研究

上海交通大学硕士学位论文包装箱生产瓶颈工序的优化调度研究姓名：王康园申请学位级别：硕士专业：工业工程指导教师：范秀敏;陈坚20031001Job-ShopNPResearchonOptimalSchedulingofBottleneckProcessesforPackagingProductionABSTRACTForsmallbatch,multi-varietyproduction,becauseeachjobhasquitedifferentbatchquantity,typeandspecificationthenevenonsameoperation,theworktimeisquitedifferent.Normallyworktimeforecasting,isahardwork,andalsoverydifficulttosuretheveracity.Thispaperviaregressingsampledataofactualworktimewithjobparameters,togetworktimeforecastfunction.Becauseprocessnormallyisastableoperation,sowecaninputparameterstoforecastworktimebythisfunctionforanewjob.Mostofdifferentprocessispossibletogetaregressingfunctionundermathmaticstatistictheory.Thefunctionwegotbythismethodnormallyisquitesimpleandgoodveracity,alsocanestimatethetoleranceofreliability.Job-Shopsequencingproblemisanonlinearhardproblemduetoitscomputationalcomplexity.Howeverbottleneckprocess,whichrunsinfulltime,isfixedandobvious.Jobsequencingatbottleneckprocesshassignificanteffectondeliverytimesafetyforsmallbatch,multi-varietyandfast-delivery-requiredcompany.Thispaperdesignedameasurabletargetfunctionofdeliveysafetyforonegroupjobsequencingstrategy.Andsoontoconsiderabottleneckjob-sequencingproblemforamodelwithmultimachines.Tosolvethisproblem,firstlyneedfindouttherushhoursandseparatedintoseveralstages,thensequencingthejobsforeachstagebyenumeratingmethod,andfinallyobtainingthemostsafetydeliverysequencingsolution.Thismethodisquitesimple,whileefficient.Keywords:worktime,jobsequencing,deliverysafety,job-sh[e-mail]342.1150010~3010~5008430~50SP5~7SP1.2.nSSS=0PS=1LmmWmm5Hmmtˆ(n,S,L,W,H)),,,,(ˆHWLSnft=ff1.2.f3.4.f5.6.7.f8.9.f1.t2.t3.t4.t5.t6.62.2n{t1,X1;t2,X2;…;tn,Xn}tiiXiiXi={x1i,x2i,x3i,…}X={x1,x2,x3,…}t{x1,x2,x3,…}txjFtFt21212)(tntttLniiniitt-=-=∑∑==ttLxttU∑=-=niiittU12)ˆ(UxxxxtLLU2=∑∑==-=--=niiiniiixttxntxttxxL11))((∑∑==-=-=niiniixxxnxxxL12212)(2-=nfS1=Ufxxkp1,p2,…,pkm1xi=p1i=1~n111mtxnii∑=′=⎩⎨⎧≠==′11,0,pxpxttiiiim2xi=p2i=1~n212mtxnii∑=′=⎩⎨⎧≠==′22,0,pxpxttiiii……7mkxi=pki=1~nkniikmtx∑=′=1⎩⎨⎧≠==′kikiiipxpxtt,0,212tnxmUkiii-=∑=⋅knfS-=1-=kfUtxS∑=-=niiittS12)ˆ(SULtt+=USxtUttSSUfULfUfSfUF)(//-⋅==Fa=0.050.01F)2,1(-nFaFaFaFF≥xatF11502-2-3nS=1,2,3,4L,Wtn,L,W2-2-1LxxLxtSU1n2L3WFxttL=4610202-2-18S2-2-2F27857S=68072F(0.025,1,148)=5.13;F(0.025,2,148)=3.78;F(0.025,3,148)=3.21;F(0.025,4,148)=2.8792-2-3t(min)nL(mm)W(mm)St(min)nL(mm)W(mm)St(min)nL(mm)W(mm)SLW102.3n{t1,x1;t2,x2;…;tn,xn}xt1xbxat+=ˆab2xkp1,p2,…,pkttˆ1S0=∂∂aS0=∂∂bS0)(2)1)((21=---=---=∂∂∑=niiixbatnbxataS0)(2)()(21121=-⋅⋅+=---=∂∂∑∑∑===niiiniiiniiixtxanxbxbxatbSxbta-=∑∑===+⋅⋅ninitixixibxan112)112(∑∑===+-niiiniixtxbxxbtn∑∑=----=niiniiixxttxxb121)())((xxxtLLb=xbta-=2jniijmtx∑=′=1⎩⎨⎧≠==′jijiiipxpxtt,0,=j1,2,3,…,k11⎪⎪⎩⎪⎪⎨⎧====kkpxxpxxpxxt,...,,ˆ2211∏=-⎥⎦⎤-++-+⎢⎣⎡-=kiikkpxpxbpxbpxbt12211)()(...)()(ˆ))...()(()(211kkiipxpxpxpx---=-∏=ikiiiiiiiixppppppppppb))...()()...()((1121-----=+-i=1,2,…,k1tnntttL=461020ntL=1228493nnL=3786899t=42.72n=99.3b=ntL/nnL=1228493/3786899=0.3244nbta-==42.72-0.3244*99.3=10.5nt3244.05.10ˆ+=2-3-12-3-2122.41tkx1,x2,…,xkkkxbxbxbxbat+++++=...332211)a,b1,b2,…,bk⎪⎪⎩⎪⎪⎨⎧=+++=+++=+++02211202222121101212111...............kkkkkkkkkkLbLbLbLLbLbLbLLbLbLbL∑=--=nqjqjiqiijxxxxL1))((i,j=1,2,…,k∑=--=nqqiqiittxxL10))((i=1,2,…,kkkkkkkkkLLLLLLLLLLL212222111211)(......==×),...,,,(03020100′=kLLLLL),...,,,(321′=kbbbbb2-4-20LbL=⋅01LLb⋅=-bxxxxtak⋅-=),...,,,(3212tkx1,x2,…,xkx1k1x2k2…xkkk2-4-12-4-32-4-213⎪⎪⎩⎪⎪⎨⎧===++⎪⎪⎩⎪⎪⎨⎧===+⎪⎪⎩⎪⎪⎨⎧===+=kkkkkkkkkkkkkkpxbpxbpxbpxbpxbpxbpxbpxbpxbat,......,,......,......,,,......,,ˆ2211222211112211222222111111abij1pijjibat+=ˆ2-3-1jjiibax+=i=1,2,…,k;j=1,2,…,kiata=txbjjii-=pijt22-3-2xiki1)1(210...ˆ2--++++=kiikiiixbxbxbbtix′=2ixix′′=3ixix′′′=4ix…2-4-4ixix′ix′′ix′′′…ikiiiixbxbxbxbbt''...ˆ...)1(3210-++′′+′++=2-4-22-4-3b0,b1,…,b(ki-1)ki-1ixix′ix′′ix′′′…ix1S2-2-22-3-1t4321,68.4,61.39,92.10,78.1472.42ˆ====⎪⎪⎩⎪⎪⎨⎧---+=xxxxt2-3-23259.239.1646.3253.2126/)3)(2)(1(68.42/)4)(2)(1(61.392/)4)(3)(1(92.106/)4)(3)(2(78.1472.42ˆxxxxxxxxxxxxxxxt-+-=---------------+=2-4-414x1,x2,x3S2-4-3x1=x,x2=x2,x3=x3332211ˆxbxbxbat+++=a,b1,b2,b32-2-3L11=173,L12=834,L13=3368,L22=4170,L23=17324,L33=73602L10=1783,L20=7261,L30=2325223.21=x,14.62=x,27.193=x,27.42=t)59.23,9.164,6.325)(27.19,14.6,23.2(27.42),,(321′---=-=bxxxta=212.27bxat+=ˆ=212.27-325.6x1+164.9x2-23.59x3=212.27-325.6x+164.9x2-23.59x3kk-1L=L-1===-01LLb=152.5nnnxbxbxbbt++++=...ˆ2210nxt2-5-1nxtn3~52-5-12-4-1WLbat⋅⋅+=ˆx’akaakxxxx⋅⋅⋅=′...2121tkkxbxbxbaxxft′++′+′+==...,...),(ˆ221121x’ix1,x2,…S2-5-1161.2.2-2-1FtX3.tX4.5.Fttˆ-6.2-4-37.2-6-16t8.4F9.S71n,S,L,W4871)n,n2,…,n7;2)S,S2,…,S10;3)L,L2,…,L7;4)W,W2,…,W7;5)LW,L2W,L3W,LW2,LW3,L2W2;6)S,S2,S3345607)n,n2,n32)3)4)5)6)2708)n4,n5,n6,n72)3)4)5)1202-2-1Ft10F1)nL1142.122)nLW995.903)n885.814)nLWS8245)nLS749.556)n2LW2558.227)nW535.398)nLS2519.329)nLWS2519.2310)n2LW501.5817n,nL,nW,nLW,nLS2-2-3L0=Xaverage=taverage=42.72Lb=L-1L0=a=taverage-Xaverageb=7.34nLSnLWnWnLnt0531.00613.00817.0255.01346.034.7ˆ-++++=2-5-1U=440326S=20694F=3149L-1=L=192-5-1t