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