本文主要研究了一些具有多项式时间算法排序问题的稳定性和加工时间可变的排序问题，其主要内容为： 一、分析了单机和流水作业中一些具有多项式时间算法排序问题的稳定性，即当一些关键参数(加工时间，准备时间)发生变化时最优序是否保持不变? 二、在经典的排序问题中，通常假设工件的加工时间是固定不变的常数，然而在许多实际问题中，工件的加工时间可能与工件的开工时间或位置有着某种联系，由此产生一些新的排序问题，这些新排序问题比经典的排序问题更为复杂，绝大数问题为NP困难的。本文研究了一些具有学习效应、退化效应的排序问题，它们有： (1)在Kuo和Yang提出的一类新的学习效应模型的基础上，本文分析了单机和流水作业中一些特殊条件下具有多项式时间算法的排序问题。同时也研究了a>0的退化效应的模型。 (2)相应工件的加工时间受到此工件前所有工件加工时间之和影响的指数型学习效应，对单机中最小化时间表长和总完工时间之和问题以及单机成组加工中最小化时间表长和总完工时间之和问题，本文给出了最优算法。