排序理论已成为当今世界上发展研究最为活跃、应用最为广泛的学科领域之一.排序问题通常是指在一定的约束条件下，利用给定的资源最优地完成所指定的任务．一般地，我们用工件表示被加工的对象，即要执行的任务；用机器表示提供加工的对象，即完成任务所需要的资源．排序就是在一定的约束条件下对工件和机器按时间进行分配和安排次序，使得某一个或某些目标值达到最大或最小．　　 本文中我们主要研究恒同机上的平行工件在线排序问题.其中包括m台恒同机和一个含有n个相互独立平行工件的工件集｛J1，J2，…，Jn}．每一个工件Jj(j=1，2，…，n)有一个正整数的加工时间pj，称为该工件的长度；及其加工所需要占用的机器台数mj（1≤mj≤m），称为该工件的宽度．工件在线到达分为按序在线到达和按时在线到达两种．无论哪一种在线方式，工件的所有信息都是在它到达的那一时刻才知道．所谓平行工件(parallel jobs)是指工件要求在多台机器上同时加工，并且平行工件必须在这几台机器上同时开工同时完工．平行工件关于其加工时所需要的机器台数又分为可塑平行工件(malleable parallel jobs)和不可塑平行工件(nonmalleable parallel jobs)两种．可塑平行工件所使用的机器台数可以根据需要决定，而不可塑平行工件所使用的机器台数（即它的宽度）是固定不变的．工件按照其加工特点又可分为不允许中断抢先工件(nonpreemptive jobs)和允许中断抢先工件(preemptive jobs).不允许中断抢先工件一旦开始加工就必须持续到其加工完为止，而允许中断抢先工件可以选择在其加工过程中的某一时刻停止，未加工完的部分留在以后的某个时刻再重新安排加工．本文中所研究的模型的目标函数都是最小化最大完工时间(makespan).　　 在第二章中，我们主要研究了恒同机上可塑平行工件的按时在线排序问题．其中工件都是相互独立的且不允许中断抢先.工件Jj被安排在kj台恒同机上加工时的实际加工时间定义为tj=pj/kj+(kj- l)cj，其中cj(cj＞0)为工件Jj的安装时间参数．对于两台恒同机的模型我们给出一个竞争比为1+α的在线算法．其中，α=(√5－1)/2是方程α2+α=1的一个正数解．另外，我们证明了对任意m(m≥2)台恒同机的模型都不存在竞争比小于l+α的在线算法．因此我们给出的算法对于两台恒同机模型来说是最优的．　　 在第三章中，我们主要研究了恒同机上不可塑平行工件的按时在线排序问题，其中工件是允许中断抢先的．每一个平行工件Jj除了有一个正的到达时间(arrivaltime) aj(aj〉0)和一个正的长度(length) pj(pj＞0)外，还有一个正的宽度(width) mj，其中1≤mj≤m．对于两台恒同机上不可塑平行工件只强调使用机器台数的按时在线排序问题和m台恒同机上不可塑平行工件只强调使用机器台数且工件宽度只有两种（1或m）的按时在线排序问题，我们都利用“临时排序”的思想构造了竞争比为1的最优在线算法．对于m台恒同机上不可塑平行工件可选择机器集合固定的模型，我们给出了两台恒同机在线排序模型一个竞争比为1的最优在线算法，并且证明了三台恒同机的在线排序模型不存在竞争比小于5/4的在线算法．　　 在第四章中，我们主要研究了机器带有时间窗的恒同机上不可塑平行工件在线排序问题．根据机器时间窗的改变时刻是否事先已知模型可分为时间窗已知和时间窗未知两种.对于时间窗未知的情形，时间窗的改变时间也只有在它改变的那一时刻才知道．按照工件在线到达的方式不同我们分别讨论了按序在线(over list)和按时在线(over time)两种在线排序模型.模型中的工件都是允许中断抢先的．我们证明了机器带有时间窗的两台恒同机上不可塑平行工件按序到达的在线排序模型不存在竞争比为常数的在线算法．而对于机器带有时间窗的两台恒同机上不可塑平行工件按时到达且工件可选择机器集合固定的模型我们给出了一个竞争比为1的最优在线算法．另外，关于机器带有时间窗的两台恒同机上不可塑平行工件只确定宽度的按时在线排序问题，对于机器时间窗是已知的模型我们给出了一个竞争比为1的最优在线算法；对于机器时间窗是未知的模型我们给出了一个竞争比为1+(?)(ε→0)的近似最优在线算法．