平行机在线排序问题VIP免费

24/12/26p.1平行机在线排序问题24/12/26p.2平行机在线排序问题在线排序问题几种不同的在线模型onlineoverlist的最新结果半在线排序问题半在线问题概述P2||Cmax半在线问题的若干结果其他半在线模型的主要结果“非典型”在线排序问题24/12/26p.3平行机在线排序问题m台平行机，n个工件，工件加工不可中断同型机（identicalmachine）：每台机器完全一样同类机（uniformmachine）：每台机器的速度不同24/12/26p.4把需要完成的任务称为工件（job）把完成任务需要的资源称为机器1212,,,,,)nnJJJppp（或1,,2mMMM平行机在线排序问题1221/1=SSSm2/iijiimMSJMSSSj设机器的速度为，则在上加工所需时间为p同类机，假设特别，当时，用s=表示两台机器的速度比24/12/26p.5平行机在线排序问题jii(),()(),(1)minCmax,makespanCmax=max(2)maxmin,Cmin=minLjiijCJLMSCjj设为工件的一个排序，分别用S表示工件的开工时间与完工时间（不引起混淆时略去）用表示的完工时间考虑以下两种目标函数：极小化，其中极大化机器最小负载，其中24/12/26p.6平行机在线排序问题定义在线算法A求极小化问题的竞争比（competitiveratio）为}),()(|1{infIIcCICccOPTAA)(ICA：算法A解实例I所得的目标值；)(ICOPT：实例I的最优目标值；I取遍该问题的所有实例．24/12/26p.7平行机在线排序问题maxtthreefieldnotation)||PQCmaxCminT=pmaxp(jjjtiipplMnj=1三参数表示法（、分别表示同型机和同类机和表示两类目标函数表示所有工件的总加工时间表示最大工件的加工时间表示工件到达未加工）时机器的负载24/12/26p.8第一章：在线排序在线问题的一般假定：工件一个个地到达，工件信息随着加工过程逐个依次释放工件一旦被安排就不能改变根据实际背景要求，下面给出常见的几种在线模型24/12/26p.9Onlineoverlist•Onlineoverlist：1.工件在零时刻一个个地到达，工件Ji到达后其信息（加工时间）完全已知，且被安排在某台机器上自某时刻起开始加工，其后的工件信息未知。2.工件一旦被安排就不能改变24/12/26p.10OnlineoverlistLS算法（ListScheduling)：•LSs算法jk1lminjjjiimpplk设是当前到达待安排的工件，将安排在能使其最早开工的机器上加工，即机器M满足24/12/26p.11OnlineoverlistLSiLSn1Th1.1LSsPm|onlineoverlist|Cmax2msketchofproofMC()C()CinILpI求解的竞争比为：设是决定实例目标函数值的机器，即设是最晚完工的工件，即Pn…Pk…Mi实例ICk…Pk…Mi实例I’Ck24/12/26p.12Onlineoverlist**maxLS***TTC(),C()mTm-1m-11C()C()C()(2)C()mmmmnnnnnnnnmSpIIpTpICSpppIIIm又…P11…l1l2MiliSnCn24/12/26p.13Onlineoverlist2212mm1LSLS**1,C()2m-11C()21,C(),2C()mmmmppppmIImImI为证明界是紧的，考虑下面的实例…显然有证毕。11111111…1………111mm-111111111…1……111mmLS*C()21C()ImIm24/12/26p.14Onlineoverlist123m22Th1.2Pm|onlineoverlist|Cmax5m33sketchofproofm21pp的下界为：：当时，考虑实例**21322AACCCC1111112**3232AACCCC24/12/26p.15Onlineoverlist5m33当时，可类似证明下界为证毕。**21523AACCCC**747543AACCCC111111111**=10653AACCCC1113331113331113331113336111333624/12/26p.16参考文献OnlinesurveyK.Pruhs,E.Torng,J.Sgall,Onlinescheduling,InHandbookofScheduling:Algorithms,Models,andPerformanceAnalysis,ed.JosephY.-T.Leung,chapter15,pages15-1-15-41,CRCPress,2004.J.Sgall,On-linescheduling,InOnlineAlgorithms:TheStateoftheArt,ed.A.FiatandG.J.Woeginger,LectureNotesinComput.Sci.1442,pages196-231,Springer,1998.24/12/26p.17参考文献OnlineoverlistGraham,R.L.:Bound...