资源描述：
《分层在线排序及双代理排序研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、学校代码10459学号或申请号201311140057密级博士学位论文分层在线排序及双代理排序研究作者姓名：齐祥来导师姓名：原晋江教授学科门类：理学专业名称：运筹学与控制论完成时间：2018年3月AdissertationsubmittedtoZhengzhouUniversityforthedegreeofDoctorAstudyononlinehierarchicalschedulingandtwo-agentschedulingCandidate:XianglaiQiSupervisor:Prof.JinjiangYuanSpe
2、ciality:OperationsResearchandCyberneticsDepartment:SchoolofMathematicsandStatisticsDate:March,2018摘要分层排序(又称带服务等级的排序)是排序论领域中的一个重要分支,近年来受到许多研究者的关注.在一些排序环境中,工件仅允许在一些预先指定好的机器上进行加工.在这种情况下,每个工件??预先指定一个非空的机器子集ℳ?,使得该工件只能在这个指定的机器子集ℳ?上进行加工;我们称该机器子集ℳ?为该工件的可用集(eligibleset).本文仅讨论包含加
3、工集型,该情形在相关文献中也称为带服务等级的(gradeofserviceeligibility,shortly,GoSeligibility)或分层的(hierarchical)排序问题.在本文中,我们称之为分层排序问题.分层排序问题在不同的领域有很多的实际应用.例如,在现在服务行业中,顾客经常被分成若干个不同的类型,比如金卡会员、银卡会员、普通会员、非会员等.这种分类代表了顾客的各个不同级别,对不同级别的会员所提供的服务也不尽相同,高级别的会员往往比低级别的会员会得到更多的服务；在无线通信网络中,信息会按照重要程度的不同进行分类,
4、更紧急的信息会优先得到传送.本学位论文研究了分层排序和多代理排序中的若干问题.学位论文共分四章：∙第一章简述了排序论的应用背景、发展历程、常用记号和术语,介绍了分层排序和多代理排序问题的基本理论与方法,并对与本文相关的一些研究结果进行了综述.∙第二章研究了工件可分模型下两台恒同机上在线和半在线的分层排序问题,目标函数是最小化机器负载向量的?-范数.对在线算法和半在线的分层排序问题,我们分别给出了最好可能的在线和半在线算法,这里的半在线指的是已知所有工件的加工时间之和.∙第三章研究了工件不可分模型下两台恒同机上在线和半在线的分层排序问题
5、,目标函数是最小化机器负载向量的?-范数.我们在多种情形下给出了最好可能的在线算法和半在线算法,其中在半在线情形下,我们研究了三种环境,分别是已知所有工件的加工时间和,已知每种等级限制的工件的加工时间和,以及机器具有缓存空间(buffer)或允许重排(rearrangement)的情形.i∙第四章研究了双代理情形下的排序问题.通过给出一个反例,我们证∑︀明由Yin等人[109]对问题1
6、s-batch
7、??+??:??+??≤?给???max??出的SMDP算法是错误的.我们进一步证明由Kovalyov等人[65]对问题∑︀1
8、s-b
9、atch
10、??:??≤?给出的算法可以在?(??2?3)时间内解决问题?max??∑︀1
11、s-batch
12、??+??:??+??≤?.最后,通过估计和枚举代理?的???max??∑︀所有可能的最大延迟,我们证明Pareto排序问题1
13、s-batch
14、#(??,??)和?max∑︀1
15、s-batch
16、#(??+??,??+??)可以在?(??4?5)时间内解决.???max????关键词：分层排序;双代理;??-范数;在线算法;半在线算法;最好可能的;Pareto最优点;多项式时间算法.iiAbstractThehierarchical
17、scheduling(alsocalledschedulingwithgradeofserviceel-igibility)isanimportantresearchdirectioninschedulingtheory,andhasre-ceivedhighattentionbecauseofitspracticalandtheoreticalsignificance.Insomeschedulingsetting,jobsareonlyallowedtobeprocessedonsomepre-definedma-chines.I
18、nsuchacase,eachjob??hasanon-emptysubsetofmachines(denotedbyℳ?)thatcanprocessthejob,referredtoastheeligibleseto
