论文研究-三台机并行工件排序问题的改进的下界.pdf

所需积分/C币:10 2019-09-11 01:20:14 471KB .PDF
32
收藏 收藏
举报

与经典的排序问题不同的是,并行工件排序指的是在加工某些工件时,需要多个机器同时并行工作。竞争比是评价在线算法好坏的一个重要指标,而竞争比的下界则是算法设计的一个重要参考。利用反证法,通过构造一个特殊的反例,分析了由此产生的全部9种可能的情形,建立了它们对应的9种线性规划模型,借助计算软件证明了前8种情形是不可能的,然后详细分析了第9种情形也是不可能的,从而给出了三台机并行工件排序问题的竞争比的一个改进的下界2.07。这个结果优于已知的最好的下界1.999。
28 015,51(10) Computer Engineering and Applications计算机工程与应用 面8种可以利用线性规划来处理。 表明ρ比较接近所需要的下界。另外,利用类似与下 首先,由n0,n,p,p2的构造,有 面第9个分类的分析方法,同样可以得到R4>p,>尸。 P 2)为了简单起见,仅重点针对第9个分类进行分析(这也 p 3r+3 (3)是因为第9个分类才是得出207这个下界的关键分 P1=s+Po+VI 4)类),对于其他8个分类的分析,只需要调整相关不等式 P2=x1+P1+y2 (5)即可,在这里利用计算软件的结果只是为了叙述及验证 r 的方便。 由R(n0)≤p,即一≤,有 下面分析第9个分类,即q1=t=s-r-1且 ≤P+ (6)情形。先给出几个简单的结论 因为R(p2)<P,则有x1<(-2)1+(p-1q1=(p-2)p1 由R(p0)≤p,即 p,有 Po (p-1,所以 ≤(+-1)p 91+y p-2)p (12) 由R)≤D,即“+≤p,有 由R(pb)<p,即 +p0 p,所以 Pots s+y1≤(p-1p0+(p-191 (8) s<(P-1)p0=3(p-1)(+1) 由R(p)≤P,,即 2(s+6+y)+x1-q1 由于 (S+p+y1)+q1 2p+3 (14) x1≤(P+-2)(s+P0+y1)+(1-1q (9) P 由RG,)<p.即12s+Pn+y)+(x+y)+(+9)D,有 且 (s+p-y1)+(q1+q2) 15 x1+y2≤(p-2)s+p0+y)+(-1)(q1+g2)(10) 以及 由R(P2)≤p,,即 3(s+P0+y1)+2(x1-y2)+x2+(g1+q2) (+p0+y)+(x1+y,)+(q1+q2) 6p-p6p-1 16) 有 有 x2≤(P+-3(+P0+y)+(p+-2)(x1+y2)+ (+D)n1+Pt(+1)(3r+s+y1+3)+/(-r-1) )(q1+q2) (p-1)P1+pt(p-1)(3r+s+y1+3)+p(s-r-1) 用表1表示各种情况下的约東条件 2p+3+1)+(2p+Ds+(p+" 表1根据r,s,t,q1的关系分成9种情况 (r+1)+(2 分类对r,,1,q1的约束对q2的约束 (62-p)(P+1)+(+1)y0310 S≤P 4:-8 (62-7(+1)+(p-1)y1 如图1所示) 由R(q),即21+(x+y2)+(a、+)∠,所以 P1+(q1+42) 2)P1+(p-1q1+g2)≤ (如图2所示) 2r+1< -2)p1+(-1)(0-2)P1-p (p2-2)p1+(p2-p)t (如图3所示) 42- 另外 相同约束 条件(2)~(11) 4p-4p 2p-3p+1 (19) 显然,每个子分类相关的所有约束构成了一个线性 22-p-1 p-p-12--30-3 规划。用计算软件(用的是 LINGO11)可以很容易知道 及 前8个分类的相关线性规划是无解的。这表明在前8分 12p-20p2+7p12p2-20p+72p--3p+1 (20) 类中,RA≥p>P。事实上,条件(2)-(11)米至于R≤p 7 6 的假设,如果适当放大p,它们的可行解是存在的。这 因此 余国松,徐刚:三台机并行工件排序间题的改进的下界 2015,51(10) 29 3P1+2(x1+y2)+x2+(q1+q2) R(P2) P1+(x1+y2)+(1+42) 4 Hurink JL, Paulus J J Online scheduling of parallel jobs on two machines is 2-compctitivc[J].Opcrations Rcscarch 3P1+2(x1+y2)+(q1+92)(2 Letters,2008,36(1):51-56 P1+(x1+y2)+(q1+q2) 5] Hurink J L, Paulus J J Improvcd online algorithms for p+1)P1+p(+2(x1+y2)(718 parallel job scheduling and strip packing [J]. Theoretical (p-1P1+pt+(x1+y2) omputer Science, 2011, 412: 583-593 (22-30+1)p1+(2p2-p [6 Kern W. Paulus J J. A note on the lower bound for online (p2p-1)1+p2 strip packing[R]. Memorandum 1893, 2009, 2 [(2p2-3p+1)(3r+s+),+3)+(2p2-PC-r+s-1)] [7 Ye d, Zhang G A note on online strip packing! JJ. Journal [(p2-p-1)(3+s+y1+3)+p(-r+s-1)]= of Combinatorial Optimization, 2009, 17(4): 417-423 [8 Harren R, Kern W Improved lower bound for online strip 「(4p-80+3)(r+1)+(4p2-4p+1)s+ packing]Theory Comput Syst, 2013 (2p2-3+1)(2o2-3-3r+1)+ [9 Chen B, Vestjens A P A Scheduling on identical machines (2p2-p-1)s+(p-p-1y1]≥ how good is LPT in an on-line setting[J]. Operations [(4p2-8p+3)(+1)+(4p2-4p+1)3(p-1)(+1)+ Research Letters, 1997.21:165-169 [10 Naroska E, Schwiegelshohn U On an on-line scheduling p+1)y14(C2p2-3P-3)(+1)+(2 problem for parallel Jobs J] Information Processing Let 3(0-1)(+1)+(2-p-1y1> ters,2002,81:297-304 (12-20+7)(+1)+(2p-3p+1)y1(20 [11] Shmoys D, Wein J, williamson D Scheduling parallel (63-7p2-3p)(r+1)+(p2-p-1)y machines on-line[J siAM Journal on Computing, 1995 12p-20p+7 24:1313-1331 60-7p-3 [12 Dutton R, Mao w, Chen J, et al. Parallel job scheduling 因此对于第9个分类,得到了R4>P。综合所有的 with overhcad: a benchmark study [C]!/Proceedings of the 分类,无论算法A如何对这六个工件排序,总有R1≥p, IEEE International Conference on Networks, Architecture, 这与对算法A的假设是相矛盾的。证毕 nd Storagc( NAS), 2008: 326-333 [13 Dutton R, Mao wOnline scheduling of malleable parallel jobs[c]iProcccdings of the ISATED International Con 4结论 ference on Parallel and Distributed Computing and Sys 为了得到P3 online-list,mCn的在线算法的一个 tcms,2007:1-6 较好的下界,构造了一种反例,并且用线性规划结合其[14 Koulamas c, Kyparisis G J.An improved delayed-siat 他方法分析了可能出现的9种情形,说明了19+N55+ LPT algorithm for a partition problem on two identical 3552.07是这个问题的下界,为设计这类问题的在线 parallel machines[J]. European Journal of Operational Research,2008,187:660-666 算法提供了参考,也为m等于其他值时的下界估计提 [15] Koulamas C, Kyparisis G J.A modified LPt algorith 供了一种新思路 for the two uniform parallel machine makespan minimi zation problem [J]. European Journal of Operational Research 参考文献 2009,196:61-68 ['] Johannes B Scheduling paralles jobs to minimize the makcs- [16 Li R H. Huang H C Improved algorithm for a generalized pan[J] Journal of Scheduling, 2006,9(5): 433-452 on-line scheduling problem on identical machines[J] [2]Pruhs K, Sgall J, Torng E. Handbook of scheduling algorithms European Journal of Operational Research, 2007.176 models, and performance anaylis[M/OL]. Leung Y T [S1.: 643-652 Chapman hall/CRC, 2004 [17] Sidhoum s K, Solis Y R, Sourd F Lower bounds for the [3 Chan W T, Chin F Y L, Ye D,et al. On-line scheduling earliness-tardinessscheduling problem on parallel machines of parallel jobs on two machines[J]Journal of Discrete with distinct due dates[J]. European Journal of Operational Algorithms,2008,6(1):3-10 Research,2008,189:1305-1316

...展开详情
试读 4P 论文研究-三台机并行工件排序问题的改进的下界.pdf
立即下载 低至0.43元/次 身份认证VIP会员低至7折
一个资源只可评论一次,评论内容不能少于5个字
您会向同学/朋友/同事推荐我们的CSDN下载吗?
谢谢参与!您的真实评价是我们改进的动力~
关注 私信
上传资源赚钱or赚积分
最新推荐
论文研究-三台机并行工件排序问题的改进的下界.pdf 10积分/C币 立即下载
1/4
论文研究-三台机并行工件排序问题的改进的下界.pdf第1页

试读结束, 可继续读1页

10积分/C币 立即下载