本文提出并研究一些新型的排序问题，其模型是经典排序问题和现有的排序问题的推广。经典排序问题中，工件的加工时间是不变的，我们研究工件的加工时间依赖开工时间或者开工位置变化的模型；目前几乎没有研究在线与恶化效应结合的排序问题文献，我们提出相关模型并研究；经典的在线问题（over time模型）是指工件只有到达后才知道信息，也就是说要做决策必须要等到工件到达，我们研究的在线模型是提前一段时间就知道工件的信息。本文研究的工件信息到达时间是依时间（over time）的，分批模型是指平行批模型，即工件同一时刻最多加工B个工件，B为机器的容量，批的加工时间为该批工件中最大的加工时间。本文主要由四个部分组成。第一章，我们介绍排序问题和算法复杂性的一些基本知识，并对在线排序、分批排序、带恶化效应的排序的研究进行了综述。第二章研究加工时间是一般函数的排序问题，主要考虑了两类有一般加工时间函数的排序问题，工件的加工时间分别为基本加工时间与开工时间函数、位置函数的和。对于加工时间依赖开工时间的模型，证明一定条件下极小化最大完工时间和极小化总完工时间是多项式可解的。对于加工时间依赖开工位置的模型，给出极小化最大完工时间和总完工时间的最优序，同时证明了极小化加权总完工时间的一个最优排序性质并给出一个贪婪算法。第三章研究加工时间是具有线性恶化效应的在线排序问题，工件Jj的实际加工时间为Pj=bj+αt,其中bj为基本加工时间, α>0为恶化率, t是开工时间，目标为极小化最大完工时间。证明不分批的单机在线问题的下界至少为；对批容量无限的单机在线问题给出一个在线算法βH∞,并证明其竞争比和问题的下界相同,为（1+α）β+1，其中进而算法是最优的；对于批容量无限的同型机排序问题，给出在线算法并证明其竞争比为（1+α）βm+1，其中第四章研究工件具有提前预知信息的在线排序问题，从预知时间到工件可加工的时间之间间隔为a,还知道工件的最大加工是为pmax，目标为极小化最大完工时间，对于批容量无限的单机（在线问√题给出一个）在线算法γH∞,并证明其竞争比和问题的下界相同,为其中pmax+a/2，进而算法是最优的；对于（批容量无√限的同型机排）序问题，给出在线算法γmH∞并证明其竞争比为1+γm，其中最后，我们对本文研究的问题进行了总结和展望。