分层在线排序及双代理排序研究
分层排序(又称带服务等级的排序)是排序论领域中的一个重要分支,近年来受到许多研究者的关注.在一些排序环境中,工件仅允许在一些预先指定好的机器上进行加工.在这种情况下,每个工件乃预先指定一个非空的机器子集Mj,使得该工件只能在这个指定的机器子集Mj上进行加工;我们称该机器子集Mj为该工件的可用集(eligible set).本文仅讨论包含加工集型,该情形在相关文献中也称为带服务等级的(grade ofservice eligibility,shortly,GoS eligibility)或分层的(hierarchical)排序问题.在本文中，我们称之为分层排序问题.分层排序问题在不同的领域有很多的实际应用.例如,在现在服务行业中,顾客经常被分成若干个不同的类型,比如金卡会员、银卡会员、普通会员、非会员等.这种分类代表了顾客的各个不同级别,对不同级别的会员所提供的服务也不尽相同,高级别的会员往往比低级别的会员会得到更多的服务;在无线通信网络中,信息会按照重要程度的不同进行分类,更紧急的信息会优先得到传送.本学位论文研究了分层排序和多代理排序中的若干问题.学位论 ...