排序问题作为一类在管理科学、计算科学和控制科学等领域有着广泛应用的问题,近年来受到了广泛的关注。本文基于依赖于工件加工位置的学习效应,研究了单机和平行机环境下的三个排序问题:最小化时间表长的两台平行机问题,最小化加权完工时间和的单机排序问题以及最小化最大延迟的单机排序问题。这三个问题均为NP-hard问题。对于平行机上带学习效应的时间表长问题,本文首先建立了求解该问题最优解的整数规划模型,其次,基于模拟退火算法给出了该问题的近似算法SA,并证明了该算法依概率1全局收敛到最优解,并通过数值模拟对所提出的算法进行了性能分析。数值模拟结果表明,本文提出的近似算法SA可以达到最优值的99%,准确度高,算法较有效。对于单机环境下带学习效应的最小化加权完工时间和问题,本文讨论了它的三种特殊情形:P_j=P,w_j=w以及w_j =kP_j,说明了在这三种特殊情况下,问题均为多项式时间可解的,分别给出了问题的算法并证明了算法的最优性。我们还研究了单机环境下带学习效应的最小化最大延迟问题,讨论了问题的三种特殊情形:P_j=P,d_j= d以及d_j= kP_j,说明了在这三种特殊情况下,问题均为多项式时间可解的,分别给出了问题的算法并证明了算法的最优性。