本文主要完成了两方面的工作。1．平行批在线排序算法的研究。在过去的四十年里，生产系统的调度计划研究得到了显著的成果，从而产生了一个专门的学科—排序。在诸多的排序成果中，所研究的模型很多是确定性的。在这类模型里，主要的假设就是输入的实例的所有参数均是事先已知并且不会再发生变化的。但是，实际中的生产环境受很多不确定因素的影响，输入的实例的参数并不是全部事先确定，而是在排序的过程中逐一知道的。近年来，针对这一类型排序模型的研究逐渐发展出“在线排序”这一学科分支。本文着重讨论在线环境中的若干平行批排序问题。此时，在线环境是指输入的实例中，只有当工件到达时才知道它相应的信息（如：加工时间、到达时间等）。平行批排序模型来源于半导体制造中对集成电路芯片煅烧的工序排序问题。在这类模型里，每个工件都有一个加工时间，机器可以同时加工b个工件，每一批的加工时间等于该批次里所有工件中加工时间最长的加工时间。1．1单机、平行批、分组工件的在线排序问题。在这个模型里，待加工的工件分为多个不兼容的组，不同组中的工件不能放在同一批中加工。对批容量无界的情形，我们给出了使得完工时间尽量小的竞争比是2的在线算法，并证明该算法的性能已最具竞争性；对批容量有界的情形，针对同一目标函数，我们给出了竞争比也是2的在线算法，并证明当批容量不小于100时，性能最好的算法竞争比大于1.9802，非常接近于2。1．2单机、平行批、批容量无界、优化最大完工时间的在线排序问题。对该排序问题，Zhang等人（G．Zhang，X．Cai and C．K．Wong，On-line algorithms for minimiz-ing makespan on batch processing machines，Naval Research Logistics，48（2001），241-258．）和Deng等人（X．Deng，C．K．Poon and Y．Zhang，Approximation algorithms in batching processing，Jour-nal of Combinational Optimization，7（2003），247-257．）两组作者分别独立地给出了同一个竞争比为(5^1／2+1)／2的在线算法，并证明不存在竞争比更小的在线算法。但是，他们的算法不是弱渐进最优的（这里称一个算法是弱渐进最优的，如果工件的最长加工时间与最优值的比值趋于0时，由算法得到的可行排序的目标函数值与最优值的比值趋于1），我们设计了一个算法，在保证其竞争比不大于(5^1／2+1)／2的情况下，使得它是弱渐进最优的。1．3单机、平行批、带序约束且加工时间均为1的工件在线排序问题。考虑批容量有界、且工件序约束图的各个分支都是链的模型，以优化最大完工时间为目标，我们给出了竞争比为3^1／2的在线算法，并说明，当b≥3时，所有具有稠密特征（只要当前机器处于闲置状态，并且至少有b个独立工件（即相互之间没有序约束的工件）待加工，则立刻开始一批工件的加工）的在线算法的竞争比至少是3^1／2。考虑工件序约束任意的情形，对于批容量无界的情形，以优化最大加权完工时间或优化加权完工时间和为目标，我们均得到竞争比为5^1／2+1／2的最优在线算法；对于批容量有界的情形，以优化最大完工时间为目标，我们给出了竞争比是2的在线算法。2．边赋权环网络路由负载问题。在现代通讯中，光纤的应用大大地提高了传输的速度，并使网络传输的数据类型多样化。为了提高光纤的利用率，网络的路由选择问题是当前研究的热点。网络有各种各样的拓扑结构，其中环是常见的一种。环上分布有若干个点，相邻的点间有边相连，点与点之间有相互传递信息的请求。信息传递的途径只有两种可能：沿着顺时针或逆时针方向。对于每一条边，它的负载是指传递时经过它的信息量的总和。要考虑的问题是：如何传递信息，使得最终负载最大的边的负载达到最小。Schrijver等人在他们的文章（A．Schrijver，P．D．Seymour，and P．Winkler，The ringloading problem，SIAM J．Discrete Math．，11（1998），1-14．）中做了以下工作：（1）证明信息请求可任意分割传递时，问题是多项式时间可解的；（2）证明信息请求不可分割传递时，问题是NP-困难的，并给出了近似算法；该算法所求出的可行解的目标函数值不超过最优值的3d_max／2，其中d_max是环中点对间要传递的最大信息量。在本文所讨论的拓扑结构一环中，每一条边都有一个非负权重，每一条边的加权负载等于它的权重与其负载的上整数的乘积。我们要考虑的问题是：如何传递信息，使得最终加权负载最大的边的加权负载达到最小。我们得到如下结果：（1）证明信息请求可任意分割传递时，问题是多项式时间可解的；（2）证明信息请求可整分割传递时，问题是多项式时间可解的；（3）对于信息请求不可分割传递的情形（问题是NP-困难的），给出了多项式时间逼近方案（PTAS）。