平行机在线排序问题.ppt

平行机在线排序问题平行机在线排序问题3/12/20231平行机在线排序问题平行机在线排序问题n在线排序问题n几种不同的在线模型nonline over list的最新结果n半在线排序问题n半在线问题概述nP2|Cmax 半在线问题的若干结果n其他半在线模型的主要结果n“非典型”在线排序问题3/12/20232平行机在线排序问题nm台平行机，n个工件，工件加工不可中断n同型机（identical machine）：每台机器完全一样n同类机（uniform machine）：每台机器的速度不同3/12/20233n把需要完成的任务称为工件工件（job）n把完成任务需要的资源称为机器机器平行机在线排序问题3/12/20234平行机在线排序问题3/12/20235平行机在线排序问题n定义在线算法 A 求极小化问题的竞争比（competitive ratio）为3/12/20236平行机在线排序问题3/12/20237第一章：在线排序n在线问题的一般假定：n工件一个个地到达，工件信息随着加工过程逐个依次释放n工件一旦被安排就不能改变n根据实际背景要求，下面给出常见的几种在线模型3/12/20238Online over listOnline over list：1.工件在零时刻一个个地到达，工件Ji到达后其信息（加工时间）完全已知，且被安排在某台机器上自某时刻起开始加工，其后的工件信息未知。2.工件一旦被安排就不能改变3/12/20239Online over listLS算法（List Scheduling)：LSs算法3/12/202310Online over listPnPkMi实例实例I Ck PkMi实例实例I Ck 3/12/202311Online over listP11l1l2MiliSnCn3/12/202312Online over list111111111111mm-1111111111111mm3/12/202313Online over list11111123/12/202314Online over list1 1 11 1111111133311133311133311133361 1 133363/12/202315参考文献nOnline surveynK.Pruhs,E.Torng,J.Sgall,Online scheduling,In Handbook of Scheduling:Algorithms,Models,and Performance Analysis,ed.Joseph Y.-T.Leung,chapter 15,pages 15-1-15-41,CRC Press,2004.nJ.Sgall,On-line scheduling,In Online Algorithms:The State of the Art,ed.A.Fiat and G.J.Woeginger,Lecture Notes in Comput.Sci.1442,pages 196-231,Springer,1998.3/12/202316参考文献nOnline over listnGraham,R.L.:Bounds for certain multiprocessing anomalies.The Bell System Technical Journal,45,1563-1581,1966.nFaigle,U.,Kern,W.,Turan,G.:On the performance of online algorithms for partition problems.Acta Cybernetica,9,107-119,1989.3/12/202317Online over timeOnline over time：与online over list的区别是每个工件有其到达时间（release time），工件只有在其到达时间之后才能开始加工。3/12/202318Online over time的基本假设：工件有到达时间，在到达时间之后才能开始加工在某工件的到达时间之际，该工件的信息（加工时间）完全已知，且即被安排在某台机器上的某时刻起开始加工在某时刻t，所有到达时间大于t的工件的信息未知工件一旦被安排加工，其加工方式不可更改Online over time3/12/202319n尽管online over time被称为在线，工件信息未知的原因并不是前个工件未安排，而是该工件的到达时间未来临。若一批工件的到达时间相同，则在此时刻它们的所有信息已知，具有离线排序的特征。考虑所有工件到达时间都为0的特殊情况，此时online over time退化为离线模型而非online over list模型online over time3/12/202320online over time 用求解离线问题的LPT算法（Longest Processing Time first）求解online over time问题算法online LPT：若在某时刻，有一机器可加工工件（空闲），将已到达而未加工的工件中加工时间最长的工件安排给该机器加工。若此时没有这样的工件，则机器空闲直至下一个工件到达的时刻。3/12/202321online over timeTh1.3 算法online LPT求解Pm|online over time|Cmax的竞争比为3/2，且界为紧的。Th1.4 Pm|online over time|Cmax的下界至少为：Noga和Seiden给出了两台机的最好算法sleepy，竞争比恰与定理中m=2时一样，当m3时已知的下界小于m=2时的下界，这在平行机排 序中较为罕见3/12/202322参考文献nOnline over timenChen,B.,Vestjens,A.P.A.:Scheduling on identical machines:How good is LPT in an on-line setting?Operations Research Letters,21,165169,1997.nJohn Noga,Steven S.Seiden,An optimal online algorithm for scheduling two machines with release times.Theoretical Computer Science 268,133143,2001.3/12/202323Online with arbitrary release timesOnline with arbitrary release times工件有到达时间，在到达时间之后才能开始加工工件信息（到达时间、加工时间）在零时刻逐个释放。某工件信息已知后，即被安排在某台机器上自某时刻开始加工某一工件未安排加工前，其后工件的信息未知工件一旦被安排加工，其加工方式不可更改3/12/202324Online with arbitrary release times 当所有工件的到达时间为0时，该模型退化为online over list，所以必为在线的问题，可通过修改LS而不是LPT算法以求解称Mi上空闲时段（b，e）可加工Jj，若maxb,rj+pj e 3/12/202325Online with arbitrary release times3/12/202326MiM1ebeUiU1Online with arbitrary release times3/12/202327Online with arbitrary release times3/12/2023281 111 111 11mm m-1 mOnline with arbitrary release times3/12/202329算法A的解 最优解Online with arbitrary release times3/12/202330 注意到Th1.5、Th1.6，当m=1即单台机时仍成立。此时LS算法的竞争比为2，且为最好算法。对一般情形，Li和Huang先后给出了竞争比为2.93920和2.78436的改进算法Online with arbitrary release times3/12/202331参考文献nOnline with arbitrary release timesnLi,R.,Huang,H.C.,On-line scheduling for jobs with arbitrary release times.Computing 73,7997,2004.nLi,R.,Huang,H.C.,Improved algorithm for a generalized on-line scheduling problem on identical machines,European Journal of Operational Research,176,643652,2007.3/12/202332Non-clairvoyantnonclairvoyant 在之前的模型中，排序者在安排工件时该工件的加工时间是已知的，未知的信息是后续工件的加工时间或到达时间。而在nonclairvoyant模型中，排序者在安排工件时还不知道其加工时间。只有当该工件加工完毕后，其加工时间才为排序者所知。3/12/202333Non-clairvoyant Nonclairvoyant的基本假设：(1)工件在零时刻到达并可开始加工；工件的加工时间直至加工完毕才为已知；排序者可根据当前机器和工件情况安排未加工工件。（2）工件一旦被安排加工，其加工方式不可改变。3/12/202334Non-clairvoyantTh1.7 Pm|nonclairvoyant|Cmax的下界为21/mProof:设有m(m-1)+1个工件，设凡在时刻m-2及之前开始加工的工件加工时间为1，则在时刻m-1前至多有m(m-1)个工件加工完毕。在时刻m-1后至少有一个工件开始加工，设其中一个加工时间为m，其余工件加工时间为1，则 3/12/202335OrdinalOrdinal模型对nonclairvoyant的假设作适当调整，得到ordinal模型，其基本假设为：(1)工件在零时刻到达并可开始加工；工件的加工时间未知，但该工件的加工时间再由所有工件加工时间组成的有序集合中的顺序位置一致；排序者需在零时刻安排所有工件。(2)工件一旦被安排，其加工方式不可更改。3/12/202336Ordinal3/12/202337OrdinalTh1.8 算法ordinal求解P2|ordinal|Cmax的竞争比为4/33/12/202338OrdinalTh1.9 P2|ordinal|Cmax的下界为4/33/12/202339参考文献nNon-clairvoyantnDavid B.Shmoys,Joel Wein,David P.Williamson,Scheduling Parallel Machines On-line,SIAM Journal on Computing,24,1313 1331,1995.nOrdinalnLiu,W.P.,Sidney,J.B.,van Vliet,A.:Ordinal algorithms for parallel machine scheduling.Operations Research Letters,18,223-232,1996.3/12/202340参考文献nOrdinalnHe Yong，Tan Zhiyi,Ordinal on-line scheduling for maximizing the minimum machine completion time.Journal of Combinatorial Optimization,6,199-206，2002.nTan Zhiyi，He Yong,Semi online scheduling with ordinal data on two uniform machines.Operations Research Letters,28,221-231,2001nTan Zhiyi，He Yong，Epstein Leah,Optimal on-line algorithms for the uniform machine scheduling problem with ordinal data.Information and Computation,196,57-70,2005.3/12/202341Online over list 的新进展Pm|Cmax已知LSs是m=2，3时最好的算法，但对一般的m值，尚无最好的算法。考虑Pm|Cmax的下界。Th1.2给出m=2，3时的下界，其实例的构造有以下特点：(1)工件按层（layer）到达，除最后一个工件外，每层中工件的加工时间相同，数目与机器数相同。(2)各层工件加工时间递增。最后一个工件的加工时间为最后一层工件加工时间的两倍。3/12/202342下界bi算法解算法解a1a1a1a2a2a2aiaiai2ai最优解最优解2aiaiaiaiai3/12/202343下界3/12/202344下界11/21/21/21/21M为偶数为偶数11/21/21/21/21M为奇数为奇数1/21/211/21/23/12/202345下界BkBkBkBkAkBk-1Ak-1BoAkAkAkBk-1Bk-1Bk-1Ak-1Ak-1Ak-1+2AkBoBoBoAoAoAoAo+2A12Ao3/12/202346下界3/12/202347下界111133331616161644444450883/12/202348下界3/12/202349下界3/12/202350下界3/12/202351下界3/12/202352下界3/12/202353下界3/12/202354下界1111111111111111333311113333111133331111333316161616111133331616161611113333161616161111333316161616444444111133331616161644444416161616444444111133333/12/202355下界11113333161616164444445011113333161616164444445050161616443443164431111388444444551616 33 1 11 111331616111133331616161644444450883/12/202356算法3/12/202357算法0.278m Mk0.639m Mi3/12/202358算法3/12/202359算法3/12/202360新型算法的必要性3/12/202361参考文献nOnline over list 的新进展nJohn F.Rudin,III,R.Chandrasekaran,Improved Bounds for the Online Scheduling Problem.SIAM Journal on Computing,32,717 735,2003nR udolf Fleischer,Michaela Wahl,On-line scheduling revisited,Journal of scheduling,343-353,2000.nSusanne Albers,On randomized online scheduling,Proceedings of the thiry-fourth annual ACM symposium on Theory of computing,134 143,2002.3/12/202362Online over list的其他结果3.Online over list的其他结果Th1.13 算法LSs求解Pm|Cmin的竞争比为mL1-Pj1Pj1L2-Pj2Pj2Ln-1-Pjm-1Pjm-1Lm3/12/202363Online over list的其他结果3/12/202364Online over list的其他结果3/12/202365Online over list的其他结果3/12/202366a1 b1 a2 b2lengthP(s)rA(s)gapOnline over list的其他结果3/12/202367Online over list的其他结果3/12/202368Q2|Cmax Q2|Cmin Online over list的其他结果3/12/202369参考文献nOnline over list 的其他结果nWoeginger,G.:A polynomial time approximation scheme for maximizing the minimum machine completion time.Operations Research Letters,20,149-154,1997.nEpstein,L.,Noga,J.,Seiden,S.,Sgall,J.,Woeginger,G,:Randomized on-line scheduling on two uniform machines.Journal of Scheduling,4,71-92,2001.nEpstein,L.,Tight bounds for online bandwidth allocation on two links.Discrete Applied Mathematics,148,181188,2005.3/12/2023701.半在线排序概说半在线排序问题分为以下两类(1)已知未来工件的部分信息或工件集的一些整体信息(2)额外的工件安排方式或设备常见的半在线问题有：半在线排序3/12/202371半在线排序3/12/202372半在线排序2.P2|Cmax半在线问题（1）P2|sum|Cmax和P2|opt|CmaxTh2.1 P2|sum|Cmax的下界为4/3Proof：设T=6已知。11111111122311111223最优解=3算法解=43/12/202373半在线排序剩余工件3/12/202374半在线排序 由引理，当机器负载在(1-a/2)T,aT/2之间，总能安排剩余工件使欲证之竞争比成立。考虑引理条件不满足的情况，此时存在工件pt，在它到达前某机器的负载小于(1-a/2)T，而若该机器加工此工件，其新负载将大于aT/2，因此pt的加工时间为(a-1)T 称pt为关键工件。把引理2.2中的条件称为阀值条件甲 它有一个参数a。一旦阀值条件甲得到满足，就可按引理方式安排剩余工件使竞争比不超过a，称它为正常中止。算法设计原则是尽量使排序正常中止，若不能则另行处理。3/12/202375半在线排序3/12/202376半在线排序3/12/202377半在线排序33223343/12/202378参考文献nSemi-online surveyn何勇，杨启帆，谈之奕，平行机半在线排序问题研究（）.高校应用数学学报,18(1),105114,2003.n何勇，杨启帆，谈之奕，平行机半在线排序问题研究（）.高校应用数学学报,18(2),213222,2003.n基本半在线模型nY.Azar,O.Regev,On-line bin-stretching,Theoretical Computer Science，168,1741,2001.3/12/202379参考文献n基本半在线模型nSeiden,S.,Sgall,J.,Woeginger,G.:Semi-online scheduling with decreasing job sizes.Operations Research Letters,27,215-221,2000.nKellerer,H.,Kotov,V.,Speranza,M.R.,Tuza,Z.:Semi on-line algorithms for the partition problem.Operations Research Letters,21,235-242,1997.nHe,Y.,Zhang,G.:Semi on-line scheduling on two identical machines.Computing,62,179-187,1999.3/12/202380半在线排序（2）半在线模型的复合例如，考察8种简单类型的部分信息复合后的可能结果。3/12/202381半在线排序 考虑两种与实例最后一个工件有关的半在线模型，一是已知最后一件是加工时间最大的工件，二是当实例中最后一件到达时，系统会给排序者一个明显提示。称两者的复合为“end of sequence”。3/12/202382半在线排序111 111111121 1111 1211113/12/202383半在线排序3/12/202384半在线排序3/12/202385半在线排序3/12/2023863/12/202387半在线排序（3）P2|sum&max|Cmax 与P2|sum&decr|CmaxTh2.6 P2|sum&max|Cmax的下界为6/5Proof：设T=10和Pmax=3为已知。13131322213113113133131131131111313231312131 131131122132221 12331 131 131 131223/12/202388半在线排序3/12/202389半在线排序3/12/202390半在线排序3/12/202391半在线排序3/12/202392半在线排序Th2.8 P2|sum&decr|Cmax的下界为10/9Proof：设T=18为已知。444444445/2 5/2 5/2 5/23331445/25/25/25/24433313/12/202393半在线排序3/12/202394半在线排序Th2.9 算法Threshold_Decr(10/9)求解P2|sum&decr|Cmax的竞争比为10/9Sketch of proof：P1P2P3 P4 P5P1P2 P33/12/202395半在线排序Threshold_Decr(10/9)与之前的阀值算法的不同之处：考虑下列实例：3T/143T/14T/7T/7T/7T/73T/163T/16T/8T/8T/8T/8T/8 将工件安排在负载较大的机器上加工，算法竞争比不会优于8/7 将工件安排在负载较小的机器上加工，算法竞争比不会优于9/83/12/202396参考文献n复合半在线模型nTan Zhiyi，He Yong,Semi-on-line problems on two identical machines with combined partial informationOperations Research Letters,30，408414，2002nZhang Guochuan,Ye Deshi.A note on on-line scheduling with partial information,Computer and Mathematics with Applications,2002,44,539-543.nEpstein,L.,Bin stretching revisited.Acta Informatica,39,97117,20033/12/202397参考文献n复合半在线模型nE.Angelelli,M.G.Speranza,Z.Tuza,Semi on-line scheduling on two parallel processors with upper bound on the items,Algorithmica,37,243-262,2003nE.Angelelli,M.G.Speranza,Z.Tuza,New bounds and algorithms for on-line scheduling:two identical processors,known sum and upper bound on the tasks,Discrete Mathematics and Theoretical Computer Science,8,1-16,2006.3/12/202398半在线排序4.P2|dis sum|Cmax和P2|dis opt|Cmax以P2|dis sum|Cmax为例说明算法的竞争比与不精确程度之间的关系。设已知工件总加工时间Tp，rp，这里p0，r 1称为扰动因子。为方便起见，设p=2，从而最优解13/12/202399半在线排序15/24/33/2(4r)/(2r+1)LSThreshold(4/3)3/12/2023100半在线排序(4-2a)r-a a-1 (2-a)r a a-(2-a)ra-(2-a)r12a(1+r)-4r-13/12/2023101半在线排序3/12/2023102半在线排序3/12/2023103半在线排序3/12/2023104半在线排序3/12/2023105半在线排序3/12/2023106 Step 3.2.1(SC1 implicitly satisfied)11.21.2.222.2.133.23.2.12.23/12/2023107 Step 4.2.2(SC1 or SC2 never satisfied)1233.2.244.24.2.23.23/12/2023108半在线排序3/12/2023109半在线排序3/12/2023110ndis sum:ndis opt:,可更小 半在线排序3/12/2023111半在线排序3/12/2023112半在线排序3/12/20231130.04450.76400.03030.29570.03030.2635半在线排序3/12/2023114参考文献n不精确半在线nZhiyi Tan,Yong He,Semi-online scheduling problems on two identical machines with inexact partial information,Theoretical Computer Science,doi:10.1016/j.tcs.2007.02.014,2007.3/12/2023115半在线排序3.半在线模型的其它结果(1)Pm|Cmin对Pm|sum|Cmin，Pm|max|Cmin，最好算法的竞争比均为：3/2 m=2 m-1 m3 对Pm|sum&max|Cmin,最好算法的竞争比为：5/4 m=2 3/2 m=3 m-2 m4与此相反，Pm|opt|Cmin的最好算法尚未得到，已有的两个算法竞争比分别为2-1/m，11/6 3/12/2023116半在线排序Pm|decr|Cmin，已知LSs算法的竞争比为(4m-2)/(3m-1),当m=2，3时最优Pm|UB&LB|Cmin,若以B=UB/LB为参数，LS算法的竞争比为 B 1B m m Bm 且对任意的B都是最好的。3/12/2023117参考文献nPm|Cmin半在线nTan Zhiyi,Wu Yong,Optimal semi-online algorithms for machine covering,Theoretical Computer Science,372,6980,2007.nY.Azar,L.Epstein,On-line machine covering,Journal of Scheduling 1,6777,1998.nT.Ebenlendr,J.Noga,J.Sgall,and G.Woeginger,A note on semi-online machine covering,Proceeding of the 3rd Workshop on Approximation and Online Algorithms,Lecture Notes in Computer Science,3879,110-118,2006.nY.He,The optimal on-line parallel machine scheduling,Computers&Mathematics with Applications,39,117121,2000.3/12/2023118半在线排序(2)Pm|CmaxPm|sum|Cmax,有竞争比为1.6的算法，问题下界为 1.5 m6 1.565 mPm|opt|Cmax，有竞争比分别为(5m-1)/(3m+1)和13/8的算法，问题下界为4/3Pm|decr|Cmax，算法LS的竞争比为4/3-1/3m，但还没有关于下界的讨论。P3|sum&max|Cmax的最好算法竞争比为4/3P3|end of sequence|Cmax的最好算法竞争比为3/23/12/2023119参考文献nPm|Cmax半在线nE.Angelelli,A.B.Nagy,M.G.Speranza,Z.Tuza,The on-line multiprocessor scheduling problem with known sum of the tasks,Journal of Scheduling,7,421-428,2004.nT.C.E.Cheng,H.Kellerer,V.Kotov,Semi-on-line multiprocessor scheduling with given total processing time,Theoretical Computer Science,337,134-146,2005.nYong Wu,Zhiyi Tan,Qifan Yang,Optimal semi-online scheduling algorithms on a small number of machines,Proceeding of the 1st international symposium on combinatorics,algorithms,probabilistic and experimental methodologies,Lecture Notes in Computer Science,2007.3/12/2023120半在线排序(3)Q2|Cmax 和 Q2|Cmin对Q2|decr|Cmax，其最好算法的竞争比为：3/12/2023121半在线排序3/12/20231223/12/2023123半在线排序对目标为极大化机器最小完工时间情形，目前只对Q2|opt|Cmin 和 Q2|sum|Cmin得到了最好算法，它们的竞争比分别为：3/12/2023124The optimal bounds of Q2|sum|Cmin and Q2|opt|Cmin.The bold lines are for Q2|sum|Cmin3/12/2023125参考文献nQ2|Cmax和Q2|Cmin半在线nEpstein,L.,Favrholdt,L.M.:Optimal non-preemptive semi-online scheduling on two related machines.Journal of Algorithms,57,4973,2005.nTan Zhiyi,Cao Shunjuan,Semi-online machine covering on two uniform machines with known total size,Computing,78,369-378,2006.3/12/2023126第三章：其他在线排序问题n极小化最大开工时间Th3.1(1)P2|Smax的下界为2 (2)P3|Smax的下界为5/2 (3)Q2|Smax的下界为1+STh3.2 LSs是求解P2|Smax，P3|Smax和Q2|Smax的最好算法对Pm|Smax，Epstein和Stee证明了LSs算法的竞争比为O(logm),并给出了竞争比为12的算法Balance，并证明了当m时，问题的下界至少为43/12/2023127参考文献n最大开工时间nL.Epstein,R.van Stee,Minimizing the maximum starting time on-line.Information and Computation,195,53-65,2004.n(offline)L.Epstein,T.Tassa,Approximation schemes for the min-max starting time problem,Acta Informatica 40,657-674,2004.3/12/2023128其他在线问题3/12/2023129其他在线问题3/12/2023130其他在线问题3/12/2023131其他在线问题3/12/2023132参考文献n可拒绝加工排序问题nBartal Y,Leonardi S,Marchetti-Spaccamela A,Sgall J,Stougie L,Multiprocessor scheduling with rejection.SIAM Journal on Discrete Mathematics,13,6478,2001.nHe Y,Min X,On-line machine scheduling with rejection.Computing,65,112,2000.nDosa G,He Y,Preemptive and non-preemptive on-line algorithms for scheduling with rejection on two uniform machines.Computing,76,149164,2006.3/12/2023133其他在线问题3/12/2023134参考文献n带机器费用排序问题nImreh C,Noga J，Scheduling with machine cost.RANDOM-APPROX99,Lecture Notes in Computer Science,1671,168176,1999.nDosa G,He Y,Better on-line algorithms for scheduling with machine cost.SIAM Journal on Computing,33,10351051,2004.nY.He,S.G.Han,Y.W.Jiang,Online algorithms for scheduling with machine activation cost,Asia-pacific Journal of Operations Research,to appear.nHAN Shu-guang,JIANG Yi-wei,HU Jue-liang,Online algorithms for scheduling with machine activation cost on two uniform machines,Journal of Zhejiang University SCIENCE A,8,127-133,2007.3/12/2023135其他在线问题3/12/2023136参考文献n在线问题资源增广研究nL.Epstein,A.Ganot,Optimal on-line algorithms to minimize makespan on two machines with resource augmentation,Proceedi