排序问题是指在一定约束限制条件下,对工件、机器按时间进行分配和安排他们的加工次序,要求使得一个或者多个目标函数值达到最优,而单机重新排序问题是既复杂又重要的排序问题之一。重新排序模型是指一批原始工件在某时刻已经按照某种目标排好序,使得某一目标函数值达到最优,但是在将要开始加工之前或在整个加工过程中又有一批新的工件来到,就需要将新到达的工件和原来还未加工的工件一起加工,这就要求在原有工件次序不至于打乱太多的前提下使得总目标函数值达到最优。Hall和Potts[1]系统的研究了重新排序问题,并给出了时间错位和序列错位的概念,考虑了在原来最优排序和现在任意排序的基础上进行的重新排序问题,使得在错位不至于太大的前提下目标函数值达到最优。第二章针对关于工件具有退化效应和学习效应的重新排序问题,分别考虑了在错位限制下工件具有学习效应的最小化最大完工时间的重新排序问题,并给出了其计算复杂性;当错位限制下的具有退化效应的最小化总完工时间的重新排序问题,并给出了它的计算复杂性。第三章针对关于加工时间不变或加工时间相同或工期相同的重新排序问题,考虑了加工时间不变且时间错位与序列错位呈凸组合关系的重新排序问题;具有相同加工时间或相同工期的最大误工问题,并给出了其计算复杂性。