工件具有相似长度的半在线排序问题

《工件具有相似长度的半在线排序问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、湖南师范大学硕士学位论文工件具有相似长度的半在线排序问题姓名：陈强申请学位级别：硕士专业：运筹学与控制论指导教师：李荣珩20090301摘要本硕士论文由三章组成，主要讨论两类在m台平行机器上加工的工件具有相似长度的半在线排序问题．第一个问题是对于在m台同型机器上加工，具有相似长度，即工件的加工时长在【1，r】内的情况，通过对Ls算法的分析，得出了改进的最坏情况性能比．第二个问题是考虑工件在m台同类机器上加工，有到达时间，具有相似长度，提出了一个新的算法，并得出了相应的最坏情况性能比．第一章介绍了问题

2、研究的背景和该领域的研究现状，主要介绍了一下最坏情况性能比，机器的分类，等基础知识．第二章分别从两个方面对LS算法在第一种情况下的最坏性能比进行分析，得到了改进的结果．第三章对于第二个问题，构造新的算法，证明其最坏情况性能比．关键词：最坏情况性能比，到达时间，相似长度．ABSTRACTThisthesisofMasteriscomposedofthpeech印ters．WbmailllystudytWoprob—lemsofsemion·linescheduljngwiththejob1engthj

3、nf1，r】onmparallelmachineS．Thefirstproblemcanbefomallyde丘nedaLsfollows．Asequenceofjobsjstobescheduledonmparallelidenticalma(．hjnes．Int址ssemion-linesjtuatjon，thejobs’sreleasetimesa弛nomallynon—decreausing．westudythecompetmveratioofa1缈rithmLSthenobtainabet

4、terresult．Thesecondproblemw_estudythesituatjonasequenceofjobsistobescheduledonmp甜aJleluniformmachjnes．Inchapterl，Introdu(．esthebackgroundoftheproblem—researchjngandtherecentdeVelopmentoftheresearchinthjsfield．besides，w，e百VebaSicnotionofcompetitiveratio

5、n，甜gofithmLS，ands0on．Inch印ter2，、艴majnlystudythecompetitiverationofalgoritllIIlLSf如mtwodjH色rentsides锄d17l陀obtainsomeresults．Inch印ter3，we舀veanewaLlgorithmforthesecondsituation锄dprovethecOmpetitivera土iOn．Keywords：CompetitiveRation，ArrivaJtimes，SimilarLen昏

6、hs．III工件具有相似长度的半在线排序问题湖南师范大学学位论文原创性声明本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究工作所取得的成果．除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的作品成果．对本文的研究做出重要贡献的个人和集体，均已在文中以明确方式标明．本人完全意识到本声明的法律结果由本人承担．学位论文作者签名：7麦；罩勿。71年6月弓日湖南师范大学学位论文版权使用授权书本学位论文作者完全了解学校有关保留，使用学位论文的规定，同意学校保留并向国家有

7、关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅．本人授权湖南师范大学可以将学位论文的全部或部分内容编人有关数据库进行检索，可以采用影印，缩印或扫描等复制手段保存和汇编本学位论文。本学位论文属于1、保密口，在——年解密后适用本授权书．2、不保密口．(请在以上相应方框内打”／，)}．LrI．．Lrl五／，／、月月年年砰文√卅彳期期日日'丁亏祷考，一隐镶李名名签签者师作导工件具有相似长度的半在线排序问题1绪论排序问题是组合优化中一类重要的问题，有着广泛的实际应用背景，在生产管理和调度，网路通讯

8、及理论计算机科学等方面有着广泛的运用．人们对各类排序问题的研究越来越深入，并且取得了一系列好结果．1．1问题产生的背景从最优化的角度来说安排时间表(sc^eduzi哪)是为完成若干项任务而把所需要用到的人、财、物等资源按时问进行最优分配，最优排序，和最优调度．我们应该把“排序’’理解为两种涵义：狭义的涵义是安排次序；广义的涵义是安排时问表．排序领域内许多早期的工作是在制造业的推动下发展起来的，所以在描叙排序问题时很自然会使用制造业的术语．虽然排序问题在许多非制造业的领