几类新型在线分批排序问题研究

《几类新型在线分批排序问题研究》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、曲阜师范大学研究生学位论文原创性说明（根据学位论文类型和应地在划“0）本人郑重声明：此处所捉交的博士颐士□论文《几类新型在线分批排序问题》,是本人在导师指导下，在曲阜师范大学攻读博士同/硕士□学位期间独立进行研究工作所取得的成果。论文中除注明部分外不包含他人已经发表或撰写的研究成果。对木文的研究工作做出重要贡献的个人和集体，均已在文中已明确的方式注明。本声明的法律结果将完全由本人承担。作者签名：日期：曲阜师范大学研究生学位论文使用授权书（根据学位论文类型和应地在“□”划“曲）《几类新型在线分批排序

2、问题》系本人在曲阜师范大学攻读博士0硕士□学位期间,在导师指导下完成的博士/陋士□学位论文。本论文的研究成果归曲阜师范大学所有，本论文的研究内容不得以其他单位的名义发表。本人完全了解曲阜师范大学关于保存、使用学位论文的规定，同意学校保留并向有关部门送交论文的复卬件和电子版本，允许论文被查阅和借阅。本人授权曲阜师范大学，可以采用影印或其他复制手段保存论文，可以公开发表论文的全部或部分内容。日期:FI期:作者签名:导师签名:本文提出并研究一些新型的排序问题，其模型是经典排序问题和现有的排序问题的推广。

3、经典排序问题中，工件的加工时间是不变的，我们研究工件的加工时间依赖开工时间或者开工位置变化的模型；目前几乎没有研究在线与恶化效应结合的排序问题文献,我们提出相关模型并研究；经典的在线问题(overtime模型)是指工件只有到达后才知道信息，也就是说要做决策必须要等到工件到达，我们研究的在线模型是提前一段时间就知道工件的信息。本文研究的工件信息到达时间是依时间(overtime)的，分批模型是指平行批模型，即工件同一时刻最多加工B个工件，B为机器的容量，批的加工时间为该批工件屮最大的加工时间。本文主

4、要由四个部分纽•成。第一章，我们介绍排序问题和算法复杂性的一些基本知识，并对在线排序、分批排序、带恶化效应的排序的研究进行了综述。第二章研究加工时间是一般函数的排序问题，主要考虑了两类有一•般加工时间函数的排序问题，工件的加工时间分别为基本加工时间与开工时间函数、位置函数的和。对于加工时间依赖开工时间的模型，证明一定条件下极小化最大完工时间和极小化总完工时间是多项式可解的。对于加工时间依赖开丁位置的模型，给出极小化最大完丁-时间和总完工时间的最优序，同时证明了极小化加权总完工时间的一个最优排序性质

5、并给出一个贪婪算法。第三章研究加工时间是具有线性恶化效应的在线排序问题，工件0的实际加工时间为Pj=bjZt,其中仿为基本加工时间0为恶化率,/是开工时间，H标为极小化a1«2♦2u5"2(算法為弘并证明其竞争比为(1++1，:其中伽=最大完工时间。证明不分批的单机在线问题的下界至少为】也;对批容量无限的单机在线问题给出一个在线算法0弘,并证明其竞争比和问题的下界相同，为(1+4〃+1,其中“二亠加,进而算法是最优的；对于批容量无限的同排序问题，给出在线丨）+加2（I-（z）2+4（（z+1）2（

6、1+0第四章研究工件具有提前预知信息的在线排序问题，从预知时间到工件可加工的时间之间间隔为Q,还知道工件的最大加工是为》唤，忖标为极小化最大完工时间，对于批容量无限的单机在线问軀给出一个在线算法卩弘,并证明其竞争比和问题的下界相同，为1+(V).4/huaxy,其中厂-1+l+z“々，进而算法是最优的；对于批容卑无护的同畀机排序问题，给出在线算法并证明其竞争比为1+加，其中ym=-m+加2+4施+“々。最后，我们对本文研究的问题进行了总结和展望。••11关键词：排序；在线算法；分批排序；恶化效应；

7、竞争比AbstractInthispaper,wepresentandconsidersomenewschedulingproblems,whichgeneralizetheclassicorexistingschedulingproblems.Forclassicschedulingproblems,thejob^sprocessingtimeisfixed,andwestudythemodelsofsinglemachineschedulingwithgeneralprocessingtim

8、efunctions.Thereisnearlynoarticleatpresentaboutthecombiningmodelsonlineschedulingandschedulingwithdeterioration,weconsideringthemandgetsomenewschedulingmodels・Forclassiconline(overtimemodel)schedulingproblems,thejob5sinformationwillbeknownaft