带时间延迟的极小化总完工时间的单机排序问题

《带时间延迟的极小化总完工时间的单机排序问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、浙江理工大学学报!自然科学版"#第!"卷#第"期##$"%年"月&'()*+,'-./012+*34526705/8*290):2;',?!"#='?"#&+*?#$"%文章编号!!"#$6$%&!"'(!)#(!6((%$6(&带时间延迟的极小化总完工时间的单机排序问题胡觉亮$王焕男$蒋义伟!浙江理工大学理学院#杭州!"$$"E"!!摘!要!研究工件带有两道工序的单台机排序问题%在该问题中#工件的第一道工序先于第二道工序加工#并且第二道工序的开工时间与第一道工序的完工时间至少间隔一定的延迟时间#目标是极小化所有工件的总完工时间%文章考

2、虑所有工件相同且两道工序的加工时间均为单位时间的情形%通过引入O6连续加工的概念和分析最优解的性质#根据延迟时间的大小#分别设计了两个算法并证明了算法所得的排序为最优排序%关键词!单台机&时间延迟&总完工时间&算法设计与分析&最优排序中图分类号!V#!!!!!文献标志码!K'%(法%K3009等给出了问题"p0^+5;S$KRRFNRF"(!引!言[JH+^的一个C*%-近似算法$并证明界不可改进$同本文主要研究带延迟时间的单机排序问题%每时给出了问题T#p0^+5;S$K的一RRFNRF"[JH+^'B(个工件0R有两道工序KR和NR$第一道工序先于第个!*#-近似算法$

3、b(等证明了上述两个问题是强'A('C(二道工序加工$第一道工序的完工时间GK与第二道&B-难的%J('等和L,+:5'5W等研究了问题T#R工序的开工时间ENR之间至少存在SR个单位时间延p0^+5;SR[&JR的计算复杂性并给出相应的启发式迟$也就是说第二道工序至少等待S个单位时间才R算法%能开工%此类问题在一些产品制造工艺流程&布匹'E(关于至少延迟的排序问题$X0)*等证明了以印染和服装订单的生产中有重要的应用背景%对于极小化最大完工时间为目标的单台机排序在解不限带有延迟的排序问题$主要分为两类$一类是工件于排列排序的情况下是=a6难的%而对于两台流水0R前后两道工

4、序的延迟时间恰好为SR$本文称之为'F(作业排序问题T#$S$,,qKH25'给出了该R$J"H+^#精确延迟排序)另一类是两道工序间的延迟时间至问题的一个#-近似算法$并提出了一个禁忌搜索算少为S$称之为至少延迟排序%R法%若两道工序的加工时间相同时$,,qKH25''"(关于精确延迟的排序问题$V)H+*等证明了'"$(等证明了问题T#$S是强=a6难的$R$KRRNR$JH+^单台机的一些特殊情况是多项式可解的$并证明即'""('"#(&'/*:'*和N2;;0*证明该问题存在最优排列便所有工序的加工时间相同$该问题还是强=a6难排序"_0)H(;+;2'*:

5、5/0](,0#%若两道工序加工时'#(的%O0(*3等利用贪婪算法研究延迟非增的情形$'"!(间相同且延迟时间S.$$S0时$b(证明了问题R/给出了问题T#[SHR$KRFK$NRFN$K(N[&JR的W#$SR/.$$S0$KRRNR$JH+^是强=a6难的%进一步$最优排序$并对问题T#[SH$K$N$K"N['B(RRFKRFN即使两道工序的加工时间均为单位时间$b(证明'!(分别研了问题T#$S$K也是强=a-难的%&JR给出了一个#-近似算法%K3009等RRRNRR"$JH+^对上述研究综述进行汇总后$如表"所示%究了单台机和两台流水作业机器问题的一些近似算

6、收稿日期!#$"#@"$@!"基金项目!国家自然科学基金"""$$"#%#$""$C"##$#作者简介!胡觉亮""FBE@#$男$浙江杭州人$教授$大学本科$主要从事组合优化与数学建模的研究E%!!!!!!!!浙!江!理!工!大!学!学!报"自然科学版##$"%年!第!"卷表!!带有至少"精确#延迟时间的单机和两台机流水作业排序单台机两台机流水作业"$SR$JH+^'E(T#$SR$JH+^'F(至少T#$SR$@/$RR"$JH+^'B(延T#$SR$KRRNR$JH+^'"$(迟排T#$SRRS$JH+^'""('"#(序T#$SR/.$$S0$KRRNR$JH+^'"

7、!(T#[SHR$KRFK$NRFN$K(N[&JR'#(T#[SHR$KRFK$NRFN$K"N[&JR'#(精确"$0^+5;SR$KRRNRRSR$JH+^'""(延T#$0^+5;SR$&JR'A('C("$0^+5;SR$KRRNR$JH+^'"!('"A(迟排"$0^+5;SR$JH+^'F('"$(T#$0^+5;SR$JH+^'!(序"$0^+5;SR$KR*NR$JH+^'"!(T#$0^+5;SR$KR*NR$JH+^'!("$0^+5;SR$KR(NR$JH+^'"!(T#$0^+5;SR$K