排序问题是组合优化问题的一类重要分支，这一问题最早起源于机器制造业，现在已普遍应用于运筹学，经济管理科学、系统控制和计算机科学等多个学科。在经典排序问题当中，一般假设工件的加工时间为常数，但在很多实际问题中，工件的实际加工时间可能与其所在位置，开工时间，所分配的资源等多种因素有着各种联系，使得工件的加工时间不再是固定常数。本文主要研究工件的实际加工时间与位置相关的单机排序问题，主要结果如下：　　1、带有线性位置恶化及维修区间的单机排序问题　　(1)工件的实际加工时间与其所在的位置线性相关，且位置具有恶化效应，维修区间长度与其前一组工件的完工时间和成线性关系，目标函数是最小化最大完工时间和最小化总完工时间问题，在最大完工时间问题模型中，证明了工件序列满足组平衡原则，并给出了相关结论与算法。　　(2)对于总完工时间问题，可以转化为线性指派问题进行求解，证明该问题也是多项式时间可解的，其算法的时间复杂度为O(nfcl0+3)。　　2、带有位置效应和到达时间的单机组排序问题　　(1)在工件独立，组相关的情形下，工件具有到达时间，且其实际加工时间是工件加工位置的函数，组准备时间与前一组完工时间线性相关。在开始加工之前，工件的分组已经确定，考虑工件的最大完工时间问题，确定了组内工件和组与组之间的最优排列顺序，并给出相应定理及算法。　　(2)在组准备时间为常数的特殊情况下证明工件的最大完工时间问题是多项式可解的，并给出相关结论。　　3、具有对数学习效应且与已加工序列相关的单机排序问题　　(1)工件具有学习效应，其实际加工时间与已加工工件对数相关，也与其所在位置相关，并且工件具有准备时间，其准备时间与已加工工件的完工时间和线性相关，考虑工件的最大完工时间，完工时间和问题，并证明了最大完工时间，完工时间和等问题是多项式可解的。　　(2)在一定条件下证明了总权重完工时间和最大延迟等问题仍为多项式可解的。