带有机器维修和工件派送的单机排序问题

蔡 伟,杨 梅

(1.南京审计大学金审学院，江苏南京 210046；2.中国石油大学(北京)克拉玛依校区，新疆克拉玛依 834000)

0 引言

机器加工及派送协同和带维修区间的排序问题是两类重要的排序问题，由于这两类排序问题在制造生产与供应链管理中应用前景广阔，所以近年来得到了广泛研究.而机器带维修区间的加工与工件派送相结合的排序问题，同样具有重要的应用价值，得到了一定的关注和研究.

1 问题描述及符号说明

本文研究的带有机器维修和单车辆派送到多顾客的排序问题,具体描述如下：给定工件集Y={J1，J2，…，Jn}，工件的Ji加工时间为pi，体积为si(0

n工件的个数ni第i个客户的工件数目m客户的个数Jj第j个工件Y={J1,J2,…,Jn}总工件集合Y=J1∪J2∪…∪Jm总工件集合Ji={Ji1,Ji2,…,Jini}第i个客户的工件集合P(B)集合B中工件的总加工时间ti工件派送到第i个客户所需时间s维修开始的时间t维修结束的时间△维修时长δ维修前空闲时间Ba维修后加工的第一批次BqSPT序列中最后一个批次Bw决定批次P所有工件加工时间和

定理1 问题(1，h(1)→D，k=m|v=1，c=1，ti|Cmax)是NP-难的.

证明由现有结论知：问题(1，h(1)→D，k=1|v=1，c=1，ti|Cmax)是NP-难的，本文研究的问题是派送到多客户情况，把派送到每个客户的时间都看成相同就是现有结论中单客户情形，所以问题[1，h(1)→D，k=m|v=1，c=1，ti|Cmax]也是NP-难的.或者可以把工件的加工时间都看成0，此时与机器加工无关，只需将工件分批派送，即简化为一个装箱问题，由于装箱问题是NP-难的，那么本章节研究的问题也是NP-难的.

2 近似算法

第1步 依据每批体积不超过车辆总体积的原则，利用FFD算法对每个客户的工件进行分批.

(3)将派送到客户的时间按不减排序，最小记为t1,最大记为tm.

第3步 按照如下规则构造流水作业排序问题实例I(F2||Cmax).

第4步 利用Johnson算法最优的求解所构造流水作业排序问题实例I，所得排序记为π=〈B1，B2，…，BK〉.

(1)按照π中的批次顺序加工、交付批次；

(2)同一批次加工不被维修打断，即若维修前不能加工完该批次，则该批次放在维修后加工；

(3)每一个批次内部工件加工顺序任意，若车辆可用时有多个批次可派送，则先加工完的批次先派送.

3 最坏情况界分析

成立，于是对每个客户i都可得

那么

那么

证明已知Cmax的取值是前面批次的完工时间与后面运送时间和，我们称决定完工时间的批次w为决定批次.根据批次的加工时间与派送时间，批次分成SPT与LPT阶段，按照维修的位置及决定批次的位置分以下情况证明.

由于情况(1)(3)(6)本质上都是决定批次在SPT序内部，并且维修在计算完工时间时不起作用，证明方式完全相同，本文只证明情况(1)即可.情况(2)(5)(7)(8)本质上都是决定批次在LPT序内部，证明过程相同者只证明其中一种.情况(4)本质上是决定批次在SPT序内部，但是放缩有所不同，需单独证明.

(1)维修在SPT与LPT之间，即维修不打断SPT和LPT序列.

a.决定批次在维修之前,

b.决定批次在维修之后,

(2)维修在SPT之间，即维修打断SPT序列.

c.决定批次在维修之前，证明与(1)的a相同.

d.决定批次在维修之后,

ⅰ.决定批次在SPT内,

ⅱ.决定批次在LPT内，证明与(1)的b相同.

(3)维修在LPT之间，即维修打断LPT序列.

a.决定批次在维修之前,

ⅰ.决定批次在SPT内，证明与(1)的a相同.

ⅱ.决定批次在LPT内,

b.决定批次在维修之后，证明与(1)的b相同.

对于问题(1，h(1)→D，k=m|v=1，c=1，ti|Cmax),本章节提出的FFD-Johnson算法得到的界不是紧界，这就需要我们提出更好的算法，或者是在最差性能比分析的过程中给出更细致与严格的放缩.

定理3 FFD-Jonhson算法的时间复杂度为O(nlogn)，n是工件个数.

证明首先FFD装箱算法所需时间是O(nlogn)，所分批次数目最多为n；其次比较批次的加工时间与派送时间，所需时间为最多为O(n)；最后对加工时间小于派送时间的批次按SPT序排，加工时间大于派送时间的批次按LPT序排，所需时间也是O(nlogn)；因此FFD-Jonhson算法的时间复杂度为O(nlogn).

4 特殊情况

接下来考虑只有一个客户的特殊情况，即：工件在带有一个不可用维修区间的机器上加工且由单车辆派送到单顾客的情形，问题表示为(1，h(1)→D，k=1|v=1，c=1，T|Cmax).

引理4 对于该特殊情况，最优排序π*得到的最优时间表长C*max满足

定理4 对于所给特殊问题(1，h(1)→D，k=1|v=1，c=1，T|Cmax)，FFD-Johnson算法的界为2，且是紧界.

证明若K*≥2，按维修区间的位置分以下几种情形证明：

(1)维修不打断SPT和LPT序.

a.由于车辆在派送SPT序的批次不会空闲，所以当车辆在派送LPT序的批次时有空闲，那么

b.若车辆在派送LPT序的批次时不空闲,

(2)维修打断SPT序.

a.车辆在派送LPT序批次时有空闲,

b.车辆在派送LPT序批次时无空闲且车辆在派送SPT序的批次也无空闲,

c.车辆在派送LPT序批次时无空闲且在派送SPT序的批次时有空闲，此时空闲只会发生在维修后第一个批次加工完成之前，否则与派送SPT序的批次时有空闲矛盾，因此

ⅰ.当K=K*时,

ⅱ.当K>K*时,

(3)维修打断LPT序.

a.车辆在派送LPT序批次时有空闲,

Cmax=P+△+δ+T≤2C*max.

b.车辆在派送LPT序批次时无空闲,

Cmax=P(B1)+KT≤2C*max.

紧界实例：设有两个工件，加工时间与体积分别为J1=(1，∈)和J2=(∈，1),派送时间T=2∈，机器维修区间为[1，1+∈]，车辆容积为1，其中∈是趋于0的正常数.利用FFD装箱算法将工件分为两个批次B1={J1}和B2={J2}.最优算法是先加工B1再加工B2，所用时间为1+4∈,利用FFD-Johnson算法是先加工B2再加工B1，所用时间为2+3∈，于是当∈→0时,