具有指定到达时间的平行机在线排序问题研究

摘要

本文以现代服务业中的预定系统为实际背景，将具有最迟完工时间的平行机在线排序问题拓展，研究了一类具有指定到达时间和最迟完工时间的在线排序问题(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组数据进行测试，分别统计它们的平均值和方差。 本文的研究成果在现代服务行业中具有具有广泛地应用前景，它可以应用在服务业的预定系统中来提高设备的利用率，最大限度地满足客户的需求，例如，可以在航空货运码头采用这种系统分配有限的站台，提高站台的利用率。

目录

声明

摘要

1导论

1.1前言

1.2本文研究的问题以及背景

2在线排序问题文献综述

2.1经典在线排序问题

2.2平行机在线排序问题

2.3具有最迟完工时间的平行机在线排序问题(Pm｜ pj，rj，dj ｜∑(U))

3具有指定到达时间(Arbitrary Release Time)和最迟完工时间(Deadline)的平行机在线排序问题(Pm｜ pj，Arbitraryrj，dj｜∑(U))

3.1两台平行机的P2 ｜ pj=1，Arbitraryrj，dj ｜∑(U)问题下界分析

3.2在线算法及性质分析

3.2.1在线算法Ⅰ及相关的分析

3.2.2在线算法Ⅱ的基本思想和主要步骤

3.2.3在线算法Ⅱ的结果分析

3.2.4在线算法Ⅲ的基本思想和主要步骤

3.2.5在线算法Ⅲ的结果分析

4P2｜ pj=1，Arbitraryrj，dj｜∑(U)问题的最优化模型和计算实例

4.1混合整数规划模型：

4.2计算实例

4.2.1测试数据的生成

4.2.2计算结果

5总结与展望

5.1本文的研究成果与结论

5.2有待进一步研究的问题

参考文献

致谢

附录