本文以现代服务业中的预定系统为实际背景，将具有最迟完工时间的平行机在线排序问题拓展，研究了一类具有指定到达时间和最迟完工时间的在线排序问题(Pm|P<,j>,Arbitraryr<,j>，d<,j>|∑U)，并且证明了该问题是NP-Hard问题。由于该问题是NP-Hard问题，所以在大规模的情况下，使用有限的资源在合理的时间内计算出最优解是非常困难的事情。因此，本文将重点放在启发式在线算法的设计和其性质的证明上面，最后，本文采用计算机模拟的方法，对启发式在线算法的效率进行了模拟。本文的主要贡献如下： 1．针对P2 | p，=1，Arbitraryr<,j>，d<,j>l∑U问题，证明了该问题的下界为2。 2．在线算法Ⅰ的提出和性质的证明。本文在经典LS算法的基础上提出第一个启发式在线算法，并且对其性质做了分析。 3．在线算法Ⅱ的提出和性质的证明。为了能够有效地为未来到达系统的工作预留空间，在在线算法Ⅰ的基础上，将两台机器分别赋予不同的优先级，提出了在线算法Ⅱ，并且分析了它的性质。 4．在线算法Ⅲ的提出和性质的证明。为了能够更为有效地为未来到达系统的工作预留空间，在在线算法Ⅱ的基础上，提出了在线算法Ⅲ，并且证明其竞争比为2二。 5．提出具有0-1约束的混合整数规划模型。 6．在线算法Ⅲ的平均境况分析。采用计算模拟的方法，使用VBA工具，按照工作个数将该问题分成四类，每一类用100组数据进行测试，分别统计它们的平均值和方差。 本文的研究成果在现代服务行业中具有具有广泛地应用前景，它可以应用在服务业的预定系统中来提高设备的利用率，最大限度地满足客户的需求，例如，可以在航空货运码头采用这种系统分配有限的站台，提高站台的利用率。