本文主要从讨论问题下界和设计算法的角度,对排序问题中的在线和半在线流水作业以及单机问题进行了研究。我们首先考虑了工件带到达时间(over time)和工件逐个到达(over list),目标为最小化最大完工时间的在线和半在线流水作业问题。然后分别考虑了机器有使用限制的单机和流水作业问题。全文由六个部分组成,在第一章我们首先给出了组合优化和排序问题的基本概念和定义,然后介绍在线和半在线排序的研究近况,最后给出机器有使用限制的排序问题的一些概念和研究现状。第二章研究了可中断的二台机器流水作业排序问题,目标为最小化最大完工时间,工件实时到达(over time),工件信息在工件到达之前不可知。我们首次给出了该在线问题的一个下界1.137,并对问题设计了一个在线算法。针对只有两个到达时间的特殊情况,我们证明了该在线算法是3/2竞争的算法。第三章主要讨论了两台机器流水作业的半在线排序问题。我们分别研究了不可中断和可中断两种情况。对于不可中断的排序模型,我们研究了已知工件工序最大及最小加工时间,工序的总加工时间以及最优值的半在线情形,分别对这些问题给出了问题的下界,并为已知最优值的半在线问题设计了一个竞争比为3/2的在线算法。而对于可中断的情况,我们也分别对上述的半在线情形进行了分析,同样给出了问题的下界,同时对已知第一道工序加工时间和以及已知最优值的问题分别给出了竞争比为3/2的在线算法。第四章研究的是机器带使用限制的两台机器流水作业问题,工件加工可以被不可用时间段中断,目标为最小化最大完工时间。我们知道若第二台机器上存在有多个不可用时间段,问题不存在常数性能比的近似算法。利用Kubzin等人的算法思想,对于两台机器上均存在多个不可用时间段问题的可近似情况,我们得到了一个性能比为3/2的近似算法。第五章主要研究了机器有使用限制的半在线流水作业排序问题,其中工件是逐个到达的(over list),目标为最小化最大完工时间。对于第一台机器上存在不可用时间段的情形,我们讨论了一类新的半在线模型,即已知第一道工序的最大加工时间amax与不可用时间段的开始时间s之间关系的半在线问题。我们分别证明了三种不同的情况：amax>s,amax<s,或amax＝s,问题的下界均为2,同时证明LS算法即为一个最优的半在线算法。我们还证明了若在第二台机器上存在不可用时间段,问题不存在常数竞争比的在线算法。在本章的最后,我们讨论了第二台机器上存在不可用时间段的已知最优值Cmax*的半在线问题,并对不可用时间段的结束时间t不超过1/2Cmax*的特殊情况给出了一个竞争比为3/2的在线算法。第六章主要研究了机器有使用限制的单机在线和半在线问题,工件是逐个到达的,目标为最小化最大完工时间。我们考虑的是工件被不可用时间段中断后要重新再加工的情形(non-resumable),机器只有一个不可用时间段。对于该模型的在线问题,证明了问题的下界是2,且LS算法即为该问题的最优算法。对于半在线问题,我们考虑的是已知工件最大加工时间的半在线模型。通过比较最大加工时间pmax与不可用时间段的开始时间s的大小关系,分别考虑了pmax>s,Pmax<s,和pmax=s的情况。证明了前两种情况的下界分别为(?)和3/2,并且若pmax=s,问题是可解的。我们对pmax>s的情况给出了一个竞争比为(?)的最优半在线算法,对于pmax<s的情况也给出了一个竞争比为3/2的最优半在线算法。最后我们还证明了,若单机上存在有多个不可用时间段,在线问题不存在常数竞争比的在线算法。