郭 晓, 冯密罗, 慕运动

(1.河南工业大学 理学院 河南 郑州 450001； 2.郑州大学 数学系 河南 郑州 450001)

0 引言

工件错位即在原始排序中产生的错位限制下，最小化最大延误时间和总完工时间的单机重新排序问题[1]．Potts等[2-4]考虑了在单机情况下，分批排序的排序方法以及分批排序问题不同情况下的不同算法． Agnetis等[5]主要考虑的是具有两个代理和两个目标函数的最小化加权总完工时间等问题．Baker等[6]考虑了多准则模型的机器排序问题，且给出了多代理目标函数的线性组合时的结果．Yuan等[7-8]考虑了具有到达时间的最大序列或时间错位限制下的最小化最大完工时间的重新排序问题．根据Hall等[1]的描述，单机重新排序问题可表示为：令J0={J1,J2,…,Jn0}为单机上的原始工件集．在模型中，假定J0中的工件已经在最小化某一经典目标函数下最优地安排加工，且π*是一个最优序．令JN={Jn0+1,Jn0+2,…,Jn0+nN}为新工件集,记J=J0∪JN,J中的每一个工件Jj的加工时间为整数且满足pj≥0,π*和σ*分别表示J0和J工件的最优序．对于J的工件的任意排序σ，定义2个变量：Cj(σ)表示J中工件Jj在σ中的完工时间;Δj(π*,σ)=|Cj(σ)-Cj(π*)|表示J0中工件Jj的时间错位．在不引起混淆的前提下，上面的参数可以分别简化为Cj,Δj(π*)．需要说明的是，在继列分批排序中，由于同一批的工件的完工时间相同，因此,在同一批中工件没有先后次序之分．

在研究问题的过程中，主要考虑两个方面：第一，研究分批重新排序问题的可行排序和最优排序的结构性质；第二，基于这些性质设计问题的最优算法．本文证明了……