论文研究 关于带有传输时间的F.pdf

论文研究-关于带有传输时间的F.pdf,  考虑传输时间的同顺序排序问题是在机器人设计及柔性制造系统中有着广泛应用的一类排序问题。 第9期关于带有传输时间的2| pern Cmax排序问题的一个新算法2关于带有传输时间的F2|Perm|Cmax的新算法步骤1令a2=max{a;t+t};步骤2令U={i{t+t>max{b}对vk∈R成立类似于(2)式易于算得D((R/{l})=∑∈R/{iy∈R/{,c}∑-∑b+b+b。-(t+∈R对于部分排序J-1(N/{4秒})=(-1(R/{}),-(N)应用引理3可得D(-(N/{})=D(J-1(NR)+max{D(J-1(/{})-IA(-1(N/H)20}(4)再注意到D(J-1(N/{)≥b,对排序-1()-(1(N/{}),)易于算得(参见图4)M'(s-1(i)=∑b;+D(J-(N{i})+aj∈N7/{}系统工程理论与实践195年9月b∑jEN/()D(J-4(N/{})A图4s-1(i)=(J-4(N/{1}),)的 Gantt图将(3)式代入(4)式,再将结果代入(5)式并整理后可得M(1()=∑b+D(J1(M/B)+max{+a,a;-b}∈N其中∑∑b-A(J1(NF)+b-(为一常量.记T()=max{T+a;a2-b;},则M(s1()=∑b+D-(NB)+r(),t∈Q∈N其中∑bD(J-1(N/R)N均与2无关,故若M(s-1(k)M(s()=min{M(6()∈再由(1)式知M(s(k))Ms(i)∈Q最后,综合上述讨论可知,从排序s1、s(r)和s(k)中挑选出的最优排序即为所讨论问题的最优解4计算实例为使读者更清楚地了解新算法各步骤的含义及与Panakan算法的区别,我们用新算法对anwalkar提供的一个实例(进行求解第9期关于带有传输时间的E2 perm Cmax排序问题的一个新算法设有8个工件N={1,2,3,4,5,6,78}要在机器A和B上按先A后B的路线加工传输机构从A运动到B以及从B运动到A所花费的时间分别为t=15和t=12.各工件的加工时间a;、b以及相应的al2如表1所示步骤1结果己列于表1中步骤2U={6,7}:V={1,2,3,4,5,8};表1步骤3U={7,6},V={3,8,1,5,2,4)};工件b步骤4(7,6,3,8,1,5,2,4),4832354步骤5P=d,M(82)=∞步骤6Q={2,5},J(Q)=15,2}1-2345621271943484846J(R)=(5,2,4),J-1(N/f)=(1,8,3,6,7)22|2721I(-(N/R)=32,D(J-1(N/R)=33474748T=18,T(2)=39,T(5)=40,T(2)61min{T(2,T(5)},83=(2,7,6,3,8,1,5,4),8424236M(83)=348;(参见图5)步骤7M(3)=min{354,∞,348}=348,83=(27,6,38,1,5,4)是最优排序匚①)(8)(6)(6)⑦32IA(J-I(N/R)D(J-2(N/)(1)(8)(3)(6(7图5(J-(N/R)=(1,8,3,6,7)的 Gantt图5结束语在本文中,我们对带有传输时间的两机器同顺序问题提出并证明了一个新算法.与 Panwalkar的算法比较,由于新算法至多只需计算三个排序的总加工时间(特别是当讠∈P时,仅需比较a;的人小即可简单地决定s()的优劣),从而使算法的复杂性降至O( n log TE),可见新算法是对Panwalkat算法的一个显著的改进最后:作者对审稿人为本文所提出的宝贵建议谨致谢意参考文獻S.S. Panwalkar. Scheduling of a two-machine-fowshop with travel time between machines.JOp1.SoC.1991,12(7):6096132 K.S. Stecke and J.J. Solberg. Loading and control policies for a fexible manufacturingsystem. IntJ. Prod Res. 1981(19 ):481-4903 W Szwarc. Optimal two machine orderings in the 3 x n flowshop problem. Ops. Res1977(25):70-774越民义,韩继业.n个T件在m台机床:的加顺序问题I.中国科学,1975(5)462-470.