《骨有前瞻区间和运输时间在线排序》由会员分享，可在线阅读，更多相关《骨有前瞻区间和运输时间在线排序（44页珍藏版）》请在金锄头文库上搜索。
1、AthesistedtoZhengzhouUniversityforthedegreeofMasterOn-lineSchedulingwithLookaheadandDeliveryTimesByJikuiYangSupervisor：ProfWenhuaLiMasterofScienceOperationsResearchandCyberneticsDepartmentofMathematicsMay2012原创性声明111111111111111叭Y21031本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个
2、人或集体已经发表或撰写过的科研成果。对本文的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明的法律责任由本人承担。学位论文作者：物继奎日期：2012年5月学位论文使用授权声明本人在导师指导下完成的论文及相关的职务作品，知识产权归属郑州大学。根据郑州大学有关保留、使用学位论文的规定，同意学校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人授权郑州大学可以将本学位论文的全部或部分编入有关数据库进行检索，可以采用影印、缩印或者其他复制手段保存论文和汇编本学位论文。本人离校后发表、使用学位论文或与该学位论文直接相关的学术论文或成果时，第一署名单位仍然为郑州大
3、学。保密论文在解密后应遵守此规定。学位论文作者：杨继奎日期：2012年5月摘要排序就是在一定的限制条件下，分配时间资源去完成一些任务，使得一个或者多个目标达到最优近年来，平行分批排序和在线排序是两个发展比较迅速的排序模型平行分批排序模型中，机器可以同时加工多个工件，并且每批的加工时间是该批所有工件中加工时间的最大者一旦批开始加工就不能被中断，直到该批被加工完毕在线排序模型中，工件的信息在其到达之前是一无所知的，并且一旦工件被安排之后就不允许再改变在L模型下，在时刻t，在线算法能预见到将在时间区间(t，t+励()】内到达的所有工件的信息，而p(t)是在时刻t可用工件中加工时间最大者本文研究了两种
4、排序模型：(1)带有前瞻区间的平行分批处理机的在线排序问题；(2)带有运输时间的单机在线排序问题采用Graham等人【1】提供的三参数表示法，这些问题分别表示为1on-line，吩，p-batch，b=CO，L饰IG瞰；1on-line，吩，p-batch，agreeable(pj，qj)，b=oO，L绵ILm“；1on-line，吩，劬功l厶。姒下面我们具体地给出本文的主要结果在第二章中，对于前两个在线分批排序问题，我们分别证明了这些问题的竞争比的下界至少是1+口，其中口是方程口2+1)口+卢一1=0的一个正根，然后分别提供了一个竞争比为l+Q的在线算法研(口，p)和凰(口，卢)，最后我们证
5、明了当0o)，如文献13和【2s显然，竞争比砒越趋近于1，在线算法得到的目标函数值就越趋近于离线情形下的最优目标函数值，那么在线算法也更优良本论文我们研究的都是关于最小化目标函数的排序问题对3于某个在线排序问题，如果它的一个在线算法的竞争比与该问题的竞争比的下界匹配，那么我们就说该在线算法是这个排序问题最好可能的在线算法，这也意味着该问题被彻底解决，如文献51，33】和【19】中给出的算法都是最好可能的对于大部分在线排序问题，决策者在设计在线算法时，并不知道未来工件的信息，因此设计好的在线算法的难度相当大，决策者往往都不能找到最优的解决方案而半在线排序，也即满足一定限制条件的在线排序，是介于在
6、线排序和离线排序之间的一类排序在此排序模型中，不能对已经安排的工件进行重新排序，在排序之前决策者虽然不知道工件的所有信息，但是可以预先知道后面工件的一部分信息(参见Tang等人【24】)，比如工件的运输时间不大于它的加工时间、加工时间大的工件需要比较长的运输时间(参见Yuan等人【26】)或者已知道工件的总加工时间和(参见文献【6】、【7】和【10】)等因为工件的部分信息是已知的，所以相对于在线排序而言，不仅问题的难度减小了，而且也适用于决策者找到更接近于最优的排序方案由于半在线排序问题中已知的工件的部分信息可以是不同的，因此就有不同的半在线排序模型在文献8】和【9】中，作者把半在线排序问题分
7、为三种类型：第一种类型为决策者知道后续工件的部分信息：第二种类型为已经被安排的工件的加工进程可以通过某种方式进行改变；第三种类型是不能列入前两类的本文主要研究了使用Lookahead模型的排序问题，它属于第一种半在线排序问题在不同的排序问题中，排序问题研究者给出了Lookahead模型不同的定义(参见文献【11】和【28】)，我们举例说明，对于最小化总完工时间的单机在线排序问题，Mao和Kincaid在文献【15】中定义的Lookaheadk模型为：在任意时刻t，任意在线算法4都可以预见到接下来即将到达的k个工件的信息对于最大化按时完工工件个数的单机在线排序问题，Zheng和Xu等人在文献【2
8、8】中把Lookahead参数LD定义为时间长度而不是工件的个数，如果在任意时刻t，在线算法4能预见到在时间区间(t，t+LD)内将要到达的所有工件的信息，那么算法A是L眈Dlookahead模型，而Lookahead参数LD是非负实数特别地，当LD拳0时，模型就归结为不使用Lookahead的形式文献【13】也使用了Lookahead模型在本文中，我们也是把Lookahead参数定义为时间长度，即在任意时刻t，任意在线算法都能预见到将在时间区间(t，t+励(亡)】内到达的所有工件的信息，其中，p()是时刻t可用工件的长度该Lookahead模型可以简单记为L模型，其中p04在经典排序中，我们
9、还假设任何机器在任何时刻最多只能加工一个工件，而实际生活中有的机器可以加工多个工件例如，一个烤箱可同时烘烤多个面包最典型的例子发生在大规模集成电路的生产中，为了保证成品合格；检验阶段要把集成电路放在烘箱中试验它们的耐温性(见Lee等人【12】)一个烘箱可以同时检测多个集成电路，而且在检验过程中不可以移走任何集成电路我们把这种机器可以同时加工多个工件的排序问题称为分批加工机器排序(schedulingabatchingmachine)+分批排序问题与经典排序问题的不同在于若干工件可以在一批中加工，工件加工过程中不允许中断，也不允许移走正在加工的工件在分批排序中，如何确定批是问题的关键，一旦批确定
10、下来，就可以将批视为一个工件来寻找其最优算法或近似算法根据每批的加工时间的定义不同，它又可分为平行分批(parallelbatch)和继列分批(serialbatch)平行批是指，同一批中的工件是同时开工且同时完工的，每一批的加工时间等于该批中最长工件的加工时间；继列批是指，一批中的工件是排列成一个序列进行加工的，同一批的工件也具有相同的开工时间和加工时间，但每一批的加工时间等于该批所有工件加工时间之和本文我们所考虑的模型是平行分批根据批容量B的大小可以将批处理机分为两类：批容量无界(B=oo)和批容量有界(Bmaxto，咖)，根据算法日(口，p)的执行：如果在80时刻无工件到达，由第(41)
11、步知，批玩在ro处加工，即to=伯，与80maxto，apo矛盾若80时刻存在一个工件，加工时间为P且PPo，则第(421)步知，批风中的最大工件为，即80=ro这与80maxto，apo矛盾若Pmaxro，apo，根据算法凰(Q，卢)的执行，存在一个加工时间为P，(吾，所以，任何时刻大工件的个数至多为1算法日：第0步：若时刻t机器空闲并且v(t)D，确定p(t)和口(t)；否则，一直等待这样的时刻出现第1步：若Pp(t)击p(B(t)，在时刻t加工工件山()第2步：若工件厶t)是唯一到达的工件，即uCt)=1，则等到有新的工件到达，但至多等到(讵一1)ppct)时刻第3步：若lu(亡)I2时
12、，执行下面的步骤第31步：若t+p(UCt)、(t)，则加工工件()第32步：若t+PWCt)、趸砖(t)，则选择运输时间次长的工件加工第32步：返回第0步在本节中我们将采用反证法证明在线算法日的竞争比为以假设存在这样的实例使得在线算法日的竞争比严格大于以令和7r分别表示是算法日所产生的在线排序和在离线情形下的一个最优排序于是，Lm腿(盯)击p(B()=击(p(B)+A)epp(B)S8+qz因此，我们有LmaX(仃)一上，maDc(丌)最p)+p(G(Z)+锄根据等式(41)，我们得到Lm觚(仃)一k觚(7r)Pk因为实例，是一个最小反例，所以揪乳max(丌)下面我们考虑m的大小分两种情形讨
13、论情形11在时刻鼠(盯)，以不是一个大工件，则有mp(B(鼠p)+p(aq)+俄鼽(以一1)Lm觚(丌)(以一1)(p(B(瓯(盯)+p(G(z)+91)(42)进而可得Ptp(Gq)瓯(仃)+p(G(z)+ph+qk瓯(口)+轨所以，鱼号毫掣(钜一1)m，1)若R=a，由算法日知以是大工件且R=12l，由瓯(仃)(以一1)m可知，n前无工件到达，所以住=风p)，由式(41)可得Lmax(Tr)irk+m+p(G(z)4-ql=鼠(仃)+m+p(G(z)+口l=Lmax(O)这与假设，是反例矛盾2)若冗a，令厶为排序口中在时刻鼠(盯)完成加工的工件，则irllax(o)=风(盯)+Pa+m+p
14、(G(z)+qt(43)因在时刻鼠(矿)工件五是大工件，有卿：=击p(B(鼠(盯)击仞(冗)+陬)，所以p(n)(以一1)pk，且最(矿)=瓯(盯)+m，所以，瓯(盯)、轨一慨+p)、轨一p(u(sk(仃)由算法日知在时刻&(口)，STEP(31)发生，但先加工的是，故PhPk但这与p晶(仃)时，有k畎(7r)maxIrk+Pk+p(G(z)+gl，p(R)+Pk+p(G(z)(45)有式(43)和式(45)得Lm觚(盯)一二max(7r)风(仃)+住+砌(以+1)p(R)(钜+1)ph因为实例，是反例，由不等式(45)可知，PhLmax(a)一kaX(丌)(以一1)Lm觚(丌)(以一1)仞(
15、冗)+m+p(G(z)(以一1)慨+(钜十1)pa)惭得出矛盾，所以这种情形不存在情形2在时刻鼠(盯)，大工件以和集合G(t)中部分工件已到达，不妨设G(t)中最早到达的工件为厶若7m嘞t)，则加工大工件以，若t+p(u(O)弛(t)，则选择运输时间次长工件仍然是以，这是因为瓠+m+p(G(z)+口l，我们得到Lm觚(盯)一Lm畎(7r)一“(、21)(丌)情形3在时刻s七Ca)，工件集G(Z)含有一个大工件(不妨设为五)，并且算法日选择运输时间次长的工件以而没选择大工件J：I用反证法得到在时刻瓯(仃)，集合G(1)中只有唯一一个工件J；I到达如若不然，除了五之外，G(z)中存在工件易满足吩Ss七Ca)根据集合G(z)的定义，可知劬弧且彩弧因为五是时刻最p)的大工件，工件五与如的运输时间都比的大，由STEP(32)知算法H在时刻瓯p)选择运输时间次长的工件，即J；f与易中的一个，不会选择五加工，但此与算法日在时刻瓯(口)选择以矛盾31因此，在时刻鼠(口)，根据算法日中STEP(32)选择加工运输时间次长的工件以加工，且t+p(vCt)嘞t)，这就表明瓯(盯)+m(以一1溉又Lmax(1r)p(cq)+qz，根据式(41)，我们得到：Lmax(盯)一Lmax(n)鼠(口)+m冬(、21)鼽(21)LmaX(7r)以上的讨论表明实例I不是一个反例，故
