肖 满，丁 璐，张 怡

(云南大学数学与统计学院,云南 昆明 650000)

1 引言

在服务行业中，为了获得更多利益，服务商通常根据客户的消费水平将客户分为不同的服务等级，例如普通客户和VIP客户。VIP客户往往比普通客户享受更多的服务，即普通客户能享受的服务，VIP客户都能享受，而某些特殊服务只有VIP客户才能享受，因此需要制定一些策略使得服务效率更高。例如在酒店行业，酒店需要提供免费接机服务，一般情况下普通客户只能享受包车服务，而VIP客户可以享受专车服务，也可以与普通客户一起享受包车服务。若将服务的车辆看作机器，客户的需求看作需要加工的工件，预先给每台机器和每个工件安排一个服务等级标号，这就是一类带服务等级的排序问题。

带服务等级约束的排序问题最早由Bar-Noy等人[1]提出，并针对任意等级和m台同型机，他们首次给出了一个竞争比为e+1≈3.718的在线算法，当所有工件加工时间相等时，由该算法可得到竞争比为e≈2.718。Hwang等人[2]则研究了任意等级和m台同型机的离线情形，给出了一个近似算法，在m=2和m≥3时，分别得到竞争比为5/4和2-1/(m-1)。周萍等人[3]则研究了在3台同型机上带服务等级(最多有3个等级)的离线情形。

对于机器带有约束(Eligibility Constraints)的在线情形,在有2台同型机和3台同型机时，Lim等人[11]分别证明了由AW算法可得最优竞争比2和5/2。在有m台同型机时，相关研究成果可见文献[11]。在有2台同型机时，Lee等人[12]给出了一个最优在线算法HSF。Hou等人[13]研究了m台同型机的情形。

现有……