本文主要研究来源于通讯网络的排序(scheduling)问题。我们首先研究的是并行工件(paralleljobs)的排序，每个并行工件可能需要一台或多台机器同时加工这个工件。我们考虑机器之间存在的各种网络拓扑结构对排序结果的影响。具体的网络拓扑结构可以是：完全图结构(PRAM)，线(Line)，网格(Mesh)，超立方体(Hypercube)等等。若干机器可以同时加工一个工件仅当这些机器构成的生成子网络是连通的。也就是说，仅当机器间存在通讯路径时才能够共同工作，而且这些机器必须满足工件所要求的数目和拓扑结构。除了机器之间具有网络拓扑结构之外，我们对工件的各种不同的在线到达模式进行分类和研究，如工件按先后序到达(ondependencies)，工件按释放时间到达(overtime)，工件按列表逐个到达(overlist)。我们的目标是对给定的工件集合进行排序以满足各种约束条件并使某种目标值最优化。常见的目标函数有极小化最大完工时间(minimizethemakespan)或者是最大化输出量(maximizethethroughput)。 我们对这些排序问题提出了相应的在线算法，并采用国际上通用的算法评价标准竞争比(competitiveratio)来衡量、分析给出的算法。通过研究“坏的”实例，我们给出各种问题的下界(lowerbound)。从各种模型的分析来看，不同的网络拓扑结构和工件的不同在线到达模式均对最后的排序结果产生重要的影响。本文对每个具体问题如何设计有效算法进行了深入的研究，从而达到对已有算法的重要改进和对新问题提出高性能的算法。同时我们还研究，事先获得工件的部分信息对算法的影响。对于并行工件的排序问题，我们还研究了几个离线模型，即工件的所有信息都已知。我们或者证明该问题是多项式可解的或者是对NP难问题给出多项式时间近似方案。 我们还研究一些经典排序问题，这里每个工件只需要一台机器来加工。我们首先考虑的是机器总加工时间可扩展的排序问题(schedulingwithextendableworkingtimeproblem)。每台机器有一个初始设定的正规加工时间，但机器的总加工时间可以根据需要决定是否延长。每台机器的工作时间定义为正规加工时间和总加工时间(真正加工时间)之间的较大值。我们的目标是安排所有的工件，使得所有机器工作时间的总和最小。我们分别对所有的机器都有相同的正规加工时间，和每个机器的正规加工时间可以不相同的情况进行深入的研究。 最后，我们讨论经典排序问题中，事先获得工件的部分信息的半在线模型。我们已知最后加工的工件的加工时间最长，并且当最后一个工件到达的时候，将被通知这就是最后一个工件。我们分别对小数目的平行机和同类机进行了探讨。 全文共分九章。第一章介绍本文研究的问题、模型及其应用背景，以及问题之间的分类，并简要介绍本文的工作。一些基本概念，基础知识和分析问题的工具也在本章中介绍。第九章总结本文详细的成果以及对未来研究方向的展望。其余七章分成两部分。第一部分由二到六章构成，主要研究并行工件的排序问题。第二部分由第七、第八章组成，探讨一些与经典排序相关的问题。具体说明如下： 第二章详细综述并行工件在线排序的历史文献以及相关问题的研究结果。 第三章研究的问题是：在线带先后序约束(ondependencies)的并行工件在二维网格上的排序问题。所有工件的加工时间为单位时间，每个并行工件需要一组在二维子网格上的机器同时加工。工件之间存在先后序约束。一个并行工件到达并可以开始加工当且仅当这个工件的所有前序工件都已经完工。但是，工件之间的这种序的关系事先不知道。这意味着，不同策略的安排将可能导致不同的工件到达顺序。我们研究的目标是极小化最大完工时间。我们设计了一个有效的在线算法，其竞争比不超过5.25。同时我们也证明了，任何在线算法的竞争比都不可能小于3.859。这个结果改进了原有的下界3.25和上界46/7。另外，当并行工件可以旋转90度的情况。我们证明了这个问题的上界最多为4.25，同时也证明了，不存在在线算法其竞争比小于3.535。 第四章讨论并行工件列表在线(overlist)的排序问题。并行工件的到达顺序已事先安排好在一个列表中。但是，安排者并不知道这个已经安排好的顺序，也不知道到底有多少个工件。当且仅当当前工件已经安排好下一个工件才到达(如果有的话)。工件一旦安排好之后，就不允许改动。本章讨论的问题基于机器的网络结构是完全图结构，也就是可以忽略网络的拓扑结构，而只需要满足相应的机器数即可。这个问题的目标仍然是极小化最大完工时间。我们给出了一个竞争比为7的算法，极大的改进了原先的竞争比为12的算法。我们进一步研究三种特殊情况：工件按加工时间非升的顺序到达；工件按工件的尺寸(所需的机器数)非升的顺序到达；工件的最大加工时间事先已知。对第一种情况，我们对贪婪算法进行了分析并证明其上界最多为2。对第二种情况，我们也对贪婪算法进行了分析并证明这个算法的竞争比在2.75与2.5之间。对最后一种情况，贪婪算法就不再有效，我们给出了一个算法其紧界为4。最后，我们研究工件在加工当中允许中断，当每个工件到达的时候，我们要决定何时开始加工该工件，是否对这个工件中断以及每次中断的时刻，安排好之后也就不再允许修改。据我们所知，这是第一个研究可中断并行工件列表在线排序问题的工作。我们给出了一个竞争比为2-1/m的在线算法。 第五章研究可延展的并行工件(malleableparalleljob)排序问题。每个工件的加工时间是所使用机器数的函数。每个工件加工所需的机器数事先并不固定，但在安排的时候必须确定，而且一旦确定了，就不能再更改。机器之间的网络拓扑结构为二维网格。我们考虑并行工件在满足单调性(monotonic)的情况下的排序。这里单调性指的是一个工件的加工时间在机器数目减少的情况下，其加工时间不会变短，而它的功(指的是机器数乘加工时间)不会增加。我们的目标是极小化最大完工时间。对这个问题，当机器数目为充分大的时候我们给出一个渐近完全多项式方案(AFPTAS)。也就是，对于任意给定的一个小量ε，我们给出的算法都能在多项式时间内保证算法所得的解不超过最优解的1+ε倍(加上一个常数)。 第六章我们研究问题的目标是极大化输出量(throughput)，即极大化完工工件的个数。首先我们讨论的是在超立方体上的排序问题，每个并行工件均需一个子超立方体来同时加工。并行工件释放时间(releasetime)相同，但是有各自的交工期(duedate)。容易证明这个问题是NP难的。因此，我们讨论了单位加工时间的情况。证明该问题是P问题。我们进一步讨论一个公开问题，即并行工件在两台机上的排序问题，工件有各自的释放时间，同时每个工件的加工时间为单位时间，其目标仍是极大化输出量。我们证明了该问题也是P问题。 第七章讨论机器加工时间可扩展的排序问题。给定m台机器以及每台机器的正规加工时间b1，b2，…，bm。机器的总加工时间可以根据需要决定是否延长。每台机器的工作时间定义为正规加工时间和总加工时间(即安排在该机器上的所有工件的加工时间之和)之间的较大值。工件是按列表在线到达的。目标是安排所有的工件在给定的机器上，使得所有机器工作时间的总和最小。对于所有机器的正规加工时间相同情况，我们研究了机器数目较少的的情况，详细深入的分析已有算法并证明其算法具体的竞争比。对于两台机器，我们给出了竞争比为7/6的最优在线算法。对于三台机器，我们给出了问题的下界(17+√577)/36和上界7/6。对于四台机器，我们给出了下界9/8，并证明其上界不超过19/16。接着，我们对机器的正规加工时间不同的情况进行了研究。假设最小的正规加工时间不小于最大的工件加工时间。对任意的m台机器，我们对贪婪算法进行详细的分析，并完全刻划了其紧界与机器数m之间的关系。然后，我们对两和三台机器的情况，给出了改进的算法以及问题的下界。在没有上述假设的情况下，我们对两台机器进行了研究。最后，我们对加工工件是并行工件而且是离线的情况进行了研究，提出了一个算法并证明其紧界是2。 第八章我们研究经典排序问题中的半在线模型。工件是按列表在线。同时我们已知最后加工的工件的加工时间最长，并且当最后一个工件到达的时候，将被通知这就是最后一个工件。我们分别对小数目的同型机和同类机进行了探讨。目标是极小化最大完工时间。对两台和三台同型机，我们给出了最优的在线算法，其竞争比分别为√2和3/2。接着，我们研究了两台同类机问题，对每个工件一台机器的加工速度为1，另一台的加工速度为1/s，我们分别就不同的速率s给出竞争比分析，并证明了对于大部分s，所给的算法都是最优的列表半在线算法。最后，我们对这个问题的另外一个目标函数：极大化最小完工时间进行了讨论。证明了绝大多数情况下，对于给定的s，我们所给的算法是最优的。