重新排序问题是一种新型的排序模型,它有着重要的实际应用背景。 生产部门根据自己的生产计划或是由客户提出的要求,在生产前一定时期内事先有一个作业方案,将已有的任务或订单按照某一规则安排好,使某一目标值最优。但是在即将开始生产之前或在生产过程中又有新的客户订单或任务到达。 这时就要把新的任务和原有的还未加工的任务一起加工。 为了不失信于对原客户的承诺或不耽误原任务的完成,这就要求在原有的工件或任务的次序不至于打乱得过多的前提下,使得总的目标函数值达到最优。 本文考虑学习效应作用下的最小化总完工时间的重新排序问题,其中工件的加工时间是其所在序列加工位置有关的函数。 对于最大序列错位、总序列错位和最大时间错位下的最小化总完工时间问题均给出了多项式时间算法,对于总时间错位下的最小化总完工时间问题提出了动态规划算法,并证明这个算法是拟多项式时间的。