排序问题是一类重要的组合最优化问题.在经典排序问题中通常假设任务的加工时间为常数,但在许多实际问题中,常出现任务加工时间随其开始加工时间推后而增长的现象.本文结合实际应用背景,突破经典排序中任务加工时间为常数的限制,研究任务加工时间线性恶化的机器排序问题.这类模型比相应的经典排序问题更复杂,绝大多数是NP难问题.本文主要在如下几个方面作了一些工作:1.最小化加权总完工时间的单机排序问题.在任务加工时间简单线形恶化下,根据平行链约束中关键任务优先规则,本文对任务间具有树约束的排序问题,提出了最大家庭树优先规则,进而给出了复杂性为O ( n2)的最优算法.当任务间具有一般约束时,给出了该问题的一些性质,并构造了近似算法.2.最小化完工时间的平行机排序问题.通过子乘积问题,本文证明了问题P 2 | p j =αj Sj| C max的NP困难性.在简单线形恶化下,本文把对同速机的研究推广到恒速机的情况,对恒速机排序问题Qm |pj =αjSj|Cmax,给出了复杂性分别为O (n)和O ( n2)的两种启发式算法,并分析了这两种算法的绝对性能比.3.最小化完工时间的流水作业排序问题.在作业加工时间简单线形恶化下,为了构造满足约束条件的复合作业,本文提出了作业的非负开始和停止延迟恶化率,给出作业间具有平行链约束和串并有向图约束的两台处理机流水作业排序问题的最优多项式算法;对NP难问题F 2| pi j= X ij+αijSij| C max,通过定义处理机间的优势关系,得到处理机在满足优势关系下,线形恶化最小化完工时间的流水作业排序问题Fm | pi j= X ij+αij S ij|Cmax的多项式算法.