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

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

?

機(jī)器帶周期性維護(hù)時(shí)段的加工與運(yùn)輸協(xié)同排序問題

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

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

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

單臺機(jī)；維護(hù)時(shí)段；不可恢復(fù)；近似算法

0 引 言

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

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

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

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

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

1 問題描述及符號定義

2 近似算法

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

(1)

(2)

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

算法H:

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

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

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

對算法H中批次數(shù)bH=1的情況進(jìn)行討論，若bH=1,則b*=bH,由算法H可得CH=C*，所以不妨假設(shè)bH≥2。當(dāng)批次數(shù)bH≥2時(shí)，令x為算法解中最后一個(gè)批次的總加工時(shí)間，根據(jù)一個(gè)運(yùn)輸周期時(shí)長T與一個(gè)加工時(shí)段和一個(gè)維護(hù)時(shí)段之和即E+I的大小比較，得到不同形式的算法解。當(dāng)T

下面以一個(gè)具有6個(gè)工件的實(shí)例對算法H進(jìn)行說明。

實(shí)例：給出含6個(gè)工件的集合{J1,J2,…,J6}，工件加工時(shí)間分別為p1=2，p2=8，p3=7，p4=8，p5=8，p6=4，機(jī)器的加工時(shí)段長度E=12，維護(hù)時(shí)段長度I=6。運(yùn)輸工具的容量大小z=6，運(yùn)輸時(shí)間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所示。由圖可知運(yùn)行算法H得到的目標(biāo)函數(shù)值CH=92。

圖1 算法H示例

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

(3)

(4)

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

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

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

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

3 最壞情況界的證明

本節(jié)證明算法H的最壞情況界不大于5/3。

證明：因?yàn)門

a)I+x≤T

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

(5)

下面按照b*的不同取值進(jìn)行討論。

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

b)T

(6)

下面按照b*的不同取值進(jìn)行討論。

若b*=1，則bH=b*，此時(shí)CH=C*。

下面僅討論b*≥2且滿足bH>b*的情況。

證明：當(dāng)T≥E+I時(shí)，令y為該情況下最優(yōu)解中第一個(gè)批次的總加工時(shí)間。算法解為：CH=bHT+E，最優(yōu)解C*滿足C*≥b*T+y，于是有：

(7)

下面按照b*的不同取值進(jìn)行討論。

若b*=1，則bH=b*，此時(shí)CH=C*。

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

4 結(jié) 論

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

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

[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] 汪磊揚(yáng)，劉朝暉.帶批運(yùn)輸?shù)膬膳_同型機(jī)排序問題的改進(jìn)算法[J].運(yùn)籌學(xué)學(xué)報(bào)，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ù)學(xué)規(guī)劃與組合優(yōu)化[M].杭州：浙江大學(xué)出版社，2001：104-114.

(責(zé)任編輯： 康 鋒)

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

國家自然科學(xué)基金項(xiàng)目(11471286，11501512)；浙江理工大學(xué)科研啟動(dòng)經(jīng)費(fèi)項(xiàng)目(13062171-Y)

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

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

O224

A

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