【作者】 齐祥来；

【导师】 原晋江；

【作者基本信息】 郑州大学 ， 运筹学与控制论， 2018， 博士

【摘要】 分层排序(又称带服务等级的排序)是排序论领域中的一个重要分支,近年来受到许多研究者的关注.在一些排序环境中,工件仅允许在一些预先指定好的机器上进行加工.在这种情况下,每个工件乃预先指定一个非空的机器子集Mj,使得该工件只能在这个指定的机器子集Mj上进行加工;我们称该机器子集Mj为该工件的可用集(eligible set).本文仅讨论包含加工集型,该情形在相关文献中也称为带服务等级的(grade ofservice eligibility,shortly,GoS eligibility)或分层的(hierarchical)排序问题.在本文中，我们称之为分层排序问题.分层排序问题在不同的领域有很多的实际应用.例如,在现在服务行业中,顾客经常被分成若干个不同的类型,比如金卡会员、银卡会员、普通会员、非会员等.这种分类代表了顾客的各个不同级别,对不同级别的会员所提供的服务也不尽相同,高级别的会员往往比低级别的会员会得到更多的服务;在无线通信网络中,信息会按照重要程度的不同进行分类,更紧急的信息会优先得到传送.本学位论文研究了分层排序和多代理排序中的若干问题.学位论文共分四章:·第一章简述了排序论的应用背景、发展历程、常用记号和术语,介绍了分层排序和多代理排序问题的基本理论与方法,并对与本文相关的一些研究结果进行了综述.·第二章研究了工件可分模型下两台恒同机上在线和半在线的分层排序问题,目标函数是最小化机器负载向量的P-范数.对在线算法和半在线的分层排序问题,我们分别给出了最好可能的在线和半在线算法,这里的半在线指的是已知所有工件的加工时间之和.·第三章研究了工件不可分模型下两台恒同机上在线和半在线的分层排序问题,目标函数是最小化机器负载向量的P-范数.我们在多种情形下给出了最好可能的在线算法和半在线算法,其中在半在线情形下,我们研究了三种环境,分别是已知所有工件的加工时间和,已知每种等级限制的工件的加工时间和,以及机器具有缓存空间(buffer)或允许重排(rearrangement)的情形.·第四章研究了双代理情形下的排序问题.通过给出一个反例,我们证明由Yin 等人[109]对问题l|s-batch｜∑CjA+ mAφA:LmaxB+mBφB≤U给出的SMDP算法是错误的.我们进一步证明由Kovalyov等人[65]对问题1|s-batch|∑CjA:LmaxB ≤ U给出的算法可以在O(nnA2nB3)时间内解决问题1|s-batch｜∑CjA+ mAφA:LmaxB+mBφB≤U.最后,通过估计和枚举代理B的所有可能的最大延迟,我们证明Pareto排序问题1|s-batch|#(∑CjA,LmaxB)和1|s-batch|#(∑CjA+mAφA,LmaxB+mBφB)可以在O(nnA4nB5)时间内解决.更多还原

【Abstract】 The hierarchical scheduling(also called scheduling with grade of service el-igibility)is an important research direction in scheduling theory,and has re-ceived high attention because of its practical and theoretical significance.In some scheduling setting,jobs are only allowed to be processed on some pre-defined ma-chines.In such a case,each job Jj has a non-empty subset of machines(denoted by Mj)that can process the job,referred to as the eligible set of the job.In this thesis,we only consider the inclusive sets.This restriction is also called grade of service eligibility(shortly,GoS eligibility),or hierarchical scheduling.In this thesis this scheduling model is called the hierarchical scheduling.Hierarchical scheduling has many applications in different areas.For example,in the service industry in which a service provider has customers categorized as platinum,gold,silver,and regular members,where those special members are entitled to premi-um services;in wireless communication networks,messages can be classified by their importance,more urgent messages will be sent first.We study in this thesis some hierarchical scheduling problems and two-agent scheduling problems.The thesis consists of four chapters:In Chapter 1,we first introduce the background,development history,com-mon notations and terminologies etc.on scheduling theory,and emphatically introduce the fundamental notions and methods on hierarchical scheduling and scheduling problem with multi-agent.Then we give a review of the related re-search results.In Chapter 2,we consider the hierarchical scheduling problem on two iden-tical machines to minimize the lp-norm.In this chapter,we study the online and semi-online scheduling problems in the settings of fractional assignment,and de-sign best possible algorithms for them,where semi-online means that the total processing time of the jobs is known in advance.In Chapter 3,we consider the hierarchical scheduling problem on two identi-cal machines to minimize the lp-norm in the settings of integral assignment.We also consider online and some semi-online scheduling problems and design best possible algorithms for them,where we study three semi-online versions:in the first version,knowing the total processing time of the jobs in advance,in the second version,knowing the total processing time Ti of the jobs of hierarchy i for i= 1,2 in advance,and in the last version,buffer or arrangement being allowed.In Chapter 4,we consider two-agent scheduling.By a counterexample,we show that the algorithm SDMP presented in Yin et al.[109]for problem 1|s-batch|∑CjA+mAφA:LmaxB+mBφB ≤ U is incorrect.Then we further show that the algorithm presented in Kovalyov et al.[65]for problem 1|s-batch| ∑ CjA:LmaxB≤ U can be used to solve problem 1|s-batch| CjA +mAφA:LmaxB+mBφB≤U in O(nnA2nB3)time.Finally,by guessing and enumerating the possible max-imum lateness of agent B,we show that the two Pareto scheduling problem-s 1|s-batch|＃(∑CjA,LmaxB)and 1|s-batch|＃(∑CjA+mAφA,LmaxB+mBφB)are solvable in((nnA4nB5)time.更多还原