1. 研究目的与意义、国内外研究现状（文献综述）
排序问题的背景排序问题是一类重要的组合优化问题。
排序论的研究是运筹学研究的一个非常活跃的分支。
排序问题产生于机器制造业并且广泛地存在于社会生活的各个方面，比如日常生活中,市民在乘坐公共交通工具（公交、地铁等）上下班、到医院看病等，如何能够节省时间高效有序的问题；再比如更具体一点儿的，在2008年春运期间，突如其来的大雪致使数十万旅客滞留火车站，铁路部门如何疏导和安置滞留人员的问题等，这些都是排序问题。
2. 研究的基本内容和问题
本文研究具有服务等级的三台平行机在线排序问题，主要研究以下两类问题：(1) 具有两个服务等级的三台平行机在线排序问题，目标为最小化最大完工时间。
其中，机器和工件都有两个服务等级，工件列表在线到达且工件的加工不允许中断。
对于该问题，研究以下两种情形： （1.1）机器m1的服务等级为1，机器m2和m3的服务等级为2； （1.2）机器m1和m2的服务等级为1，机器m3的服务等级为2。
3. 研究的方法与方案
在线排序问题中，除了个别目标函数以外通常不存在最优算法。
因此，求解在线排序问题通常用近似算法（被称为在线算法）。
衡量一个在线排序算法最常用的指标就是它的竞争度（competitiveness），即把在线排序算法的结果与对相同工件运用离线排序算法得到的结果进行比较，更确切地说，我们用竞争比（competitive ratio）p来衡量一个在线算法的性能。
4. 研究创新点
对于具有三个服务等级的三台平行机在线排序,目标为最小化最大完工时间问题，已知结果是：下界9/5，上界11/5。
本课题意在用对手法找出更大的下界，并设计出在线算法找出更小的上界，并给出竞争比分析。
5. 研究计划与进展
2015年10月初至11月上旬：较为深入的理解所要研究的课题背景、基础知识，通过对手法的试验找出具有三个服务等级的三台平行机在线排序,目标为最小化最大完工时间问题中比9/5大的下界。
2015年11月下旬至12月末：（1）针对具有三个服务等级的三台平行机在线排序,目标为最小化最大完工时间问题，研究在线算法的相关文献，理解原文的基础上，利用其原理推导出问题的已知上界11/5的推导方法。
（2） 针对具有两个服务等级的三台平行机在线排序,目标为最小化最大完工时间问题，用对手法找出其下界。
