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

慕运动， 皮军德， 郭 晓

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

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

慕运动， 皮军德， 郭 晓

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

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

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

1 引言和问题阐述

在本文中，我们研究单机分批排序中的继列分批，即s分批重新排序问题.所谓s分批是指在同一批的工件，具有相同的开工时间和完工时间，其加工时间等于全部工件的加工时间之和.假设原始工件已经按照总完工时间最优地排列，新工件在零时刻都已经到达，当新工件安排加工时，我们必须要考虑原始工件的错位问题，使得在时间错位约束下，继列分批的继列分批最小化总完工时间的重新排序问题.Hall和Potts［5］在前人研究的基础上首先引入了工件错位的概念，考虑了在对从原始排序中产生的错位限制下的具有新来工件的最小化最大延误时间和总完工时间的单机重新排序问题.Potts和Brucker［7］［8］考虑了在单机情况下，分批排序的集中排序方法以及分批排序问题不同情况下的不同算法.Agnetis［1］主要考虑的是具有两个代理和两个目标函数的最小化加权总完工时间.Baker和Smith［2］考虑了多准则模型的机器排序问题，且给出了多代理目标函数的线性组合时的结果.Yuan和Mu［9，10］考虑了具有到达时间的最大序列或时间错位限制下的最小化完工时间的重新排序问题.根据Hall和Potts［5］的描述，单机重新排序问题能表示为：令JO＝｛J1，J2，…｝为单机上的原始工件集.在模型中，我们假定JO中的工件已经在最小化某一经典目标函数下最优地安排加工，且π＊是一个最优序.令JN＝｛，，…，｝为新工件集.记J＝JO∪JN.J中的每一个工件Jj的加工时间为整数且满足pj≥0.π＊和σ＊分别表示JO和J工件的最优序.对于J的工件的任意排序σ，我们定义下面几个变量：

·Cj（σ）表示J中工件Jj在σ中的完工时间.

·Dj（π＊，σ）表示JO中工件Jj的序列错位，即如果工件Jj在序列π＊和σ中分别是第x和y个工件，那么Dj（π＊，σ）＝.

在不引起混淆的前提下，上面的参数可以分别简化为Cj，Dj（π＊）.

排序问题的标准分类方法［3，4］是三参数法分类αβγ，其中α表示排序环境，β描述工件特征或者限制要求，γ为最优化准则.本文仅讨论单机分批问题，也就是α＝1时的情形.对于β，讨论继列分批时对错位的限制，这些限制有下面的二种形式：

对于γ，这里的函数为总完工时间，因此研究模型可记为

在研究问题的过程中，主要考虑两个方面：第一，研究分批重新排序问题的可行排序和最优排序的结构性质.第二，基于这些性质，设计问题的最优算法.本文证明了这些问题能在多项式时间或者拟多项式时间内可解.

2 问题的性质

证因为在排序π＊和σ＊中JO中的工件具有相同的排序，移走排序σ＊中的任何一个空闲时间仍能够保持其可行性，且∑Cj的数值不会增大.那么，该问题存在工件间没有空闲时间的最优排序.优先级指标序列排序原则表明JO中的工件在排序π＊和σ＊中具有相同的次序.因此，Dmax（π＊）的值由排在JO最后一个工件之前的工件个数决定.

证首先分析JO中的工件.最优序σ＊中JO的工件并没有与排序π＊一样按照SPT序排列.令工件Ji是σ＊中比排序π＊中相对于JO的其它工件更靠后的具有最小指标的工件，工件Jj（j＞i）为σ＊中排在工件Ji之前的JO的一个工件，如果它们在同一批次中，显然不会增加∑Cj，所以主要讨论的是它们不在同一个批次中的情况.因为π＊是一个SPT序列，所以有pi≤pj.通过相互交换σ＊中工件Ji和Jj的位置得到一个新的排序，记为σ′，那么

且σ′中所有位于Ji和Jj所在批之间各批的工件都比σ＊中提早完工pj－pi个单位时间.这样可知，通过这种互换JN中工件的完工时间不会增加，JO中的工件的序列错位不会超过k.如果σ′中工件Jj的位置不比π＊中的位置靠前（与工件Ji的情形一样），那么，Dj（π＊，σ′）＜Di（π＊，σ＊），否则，Dj（π＊，σ′）＜Dj（π＊，σ＊）.在两种情形下，

其中h表示σ＊中位于Ji和Jj所在批之间各批以及Ji所在批中含有JN的工件数，都有Dmax（π＊，σ′）≤Dmax（π＊，σ＊）和∑Dj（π＊，σ′）≤∑Di（π＊，σ＊）.因此，排序σ＇是可行的且是最优的.重复上述有限次讨论可以说明一定存在与排序π＊一样按照SPT序排列的最优序.显然，如果工件之间存在着空闲时间，减去相应的空闲时间，那么∑Ci肯定会减小，因此工件之间不存在着空闲时间.

3 算法设计

算法1：

输入：给定pj（j＝1，2，…，n），k，π＊和，且k≤nN；

标号：让JN中所有工件按照SPT规则排列好；

值函数：f（i，j，t，δ）表示最大序列错位为δ的时候，部分工件的总完工时间为最小的排序.其中i表示为JO的i个工件，j表示为JN中的j个工件，t表示当前工件的完工时间；

其中h0表示当前批中工件Ji－1所在批到当前批之前所有批中属于JN的工件个数（如果在同一批，则h0＝0），h1表示当前批含有工件个数（不包含工件Jj），h2表示工件Ji－1所在批到Jj所在批中属于JN的工件个数.h3表示当前批含有工件的个数（不包含工件Jj）.

定理1算法1在时间的最优排序的算法.

证 由引理1，2可知，只要通过SPT规则把JO和JN的全部的情况给列出来，算法2通过比较所有的可能出现的情况，就可以得到最优排序.现在考虑算法2的时间复杂性.因为i≤n0，j≤nN，δ≤k≤nN，而工件的最后完工时间t计算的次数最多为2n，因此递推函数的算法复杂性为O）.而上面的排序过程中所产生的的时间复杂性为O），因此总的算法复杂性为O（）.

算法2：

输入：给定pj（j＝1，2，…，n），k和π＊，且k≤n0nN；

标号：给JN中所有工件按照SPT规则标号；

值函数：f（i，j，t，δ）表示总序列错位为δ的时候，部分工件的总完工时间为最小的排序.其中i表示为JO的i个工件，j表示为JN中的j个工件，t表示当前工件的完工时间；

初值条件：f（0，0，0，0）＝0；

其中h0表示为当前批之前所有批中属于JN的工件个数，h1表示当前批中工件个数（不包含工件Ji），h2表示当前批中工件个数（不包含工件Jj）.

定理2算法2在时间最优排序算法.

证由引理2可以知道，只要通过SPT规则把JO和JN的全部的情况给列出来，算法2通过比较所有的可能出现的情况，就可以得到最优排序.现在考虑算法2的时间复杂性，因为i≤n0，j≤nN，δ≤k≤n0nN，而工件的最后完工时间t所计算的次数最多为2n，因此递推函数的算法复杂性为O（）.而上面的排序过程中所产生的的时间复杂性为O（n＋nNlognN），因此总的算法复杂性为O（n20n2Nn）.

［1］Agnetis A，Mirchandani P B，Pacciarelli D and Pacifici A.Scheduling problems with two completing agents［J］.Operations Research，2004，52：229－242.

［2］Baker K R and Smith J C.A multiple－criterion moderl for machine scheduling［J］.Jounrnal of Scheduling，2003，6：7－16.

［3］Brucker P.Scheduling algorithms［M］.Berlin：Springer Verlag，2001.

［4］Graham R L，Lawler E L，Lenstra J K，et al.Optimization and approximation in deterministic machine scheduling：A survey［J］.Annals of Discrete Mathematics，1979，5：287－326.

［5］Hall N G and Poots C N.Rescheduling for new orders［J］.Operations Research，2004，52：440－453.

［6］Potts C N and Van L N，Wassenhove.Integrating scheduling with batching and lot－sizing：a review of algorithms and complexity［J］.Operational Research，1992，43：395－406.

［7］Potts C N，Kovalyov MY.Scheduling with batching：a Review［J］.European Journal of Operation Research.2000，120：228－249.

［8］Brucker P，Gladky A.Scheduling a batching machine［J］.Journal of Scheduling，1998，1：31－54.

［9］Yuan J J and Mu Y D.Rescheduling with release dates to minimize makespan under a limit on the maximum sequence disruption［J］.European Journal of Operation Research，2007，182：936－944.

［10］Yuan J J and Mu Y D，Lu L F and Li W H.Rescheduling with release dates to minimize total sequence disruption under a limit on the makespan［J］.Asia－Pacific Journal of Operational Research，2007，24：789－796.

Rescheduling to Minimize Total Completion under a Limit Sequence Disruption of the Series Batching

MUYun－dong，PiJun－de，GUOXiao
（College of Science，Henan University of Technology，Zhengzhou 450001，China）

In the rescheduling on a single batching machine，a set of the original jobs has already been scheduled，in order to make a given objective function is minimal.The decision maker needs to insert the new jobs into the existing schedule without excessively disrupting it.We consider the total completion time of the series batching under the a limit on the sequence disruption，and give the polynomial time algorithms to the maximum sequence disruption and the total sequence disruptions.

rescheduling；single machine；batching；batching sequence；sequence disruption

O224

A

1672－1454（2012）04－0068－04

2010－03－26；［修改日期］2010－09－27

河南省自然科学基金NSFHN（112300410078）；河南省教育厅自然科学基金（2011B110008）；河南工业大学博士科研基金