许 尉，赵玉芳，岳雅娟

（沈阳师范大学 数学与系统科学学院，沈阳 110034）

0 引 言

在很多实际生产中，工件一般在处理机上加工后，若干个放在一起，形成一批，用车等工具运走，转交到客户手中，才算加工完。把这个时间称为这批工件的交货期，这样的问题成为批运输问题。在这个问题中，既要考虑工件的加工顺序，还要决定如何分批，使目标函数达到最优，所以这个问题变得更为复杂。批运输问题是Cheng等［1］首次提出的，对于单机、目标函数为总权提前惩罚与运输费用之和问题，他们证明了这个问题是一般意义NP－难的。Cheng等［2］进一步给出了此问题的一个动态规划算法，当批数有一个固定的上界时，这个算法是拟多项式的。对于极小化批运输费用与工件的提早惩罚之和的单机分批排序问题，Cheng等［3］给出了这个问题与平行机排序问题的关系，从而把此问题归类于平行机问题。对于目标函数是总加权提早与平均批运输时间之和问题，Cheng等［4］证明是强NP－难的。Hermann等［5］考虑的是所有工件有一个公共工期的单机批运输问题，对于总提早及延误惩罚与误工工件的运输费用之和问题，给出了拟多项式动态规划算法。当公共工期是一个决策变量时，Chen［6］给出了这个问题是多项式可解的。对于极小化总加权提早及延误与误工工件运输费用之和的单机批运输问题，Yun［7］证明是强NP－难的。Ji等［8］讨论了在单机生产环境下的批运输排序问题，总加权流水时间与运输费用之和的问题是强NP－难的；当批数有一个上界时，该问题变为一般意义NP－难的。Wang等［9］研究了平行机生产环境下的批运输排序问题，对于总流水时间与运输费用之和问题，证明了一般情况下是强NP－难的，并给出了一个动态规划算法。

机器由于维修或故障等原因会导致在某段时间内不可用，从而影响工件的加工过程，这种现象在排序问题中被称之为机器可用性限制问题。Lee［10］研究了机器具有可用性限制的排序问题，讨论了极小化加权总完工时间的单机及平行机排序问题，指出这2个问题都是NP－难的，给出启发式算法，并分析了误差界。对于不可用区间是已知的情况，Lee［11］考虑了2台机器的流水作业排序问题，证明了时间表长问题是NP－难的，且给出了拟多项式动态规划算法。Lee［12］进一步分别对可恢复和不可恢复的情况进行了讨论，分析了问题的复杂性，给出了拟多项式动态规划算法，并且对给出的启发式算法进行了误差界分析。Chen［13］研究了带有有限个不可用区间且工件是不可恢复的单机排序问题，对于极小化总流水时间问题，给出了分枝定界算法。Kacem等［14］研究带有一个固定的不可用区间限制且工件是不可恢复的排序问题，目标函数为总加权完工时间。对于该问题他们给出了一个全多项式时间近似算法（FPTAS）。对于同时带有学习、恶化效应及可用性限制问题，赵玉芳等［15］给出了加权总完工时间拟多项式动态规划算法。Zhao等［16］研究带有速度维修的两台平行机的排序问题，当目标函数为总完工时间时给出多项式时间算法。Wang等［17］研究了机器带有速度维修单机工期分配排序问题，对于极小化总提早、总延误和共同的流余量费用问题给出多项式时间算法。Wang等［18］研究每台机器都带有恶化维修的排序问题，讨论了极小化完工时间的绝对差值总和和等待时间的绝对值差值总和问题，并证明出它们是多项式时间可解的。Wang等［19］研究带有一个恶化维修的平行机排序问题，他们给出目标函数为总完工时间的多项式时间算法。

本文将批运输问题与机器的可用性限制结合在一起，并且运输费用与批数有关，这个问题到目前为止还没有人研究过。该问题不仅对实际生产具有指导意义，而且能够丰富生产物流调度优化理论，具有一定的理论价值。

1 问题描述

其中h表示带有不可用区间限制的问题；bd表示批运输问题；U为批数R的上界。

2 问题1，h｜bd，R≤U｜（ ∑Fi＋α（R））

对于工件是不可恢复的极小化总完工时间的单机排序问题，Adiri等［21］指出其问题是NP－难的。那么对于目标函数是总流水时间的问题，至少为NP－难的。故可得到下面结论。

对于单机带有不可用区间目标函数为

引 理 1 问 题 1，h｜bd，R≤U｜（∑Fi＋α（R）） 存在一个最优解π＊＝〈B1，…，BR〉满足

1）在T1前和T2后的工件分别按SPT规则排列；

图1 问题1，h｜bd，R≤U｜ （∑Fi＋α（R））的例图

2）Bl包含所有在（Dl－1，Dl］之间完工的工件。

其他批的完工时间不变，则有＝；由pi＞pj可知，＜，其余批不变。即第l批前的工件流水时间不变，第l批的工件的流水时间减少，第l批后的工件流水时间也不变。从而G（π＊）＞G（π′），所以与假设π＊为最优序列矛盾。于是，存在一个最优序列π＊，使得T1前的工件按SPT规则排列。同理可证在T2后的工件也满足SPT规则排列。从而存在一个最优解π＊满足在T1前和T2后的工件分别按SPT规则排列。

下面用反证法证明2）。不失一般性，设最优序列π＊中工件的加工顺序为J［1］，J［2］，…，J［n］，其中J［j］表示π＊中第j个加工的工件。Bl批的交货期为，则＜…＜＜…＜。假设存在一个工件J［j］满足＜≤且不在Bl批中加工，由于工件J［j］在Bl批之前没有完工，则有＞。若把工件J［j］放在Bl批中，设为新序列π′，其他工件的加工顺序与所在批不变，则有＝，，从而G（π＊）＞G（π′），与π＊为最优排序矛盾。在其他批中的工件按照同样的讨论，可以证明存在一个最优排列，使得所有批都是由一些连续完工的工件组成的。在任意的最优排列中，因为所有在Dl处完工的工件，都可以被分到Bl中，l＝1，…，R。Bl应包含在（Dl－1，Dl］完工的所有工件。

由于同批中的所有工件的流水时间相同，可以得到下面的结论。

引理2 对于问题1，h｜bd，R≤U｜ （∑Fi＋α（R）） 任何一个最优序列，每一批内的工件加工顺序是任意的。所以＞。又因为

1）当工件Jj排在［0，T1］区间内，有

其中Fj＝｛Dl｜Dl－1＜t1≤Dl，D0＝0，l＝1，…，R｝；

2）当工件Jj排在T2后，有

其中Fj＝｛Dl｜Dl－1＜t2＋T2≤Dl，D0＝0，l＝1，…，R｝。

由以上分析可得动态规划算法如下：

在下述动态规划算法中，设

算法DP1：

1）把工件按SPT序编号，使p1≤p2…≤pn；

3）按递归方程：

其中j＝0，…，n，t1＝0，…，T1，t2＝0，…，P，Dl＝Dl－1＋1，…，T2＋P，l＝1，…，R，D0＝0；

4）G＊＝min｛HR（n，t1，t2，D1，…，DR）＋α（R）｝，利用反向追踪得到最优排序及分批，R＝1，…，U。

引理3 动态规划算法DP1的时间复杂性为O（nU2T1（T2＋P）U）。

证明 在状态（j，t1，t2，D1，…，DR）下HR（j，t1，t2，D1，…，DR）中j的取值为1，2，…，n；t1的取值为0到T1，则t2在t1取定之后便可确定；D1到DR可取到的最大值都为T2＋P，R＝1，…，U；从而递推关系式的不同状态R＝1，…，U至多有nT1（T2＋P）U。对于每个状态，递推关系式的右边可以在O（U）时间内被计算。因此，整个的计算复杂性为O（nU2T1（T2＋P）U）。

3 问题P2，h｜bd，R≤U｜ （∑Fi＋α（R））

王国庆等［9］已经证明出问题P2｜bd，R≤U｜ （∑Fi＋α（R）） 为NP－难的，在此基础上加入一个不可用区间，可得下面结论。

定理2 问题P2，h｜bd，R≤U｜ （∑Fi＋α（R）） 至少是NP－难的。

引理4 问题P2，h｜bd，R≤U｜ （∑Fi＋α（R）） 存在一个最优解π＊＝〈B1，…，BR〉满足

1）在M1上的T1前和T2后与M2上加工的工件分别按SPT规则排列；

2）Bl批中包含所有在（Dl－1，Dl］之间完工的工件，l＝1，…，R。

其他批的完工时间不变，则有＝；由pi＞pj可知，＜其余批不变，第l批前的工件流水时间不变，第l批的工件的流水时间减少，第l批后的工件流水时间也不变。从而G（π＊）＞G（π′），所以与假设π＊为最优序列矛盾。综上所述，可以证明出存在一个最优解使得在M1上的T1前和T2后与M2上加工的工件分别按SPT规则排列。

2）同引理1中2）的证明。

而对于2台平行机的情况下，机器由于维修或故障，会导致机器在一段时间内不可用，在这种机器受限的情况下，假设只有1台机器受限。那么把问题划分为2类，一类是机器中途维修；另一类是机器中途损坏，即懂某一刻开始一直不可用。具体描述如下：

3.1 机器中途维修

图2 问题3.1的实例

对于第一类情况（如图2所示）。

由引理4可知，对于问题P2，h｜bd，R≤U｜（∑Fi＋α（R）） 的第一类情况，存在最优排序，在M1上的T1前和T2后与M2上的工件的加工顺序都按SPT排列。那么将工件分成3部分，分别在M1上的T1前和T2后与M2上，使每一部分工件都按SPT排列，从而得到最优排序。据此，可以建立求解这个问题的动态规划算法。

在下述动态规划算法中，假设工件J1…Jj已排完，定义HR（j，t1，t2，t3，D1，…，DR）为已排列工件J1到Jj的最小总流水时间，使得在M1上T1前的总加工时间为t1（t1＜T1），在M1上T2后总加工时间为t2，则当前在T2后最后一个工件的完工时间为t2＋T2，在M2上工件的总加工时间为t3，Bl的交货期为Dl，l＝1，…，R。于是，工件J1…Jj的总流水时间分以下3种情况：

1）当工件Jj排在M1上的［0，T1］区间内，有

其中Fj＝｛Dl｜Dl－1＜t1≤Dl，D0＝0，l＝1，…，R｝；

2）当工件Jj排在M1上的T2后，有

其中Fj＝｛Dl｜Dl－1＜t2＋T2≤Dl，D0＝0，l＝1，…，R｝；

3）当工件Jj排在M2上，有

其中Fj＝｛Dl｜Dl－1＜t3≤Dl，D0＝0，l＝1，…，R｝。

由以上分析可得动态规划算法如下：

算法DP2：

1）把工件按SPT序编号，使p1≤p2…≤pn；

3）按递归方程：

其中j＝0，…，n，t1＝0，…，T1，t2＝0，…，P，t3＝0，…，P，Dl＝Dl－1＋1，…，T2＋P，l＝1，…，R，D0＝0；

4）G＊＝min｛HR（n，t1，t2，t3，D1，…，DR）＋α（R）｝，利用反向追踪得到最优排序及分批R＝1，…，U。

引理5 动态规划算法DP2的时间复杂性为O（nT1PU2（T2＋P）U）。

证明 在状态（j，t1，t2，t3，D1，…，DR）下HR（j，t1，t2，t3，D1，…，DR）中j的取值为1，2，…，n；t1的取值为0到T1，而t2的取值为0到P，从而t3便可被确定下来；D1到DR可取到的最大值都为T2＋P，R＝1，…，U；从而递推关系式的不同状态至多有nT1P（T2＋P）U。对于每个状态下Fj可以在O（U）时间内被计算。因此，整个的计算复杂性为O（nU2T1（T2＋P）U）。

3.2 机器中途损坏

图3 问题3.2的实例

对于第二类情况（如图3所示）。

由引理4可知，对于问题P2，h｜bd，R≤U｜（∑Fi＋α（R）） 的第二类情况，存在最优排序，在M1上的T1前与M2上的工件的加工顺序都按SPT排列。那么可以将工件分成2部分，分别在M1上的T1前和M2上，使每一部分工件都按SPT排列，从而得到最优排序。据此，可以建立求解这个问题的动态规划算法。

在下述动态规划算法中，假设工件J1…Jj已排完，定义HR（j，t1，t2，D1，…，DR）为已排列工件J1到Jj的最小总流水时间，使得在M1上T1前的总加工时间为t1（t1＜T1），在M2上工件的总加工时间为t2，Bl的交货期为Dl，l＝1，…，R。于是，工件J1，…，Jj的总流水时间分以下两种情况：

1）当工件Jj排在M1上的［0，T1］区间内，有

其中Fj＝｛Dl｜Dl－1＜t1≤Dl，D0＝0，l＝1，…，R｝；

2）当工件Jj排在M2上，有

其中Fj＝｛Dl｜Dl－1＜t3≤Dl，D0＝0，l＝1，…，R｝。

由以上分析可得动态规划算法DP3如下：

1）把工件按SPT序编号，使p1≤p2…≤pn；

3）按递归方程：

其中j＝0，…，n，t1＝0，…，T1，t2＝0，…，P，Dl＝Dl－1＋1，…，T2＋P，l＝1，…，R，D0＝0；

4）G＊＝min｛HR（n，t1，t2，D1，…，DR）＋α（R）｝，利用反向追踪得到最优排序及分批，R＝1，…，U。

引理6 动态规划算法DP3的时间复杂性为O（nT1U2PU）。

证明 在状态（j，t1，t2，D1，…，DR）下HR（j，t1，t2，D1，…，DR）中j的取值为1，2，…，n；t1的取值为0到T1，则t2在t1取定之后便可确定；D1到DR可取到的最大值都为P，R＝1，…，U；从而递推关系式的不同状态R＝1，…，U至多有nT1PU。对于每个状态，递推关系式的右边可以在O（U）时间内被计算。因此，整个的计算复杂性为O（nT1U2PU）。

4 结 论

本文研究了单机和2台平行机带有不可用区间的批运输问题，其中机器有可用性的限制。通过分析，证明了此类问题至少是NP－难的。为此给出了此类问题的拟多项式动态规划算法，并给出了时间复杂性及相应的数值例子。为了进一步的研究，需要值得考虑的是单机及平行机情况下是否是强NP－难的。对于这两种情况是否能找到一个FPTAS方案。

［1］CHENG T C E，KAHLBACHER H G.Scheduling with delivery and earliness penalties［J］.Asia－Pacific J Oper Res，1993，10（2）：145－152.

［2］CHENG T C E，GORDON V S.Batch delivery scheduling on a single machine［J］.J Oper Res Soc，1994，45（10）：1211－1215.

［3］CHENG T C E，GORDON V S，KOVALYOV M Y.Single machine scheduling with batch deliveries［J］.Eur J Oper Res，1996，94（2）：277－283.

［4］CHENG T C E，KOVALYOV M Y，Lin B M T.Single machine scheduling with batch delivery and job earliness penalties［J］.SIAM J Optim，1997，7（2）：547－559.

［5］HERMANM J W，LEE C Y.On scheduling to minimize earliness－tardiness and batch delivery costs with a common due date［J］.Eur J Oper Res，1993，70（3）：272－288.

［6］CHEN Zhilong.Scheduling and common due date assignment with earliness－tardiness penalties and batch delivery costs［J］.Eur J Oper Res，1996，93（1）：49－60.

［7］YUAN Jinjiang.A note on the complexity of single－machine scheduling with a common due date，earliness－tardiness，and batch delivery costs［J］.Eur J Oper Res，1996，94（1）：203－205.

［8］JI Min，HE Yong，CHENG T C E.Batch delivery scheduling with batch delivery cost on a single machine［J］.Eur J Oper Res，2007，176（2）：745－755.

［9］WANG Guoqing，CHENG T C E.Parallel machine scheduling with batch delivery costs［J］.Int J Prod Econ，2000，68（2）：177－183.

［10］LEE C Y.Machine scheduling with an availability constraint［J］.J Global Optim，1996，9（3／4）：395－416.

［11］LEE C Y.Minimizing the makespan in the two－machine flowshop scheduling problem with an availability constraint［J］.Oper Res Lett，1997，20（3）：129－139.

［12］LEE C Y.Two－machine flowshop scheduling with availability constraints［J］.Eur J Oper Res，1999，114（2）：420－429.

［13］CHEN W J.Minimizing total flow time in the single－machine scheduling problem with periodic maintenance［J］.J Oper Res Soc，2006，57：410－415.

［14］KACEM I，HAOUARI M.Fully polynomial time approximation scheme for the weighted flow－time minimization on a single machine with a fixed non－availability interval［J］.Comput Indust Eng，2009，56（4）：1708－1712.

［15］崔苗苗，赵玉芳，王松丽.机器具有可用性限制的加权总完工时间问题［J］.沈阳师范大学学报：自然科学版，2012，30（2）：157－163.

［16］ZHAO Chuanli，TANG Hengyong，CHENG Congdian.Two－parallel machines scheduling with rate－modifying activities to minimize total completion time［J］.Eur J Oper Res，2009，198（1）：354－357.

［17］WANG Xiaoyuan，WANG Mingzheng.Single machine common flow allowance scheduling with rate－modifying activities［J］.Comput Indust Eng，2010，59（4）：898－902.

［18］WANG Jibo，WEI Caimin.Parallel machines scheduling with a deteriorating maintenance activity and total absolute differences penalties［J］.Appl Math Comput，2011，217（20）：8093－8099.

［19］WANG J J，WANG J B，LIU F.Parallel machines scheduling with a deteriorating maintenance activity［J］.J Oper Res Soc，2011，62：1898－1902.

［20］GRAHAM R L，LAWLER E L，LENSTRA J K，et al.Optimization and approximation in deterministic sequencing and scheduling：A survey［M］.Amesterdam：North－Hollard，1979，5：287－326.

［21］ADIRI I，BRUNO J，FROSTIG E，et al.Single machine flow－time scheduling with a single breakdown［J］.Acta Inform，1989，26（7）：679－696.