机器带周期性维护时段的加工与运输协同排序问题

胡觉亮，杨佳雯，苏晓彤，董建明

(浙江理工大学理学院，杭州 310018)



机器带周期性维护时段的加工与运输协同排序问题

胡觉亮，杨佳雯，苏晓彤，董建明

(浙江理工大学理学院，杭州 310018)

研究了一类机器带周期性维护时段且完工工件需要运输的新型排序问题。在该问题中，机器需要进行周期性的维护，且被维护时段打断的工件加工不可恢复；工件具有不同的尺寸且工件的加工时间与物理尺寸大小具有一定的比例关系，每个维护时段内只允许加工一个批次的工件；加工完的工件需要由一辆带有容量限制的运输工具运往客户。算法的目标是极小化所有工件加工完成并运送到客户的时间。证明了该问题是强NP-Hard问题，设计了该问题的一个多项式时间近似算法，并证明了该算法的最坏情况界不大于5/3。

单台机；维护时段；不可恢复；近似算法

0 引 言

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

机器带维护时段的排序问题，根据机器上维护时段的个数可分为单维护时段排序问题和周期性维护时段排序问题。关于带单维护时段的排序问题，对于考虑工件的加工一旦被维护时段打断且加工不可恢复的情况，目前已有很多好的结果。当目标函数为极小化最大完工时间时，Lee[1]利用LPT规则提出一个最坏情况界不大于4/3的紧界算法。He等[2]对同样问题提出一个多项式时间近似方案。当目标函数为极小化总完工时间时，Lee等[3]证明SPT算法的紧界不大于9/7。Sadfi等[4]提出了改进的MSPT算法，并证明算法的紧界为20/17。He等[5]提出了一个多项式时间近似方案。Low等[6]对于机器带周期性维护时段的问题，针对目标函数为极小化最大完工时间的情况，提出了FFD算法的一些重要性质。Yu等[7]比较了LS算法、LPT算法和MLPT算法对最坏情况界的影响。Lee等[8]对目标函数为极小化总误工数的问题提出了一种两阶段启发式算法。Liao等[9]对目标函数是极小化最大延误的问题提出了一个分支定界法去寻找最优排序方案，以及一个针对存在大工件情况的启发式算法。Chen[10]对于目标函数是极小化总误工数的问题，提出了一种有效的启发式算法，同时还提出一个分支定界法来寻找最优排序方案。当目标函数为极小化最大完工时间的问题，Ji等[11]证明了经典LPT算法的最坏情况界为2。Chen[12]提供了一个二进制整数规划方案，以及针对大工件存在情况下的一个启发式算法。

对于加工与运输协同的排序问题，目前的研究主要集中在工件具有不同的物理尺寸这种重要情形，主要的研究成果有：Chang等[13]首先建立了该问题的模型，给出了单机环境和两台平行机环境下的近似算法，同时给出了单机环境下具有两个客户情况下的近似算法；Zhong等[14]给出了单机环境和两台平行机环境下的改进算法；Lu等[15]给出了单机环境下该类问题的最好的近似算法；汪磊扬等[16]又进一步改进了两台平行机环境下的该类问题的结果，得到改进的近似算法界接近3/2。

对于机器带维护时段同时加工完的工件需要运输到相应客户的问题，即机器带维护时段的加工与运输协同的排序问题，目前研究成果比较少，主要成果有：Wang等[17]在单台机工件不可恢复单维护时段以及运输工具容量有限，即最多只能装下k个工件的情况下，提出目标函数为极小化最大完工时间问题的近似算法，并得到最坏情况界不大于3/2；对于同一目标函数，Liu等[18]对于工件带有释放时间和尺寸大小属性的带运输排序问题，又进一步提出改进的近似算法，使得最坏情况界不大于3/2；Hu等[19]针对单台机单维护时段以及运输工具容量有限情况下的问题，提出目标函数为极小化最大完工时间问题的近似算法，得到最坏情况界为2，并证明该情况界是紧的。

本文研究机器带维护时段的加工与运输协同的排序问题，考虑工件具有不同尺寸且运输工具具有容量限制的情况。与上述机器带单维护时段的加工与运输协同的排序问题不同，本文考虑更为复杂的机器带有周期性维护时段的情况，且限制机器的加工时段长度与工件的尺寸之间具有一定的比例关系。由于该问题是强NP-Hard且具有3/2的难近似性，本文给出了该问题的一个近似算法，并证明该算法的最坏情况界不大于5/3。

1 问题描述及符号定义

2 近似算法

本文算法用到经典一维装箱问题的FFD算法。FFD算法首先将物品(工件)按照尺寸大小从大到小排列，然后将工件按序逐个装箱。若已打开的箱子无法装入当前工件时则另开一个新箱子。根据装箱问题的FFD算法的性质[20-21]，可得:

(1)

(2)

其中：FFD(I)表示对于装箱实例运用FFD算法得到的箱子数，OPT(I)表示最优的装箱数目。下面将给出问题的一个近似算法，具体算法可以描述为：

算法H:

Step1 对工件按尺寸大小的非增顺序进行排序，得到工件序列J1,J2,…,Jn。

Step2 按FFD算法对工件进行分批，得到批次数为bH，每个批次记为Bk(k=1,2,…,bH)。

Step4 按批次顺序依次加工工件，每个加工时段中只安排一个批次的加工。当运输工具处于空闲时，除最后一个批次外，每个批次加工完成并等到当前加工时段结束后对该批次进行运输。若最后一个批次加工完成时运输工具空闲则立即对该批次进行运输。得到算法解记为CH。

对算法H中批次数bH=1的情况进行讨论，若bH=1,则b*=bH,由算法H可得CH=C*，所以不妨假设bH≥2。当批次数bH≥2时，令x为算法解中最后一个批次的总加工时间，根据一个运输周期时长T与一个加工时段和一个维护时段之和即E+I的大小比较，得到不同形式的算法解。当T

下面以一个具有6个工件的实例对算法H进行说明。

实例：给出含6个工件的集合{J1,J2,…,J6}，工件加工时间分别为p1=2，p2=8，p3=7，p4=8，p5=8，p6=4，机器的加工时段长度E=12，维护时段长度I=6。运输工具的容量大小z=6，运输时间T=2t=20，工件的尺寸分别为s1=1，s2=4，s3=3.5，s4=4，s5=4，s6=2。执行算法H得到：bH=4，B1={J2,J6},B2={J1,J4},B3={J5},B4={J3},P1=12，P2=12，P3=8，P4=7。排序结果如图1所示。由图可知运行算法H得到的目标函数值CH=92。

图1 算法H示例

假设该问题的最优批次数为b*，则根据式(1)和式(2)容易得到：

(3)

(4)

那么当bH>b*时，可以得到如下运行算法H后得到工件批次数情况的相关性质。

性质2[21]：批次b*+1、b*+2、…、bH中至多只有b*-1个工件。

性质3：所有放入批次b*+1、b*+2、…、bH中的任意工件的加工时间不超过一个加工时段长度E的1/3。

证明：根据性质2以及工件的加工时间和工件的尺寸大小的比例关系，可得此性质成立。

3 最坏情况界的证明

本节证明算法H的最坏情况界不大于5/3。

证明：因为T

a)I+x≤T

(E+I)+T+y，所以可得：

(5)

下面按照b*的不同取值进行讨论。

若b*=1，则bH=b*，由算法H可得CH=C*。

b)T

(6)

下面按照b*的不同取值进行讨论。

若b*=1，则bH=b*，此时CH=C*。

下面仅讨论b*≥2且满足bH>b*的情况。

证明：当T≥E+I时，令y为该情况下最优解中第一个批次的总加工时间。算法解为：CH=bHT+E，最优解C*满足C*≥b*T+y，于是有：

(7)

下面按照b*的不同取值进行讨论。

若b*=1，则bH=b*，此时CH=C*。

下面仅讨论b*≥2且满足bH>b*的情况。由式(3)可得：

4 结 论

本文研究了一类机器带维护时段的加工与运输协同的排序问题。该问题是经典的带维护时段排序问题和加工与运输协同排序问题的一个组合。在该问题中，工件先在一台需要周期性维护的机器上进行加工，然后由一辆带有容量限制的运输工具分批运往相应的客户。目标是合理安排工件的加工和运输，使得工件能够尽早加工完毕并运往客户。由于该问题是强NP-Hard问题，所以本文给出了该问题在工件的加工时间和工件的尺寸大小成比例关系且每个加工时段只可以加工一批工件情况下的一个近似算法。分析了算法的性质，并证明了该算法的最坏情况界不大于5/3。

对于该问题的进一步研究，我们将关注以下两个方面：一方面是改进本文的算法，使得最坏情况界小于5/3；另一方面是研究工件的加工时间和工件的尺寸大小没有比例关系的一般情况下的问题模型。由于不考虑运输且机器具有周期性维护时段的排序问题具有2的难近似性[11]，即不存在最坏情况界小于2的近似算法，所以该问题也具有2难近似性，这给研究增加了较大的难度。所以研究该类问题的一个最坏情况界接近2的近似算法，例如设计一个最坏情况界为5/2的算法可以作为后续研究的一个可行目标。

[1] LEE C Y. Machine scheduling with an availability constraint[J]. Journal of Global Optimization,1996,9(3):395-416.

[2] HE Y, JI M, CHENG T C E. Single machine scheduling with a restricted rate-modifying activity[J]. Naval Research Logistics,2005,52(4):361-369.

[3] LEE C Y, LIMAN S D. Single machine flow-time scheduling with scheduled maintenance[J]. Acta Informatica,1992,29(4):375-382.

[4] SADFI C, PENZ B, RAPINE C, et al. An improved approximation algorithm for the single machine total completion time scheduling problem with availability constraints[J]. European Journal of Operational Research,2005,161(1):3-10.

[5] HE Y, ZHONG W Y, GU H K. Improved algorithms for two single machine scheduling problems[J]. Theoretical Computer Science,2006,363(3):257-265.

[6] LOW C, MIN J, HSU C J, et al. Minimizing the makespan in a single machine scheduling problems with flexible and periodic maintenance[J]. Applied Mathematical Modeling,2010,34(2):334-342.

[7] YU X Y, ZHANG Y L, STEINER G. Single machine scheduling with periodic maintenance to minimize makespan revisited[J]. Journal of Scheduling,2014,17(3):263-270.

[8] LEE J Y, KIM Y D. Minimizing the number of tardy jobs in a single-machine scheduling problem with periodic maintenance[J]. Computers & Operations Research,2012,39(9):2196-2205.

[9] LIAO C J, CHEN W J. Single machine scheduling with periodic maintenance and nonresumable jobs[J]. Computer & Operations Research,2003,30(9):1335-1347.

[10] CHEN W J. Minimizing number of tardy jobs on s single Machine subject to periodic maintenance[J]. Omega,2009,37(3):591-599.

[11] JI M, HE Y, CHENG T. Single-machine scheduling with periodic maintenance to minimize makespan[J]. Computers & Operations Research,2007,34(2):1764-1770.

[12] CHEN J S. Scheduling of nonresumable jobs and flexible maintenance activities on a single machine to minimize makespan[J]. European Journal of Operational Research,2008,190(1):90-102.

[13]CHANG Y C, LEE C Y. Machine scheduling with job delivery coordination[J]. European Journal of Operational Research,2004,158(2):470-487.

[14] ZHONG W Y, DSA G, TAN Z Y. On the machine scheduling problem with job delivery coordination[J].European Journal of Operational Research,2007,182(3):1057-1072.

[15] LU L F, YUAN J J. Single machine scheduling with job delivery to minimize makespan[J]. Asia-Pacific Journal of Operational Research,2008,25(1):1-10.

[16] 汪磊扬，刘朝晖.带批运输的两台同型机排序问题的改进算法[J].运筹学学报，2013,17(1)：38-43.

[17] WANG X L, CHENG T C E. Machine scheduling with an availability constraint and job delivery coordination[J]. Naval Research Logistics,2007,54(1)：11-20.

[18] LIU P H, LU X W. An improved approximation algorithm for single machine scheduling with job delivery[J]. Theoretical Computer Science,2011,412(3):270-274.

[19] HU J L, LUO T B, SU X T, et al. Machine scheduling with a maintenance interval and job delivery coordination[M]//Wang J X, Yap C. Frontier in Algorithmics. Berlin: Springer,2015:104-114

[21] 姚恩瑜,何勇,陈仕平.数学规划与组合优化[M].杭州：浙江大学出版社，2001：104-114.

(责任编辑： 康 锋)

Processing and Transportation Coordination Scheduling of Machine with Periodic Maintenance

HUJueliang,YANGJiawen,SUXiaotong,DONGJianming

(School of Sciences, Zhejiang Sci-Tech University, Hangzhou 310018, China)

A new single machine scheduling problem with periodic maintenance and workpiece delivery coordination is considered in the paper. In this problem, the machine needs periodic maintenance, and the interrupted workpiece in maintenance period cannot be recovered. The workpieces have different size, and certain proportional relation exists between workpiece processing time and physical size. A batch of workpieces can only be processed in each maintain period. The finished workpieces need to be delivered to the customer by a vehicle with capacity limitation. The objective of algorithm is to minimize the duration from finishing all workpieces to delivery to the customer. We first prove that the problem is NP-hard problem. Then, we provide a polynomial time approximation algorithm and prove the worst case boundary of this algorithm is not greater than 5/3.

single machine; maintenance period; non-recovery; approximation algorithm

10.3969/j.issn.1673-3851.2016.11.026

2015-11-30

国家自然科学基金项目(11471286，11501512)；浙江理工大学科研启动经费项目(13062171-Y)

胡觉亮(1958-)，男，浙江杭州人，教授，主要从事运筹学、组合优化方面的研究。

董建明, E-mail：djm226@163.com

O224

A

1673- 3851 (2016) 06- 0951- 006 引用页码： 110803