慕运动， 皮军德， 郭 晓

（河南工业大学理学院，郑州 450001）

序列错位限制下最小化完工时间和的继列分批重新排序

慕运动， 皮军德， 郭 晓

（河南工业大学理学院，郑州 450001）

在单机分批排序中，一个原始工件集已经分好批排好顺序，使得给定的目标函数最小.当一个新的工件集到来时，决策者需要插入这些新工件到原来的顺序中，这样使得原始工件就会产生一些错位.但为了满足对原始工件集的要求而不过分的打乱它们的顺序的条件下，使得新的目标值为最优.本文主要研究的是在序列错位量限制的条件下，继列分批最小化总完工时间的重新排序问题，对于最大序列错位和总序列错位的不同约束情况下，研究可行排序和最优排序的结构性质，进而设计了它们的多项式时间算法.

重新排序；单机；分批；分批排序；序列错位

1 引言和问题阐述

在本文中，我们研究单机分批排序中的继列分批，即s分批重新排序问题.所谓s分批是指在同一批的工件，具有相同的开工时间和完工时间，其加工时间等于全部工件的加工时间之和.假设原始工件已经按照总完工时间最优地排列，新工件在零时刻都已经到达，当新工件安排加工时，我们必须要考虑原始工件的错位问题，使得在时间错位约束下，继列分批的继列分批最小化总完工时间的重新排序问题.Hall和Potts［5］在前人研究的基础上首先引入了工件错位的概念，考虑了在对从原始排序中产生的错……