胡覺亮，楊佳雯，蘇曉彤，董建明

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

?

機器帶周期性維護時段的加工與運輸協(xié)同排序問題

胡覺亮，楊佳雯，蘇曉彤，董建明

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

研究了一類機器帶周期性維護時段且完工工件需要運輸?shù)男滦团判騿栴}。在該問題中，機器需要進行周期性的維護，且被維護時段打斷的工件加工不可恢復；工件具有不同的尺寸且工件的加工時間與物理尺寸大小具有一定的比例關(guān)系，每個維護時段內(nèi)只允許加工一個批次的工件；加工完的工件需要由一輛帶有容量限制的運輸工具運往客戶。算法的目標是極小化所有工件加工完成并運送到客戶的時間。證明了該問題是強NP-Hard問題，設計了該問題的一個多項式時間近似算法，并證明了該算法的最壞情況界不大于5/3。

單臺機；維護時段；不可恢復；近似算法

0 引 言

機器帶維護時段的排序問題和加工與運輸協(xié)同的排序問題是兩類重要的排序問題。由于這兩類排序問題在生產(chǎn)制造及供應鏈管理中具有廣闊的應用前景，所以近年來得到了廣泛的研究。而機器帶維護時段的加工與運輸協(xié)同的排序問題，是這兩類排序問題的結(jié)合，同樣具有重要的應用價值并得到了一定的關(guān)注和研究。

機器帶維護時段的排序問題，根據(jù)機器上維護時段的個數(shù)可分為單維護時段排序問題和周期性維護時段排序問題。關(guān)于帶單維護時段的排序問題，對于考慮工件的加工一旦被維護時段打斷且加工不可恢復的情況，目前已有很多好的結(jié)果。當目標函數(shù)為極小化最大完工時間時，Lee[1]利用LPT規(guī)則提出一個最壞情況界不大于4/3的緊界算法。He等[2]對同樣問題提出一個多項式時間近似方案。當目標函數(shù)為極小化總完工時間時，Lee等[3]證明SPT算法的緊界不大于9/7。Sadfi等[4]提出了改進的MSPT算法，并證明算法的緊界為20/17。He等[5]提出了一個多項式時間近似方案。Low等[6]對于機器帶周期性維護時段的問題，針對目標函數(shù)為極小化最大完工時間的情況，提出了FFD算法的一些重要性質(zhì)。Yu等[7]比較了LS算法、LPT算法和MLPT算法對最壞情況界的影響。Lee等[8]對目標函數(shù)為極小化總誤工數(shù)的問題提出了一種兩階段啟發(fā)式算法。Liao等[9]對目標函數(shù)是極小化最大延誤的問題提出了一個分支定界法去尋找最優(yōu)排序方案，以及一個針對存在大工件情況的啟發(fā)式算法。Chen[10]對于目標函數(shù)是極小化總誤工數(shù)的問題，提出了一種有效的啟發(fā)式算法，同時還提出一個分支定界法來尋找最優(yōu)排序方案。當目標函數(shù)為極小化最大完工時間的問題，Ji等[11]證明了經(jīng)典LPT算法的最壞情況界為2。Chen[12]提供了一個二進制整數(shù)規(guī)劃方案，以及針對大工件存在情況下的一個啟發(fā)式算法。

對于加工與運輸協(xié)同的排序問題，目前的研究主要集中在工件具有不同的物理尺寸這種重要情形，主要的研究成果有：Chang等[13]首先建立了該問題的模型，給出了單機環(huán)境和兩臺平行機環(huán)境下的近似算法，同時給出了單機環(huán)境下具有兩個客戶情況下的近似算法；Zhong等[14]給出了單機環(huán)境和兩臺平行機環(huán)境下的改進算法；Lu等[15]給出了單機環(huán)境下該類問題的最好的近似算法；汪磊揚等[16]又進一步改進了兩臺平行機環(huán)境下的該類問題的結(jié)果，得到改進的近似算法界接近3/2。

對于機器帶維護時段同時加工完的工件需要運輸?shù)较鄳蛻舻膯栴}，即機器帶維護時段的加工與運輸協(xié)同的排序問題，目前研究成果比較少，主要成果有：Wang等[17]在單臺機工件不可恢復單維護時段以及運輸工具容量有限，即最多只能裝下k個工件的情況下，提出目標函數(shù)為極小化最大完工時間問題的近似算法，并得到最壞情況界不大于3/2；對于同一目標函數(shù)，Liu等[18]對于工件帶有釋放時間和尺寸大小屬性的帶運輸排序問題，又進一步提出改進的近似算法，使得最壞情況界不大于3/2；Hu等[19]針對單臺機單維護時段以及運輸工具容量有限情況下的問題，提出目標函數(shù)為極小化最大完工時間問題的近似算法，得到最壞情況界為2，并證明該情況界是緊的。

本文研究機器帶維護時段的加工與運輸協(xié)同的排序問題，考慮工件具有不同尺寸且運輸工具具有容量限制的情況。與上述機器帶單維護時段的加工與運輸協(xié)同的排序問題不同，本文考慮更為復雜的機器帶有周期性維護時段的情況，且限制機器的加工時段長度與工件的尺寸之間具有一定的比例關(guān)系。由于該問題是強NP-Hard且具有3/2的難近似性，本文給出了該問題的一個近似算法，并證明該算法的最壞情況界不大于5/3。

1 問題描述及符號定義

2 近似算法

本文算法用到經(jīng)典一維裝箱問題的FFD算法。FFD算法首先將物品(工件)按照尺寸大小從大到小排列，然后將工件按序逐個裝箱。若已打開的箱子無法裝入當前工件時則另開一個新箱子。根據(jù)裝箱問題的FFD算法的性質(zhì)[20-21]，可得:

(1)

(2)

其中：FFD(I)表示對于裝箱實例運用FFD算法得到的箱子數(shù)，OPT(I)表示最優(yōu)的裝箱數(shù)目。下面將給出問題的一個近似算法，具體算法可以描述為：

算法H:

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

Step2 按FFD算法對工件進行分批，得到批次數(shù)為bH，每個批次記為Bk(k=1,2,…,bH)。

Step4 按批次順序依次加工工件，每個加工時段中只安排一個批次的加工。當運輸工具處于空閑時，除最后一個批次外，每個批次加工完成并等到當前加工時段結(jié)束后對該批次進行運輸。若最后一個批次加工完成時運輸工具空閑則立即對該批次進行運輸。得到算法解記為CH。

對算法H中批次數(shù)bH=1的情況進行討論，若bH=1,則b*=bH,由算法H可得CH=C*，所以不妨假設bH≥2。當批次數(shù)bH≥2時，令x為算法解中最后一個批次的總加工時間，根據(jù)一個運輸周期時長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。執(zhí)行算法H得到：bH=4，B1={J2,J6},B2={J1,J4},B3={J5},B4={J3},P1=12，P2=12，P3=8，P4=7。排序結(jié)果如圖1所示。由圖可知運行算法H得到的目標函數(shù)值CH=92。

圖1 算法H示例

假設該問題的最優(yōu)批次數(shù)為b*，則根據(jù)式(1)和式(2)容易得到：

(3)

(4)

那么當bH>b*時，可以得到如下運行算法H后得到工件批次數(shù)情況的相關(guān)性質(zhì)。

性質(zhì)2[21]：批次b*+1、b*+2、…、bH中至多只有b*-1個工件。

性質(zhì)3：所有放入批次b*+1、b*+2、…、bH中的任意工件的加工時間不超過一個加工時段長度E的1/3。

證明：根據(jù)性質(zhì)2以及工件的加工時間和工件的尺寸大小的比例關(guān)系，可得此性質(zhì)成立。

3 最壞情況界的證明

本節(jié)證明算法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為該情況下最優(yōu)解中第一個批次的總加工時間。算法解為：CH=bHT+E，最優(yōu)解C*滿足C*≥b*T+y，于是有：

(7)

下面按照b*的不同取值進行討論。

若b*=1，則bH=b*，此時CH=C*。

下面僅討論b*≥2且滿足bH>b*的情況。由式(3)可得：

4 結(jié) 論

本文研究了一類機器帶維護時段的加工與運輸協(xié)同的排序問題。該問題是經(jīng)典的帶維護時段排序問題和加工與運輸協(xié)同排序問題的一個組合。在該問題中，工件先在一臺需要周期性維護的機器上進行加工，然后由一輛帶有容量限制的運輸工具分批運往相應的客戶。目標是合理安排工件的加工和運輸，使得工件能夠盡早加工完畢并運往客戶。由于該問題是強NP-Hard問題，所以本文給出了該問題在工件的加工時間和工件的尺寸大小成比例關(guān)系且每個加工時段只可以加工一批工件情況下的一個近似算法。分析了算法的性質(zhì)，并證明了該算法的最壞情況界不大于5/3。

對于該問題的進一步研究，我們將關(guān)注以下兩個方面：一方面是改進本文的算法，使得最壞情況界小于5/3；另一方面是研究工件的加工時間和工件的尺寸大小沒有比例關(guān)系的一般情況下的問題模型。由于不考慮運輸且機器具有周期性維護時段的排序問題具有2的難近似性[11]，即不存在最壞情況界小于2的近似算法，所以該問題也具有2難近似性，這給研究增加了較大的難度。所以研究該類問題的一個最壞情況界接近2的近似算法，例如設計一個最壞情況界為5/2的算法可以作為后續(xù)研究的一個可行目標。

[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] 汪磊揚，劉朝暉.帶批運輸?shù)膬膳_同型機排序問題的改進算法[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] 姚恩瑜,何勇,陳仕平.數(shù)學規(guī)劃與組合優(yōu)化[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)；浙江理工大學科研啟動經(jīng)費項目(13062171-Y)

胡覺亮(1958-)，男，浙江杭州人，教授，主要從事運籌學、組合優(yōu)化方面的研究。

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

O224

A

1673- 3851 (2016) 06- 0951- 006 引用頁碼： 110803