排序问题是一类重要的组合最优化问题,一直受到众多学者的重视,随着现代工业的发展,新的排序模型层出不穷,本文针对新模型,如模糊排序,恶化效应的批运送问题进行了探讨.论文共分为三章.第一章是本文的绪论部分,主要介绍了与排序问题相关的一些概念与基本知识.也介绍了模糊排序问题及具有线性恶化的排序问题的基本概念和相关知识.第二章主要考虑的是工件的加工时间和交货期均是区间数的单机模糊排序问题.我们给出了区间数的定义,区间数的可能度的定义以及重要性质;建立了相关的目标函数,讨论了三个不同模型的模糊排序问题,前两个问题可以用推广的Lawler算法多项式时间内求解,最后一个问题我们讨论了它的复杂性,证明该问题至少是NP-hard的.第三章主要研究了工件的加工时间是线性恶化的条件下,分批运送的单机排序问题.具体描述为: n个独立的、同时刻到达的工件在单台机器上加工,并成批运送到客户.工件的加工时间是关于其开工时间的简单线性增加函数,每一批的工件在这一批的最后一个工件完工的时刻运送给客户.问题的目标函数是最小化排序费用与运送费用之和,排序费用是指经典的排序目标,如总完工时间,最大延迟,总误工工件数等等,运送费用是指与运送的批数相关的增函数.本章考虑的排序问题是要确定工件在机器上的加工顺序,如何将工件分成若干批运送到客户以及运送的最优批数,从而使得总费用最小.对本章提出的几个问题,有些设计了有效的动态规划算法来求解,对于难解决的问题,给出了最优排序满足的性质.