可移動(dòng)周期性維護(hù)排序問題的算法研究

華榮偉，潘虹，嚴(yán)甜海

（1.杭州醫(yī)學(xué)院，浙江 杭州 310053；2.浙江大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，浙江 杭州 310058）

0 引言

在實(shí)際生產(chǎn)中，可能因機(jī)器發(fā)生故障在一段時(shí)間內(nèi)不能加工工件，也可能因預(yù)防性檢修暫時(shí)停止加工，這就引出了在機(jī)器維護(hù)時(shí)段的排序問題。對(duì)機(jī)器在維護(hù)時(shí)段的排序問題研究始于20 世紀(jì)80 年代［1-2］，相關(guān)模型和結(jié)果可參考綜述文獻(xiàn)［3-5］。根據(jù)工件在加工過程中因機(jī)器維護(hù)被打斷后的不同處理方式，分為三類［4］：（1）維護(hù)時(shí)段結(jié)束后，已經(jīng)完成的部分作廢，需重新加工該工件，稱不可恢復(fù)（nonresumable）；（2）維護(hù)時(shí)段結(jié)束后，只需繼續(xù)加工該工件尚未完成的部分，稱可恢復(fù)（resumable）；（3）維護(hù)時(shí)段結(jié)束后，除繼續(xù)加工該工件尚未完成的部分，還需處理已完成的部分，稱半可恢復(fù)（semiresumable）。下文若不特別說明，所涉及的均為不可恢復(fù)問題。根據(jù)機(jī)器維護(hù)時(shí)段是否具有規(guī)律性，分為周期性維護(hù)（periodic maintenance）和非周期性維護(hù)。在周期性維護(hù)中，同一臺(tái)機(jī)器兩個(gè)相鄰的維護(hù)時(shí)段之間具有某種規(guī)律。目前已有研究的模型大致可分為三類：相鄰維護(hù)時(shí)段之間間隔恰為T，稱為不可移動(dòng)［6］；相鄰維護(hù)時(shí)段之間間隔不超過T，稱為可移動(dòng)［7］；相鄰維護(hù)時(shí)段之間間隔不小于-T，不超過-T，稱為雙向可移動(dòng)［8］。一般假定維護(hù)時(shí)長(zhǎng)t 為一固定值。對(duì)非周期性維護(hù)問題，一般均假設(shè)每臺(tái)機(jī)器至多只有一個(gè)維護(hù)時(shí)段，否則很可能不存在最壞情況比為常數(shù)的近似算法［9］。因此，對(duì)有多個(gè)維護(hù)時(shí)段的周期性維護(hù)問題研究更困難，研究成果也相對(duì)較少。對(duì)于單臺(tái)機(jī)、目標(biāo)為極小化工件最大完工時(shí)間（makespan）、不可移動(dòng)周期性維護(hù)問題，JI 等［6］證明了當(dāng)時(shí)，除非P=NP，否則不存在最壞情況比小于2 的多項(xiàng)式時(shí)間近似算法，而最長(zhǎng)加工時(shí)間優(yōu)先（longest processing time，LPT）算法的最壞情況比恰為2。YU 等［10］以最優(yōu)解所含維護(hù)次數(shù)為參數(shù)，給出了多個(gè)算法的參數(shù)最壞情況比。對(duì)單臺(tái)機(jī)、目標(biāo)為極小化總完工時(shí)間、可移動(dòng)周期性維護(hù)問題，QI 等［7］證明了當(dāng)t ＞T 時(shí)，問題是強(qiáng)NP-難的。QI［11］證明了最短加工時(shí)間優(yōu)先（shortest processing time，SPT）算法的最壞情況比至少為，至多為。若目標(biāo)為極小化工件最大完工時(shí)間、維護(hù)時(shí)段為雙向可移動(dòng)，XU 等［12］證明了不存在最壞情況比小于2 的多項(xiàng)式時(shí)間近似算法。CHEN［8］給出了最壞情況比恰為2 的算法。

平行機(jī)周期性維護(hù)排序問題以兩臺(tái)同型機(jī)、目標(biāo)為極小化工件最大完工時(shí)間為主。對(duì)只有一臺(tái)機(jī)器需要周期性維護(hù)且不可移動(dòng)、另一臺(tái)機(jī)器可持續(xù)加工的問題，XU 等［13］證明了列表排序（list scheduling，LS）算法和LPT 算法的最壞情況比分別為2 和。LI 等［14］給出了最壞情況比為的算法。對(duì)該問題的可恢復(fù)情形，同樣存在最壞情況比為的算法。當(dāng)兩臺(tái)機(jī)器均需周期性維護(hù)時(shí)，若維護(hù)時(shí)段不可移動(dòng)，SUN 等［15］給出了最壞情況比為的算法。若維護(hù)時(shí)段雙向可移動(dòng)，XU 等［16］給出了最壞情況比為的算法，并證明了若P ≠NP，則不存在最壞情況比小于2 的多項(xiàng)式時(shí)間算法。對(duì)兩臺(tái)同型機(jī)，維護(hù)時(shí)段可移動(dòng)、目標(biāo)為極小化總完工時(shí)間的問題，SUN 等［15］給出了最壞情況比為的算法。LIU 等［17］分別研究了m臺(tái)同型機(jī)和兩臺(tái)同類機(jī)的排序問題，其中一臺(tái)機(jī)器存在不可移動(dòng)周期性維護(hù)時(shí)段，其他機(jī)器均可持續(xù)加工，目標(biāo)為極小化工件最大完工時(shí)間，給出了該問題相應(yīng)的算法和最壞情況比。

1 可移動(dòng)周期性維護(hù)排序問題

1.1 可移動(dòng)周期性維護(hù)排序問題介紹

主要研究?jī)膳_(tái)同型機(jī)需周期性維護(hù)且維護(hù)時(shí)段可移動(dòng)、工件不可恢復(fù)、目標(biāo)為極小化工件最大完工時(shí)間的排序問題。具體地，在兩臺(tái)機(jī)器M1，M2上分別安排n 個(gè)工件J={J1，J2，…，Jn}進(jìn)行加工，工件Jj的加工時(shí)長(zhǎng)為pj。每臺(tái)機(jī)器連續(xù)加工時(shí)長(zhǎng)不超過T后需進(jìn)行一次時(shí)長(zhǎng)為t 的維護(hù)，記。稱每臺(tái)機(jī)器上每個(gè)工件的連續(xù)加工時(shí)段為加工區(qū)間，k=1，2，…，共有k 個(gè)加工區(qū)間，如圖1 所示。本文將給出算法的參數(shù)形式的最壞情況比。

圖1 需周期性維護(hù)且維護(hù)時(shí)段可移動(dòng)的兩臺(tái)同型機(jī)Fig.1 The two parallel machines with flexible periodic maintenance activities

1.2 裝箱問題與FFD 算法

可移動(dòng)周期性維護(hù)排序問題與裝箱問題類似。裝箱問題（bin-packing）［18］描述如下：

有一組物品L={a1，a2，…，an}，物品ai的大小s(ai)∈(0，T]，需將這些物品裝入容量為T 的箱子，問至少需要啟用幾只箱子？裝箱問題也是NP-難的，本文主要涉及裝箱問題的按物品大小遞減的最先用（first fit decreasing，F(xiàn)FD）算法。

對(duì)物品重新排序：s(a1)≥s(a2)≥…≥s(an)。將物品ai（i=1，2，…，n）依次裝入能容納序號(hào)最小的箱子。具體地，如果已經(jīng)啟用的箱子中存在能容納ai的箱子，則將ai放入滿足此性質(zhì)的序號(hào)最小的箱子，如果不存在，則將ai放入未啟用的序號(hào)最小的箱子。

其中，Bi表示第i 個(gè)啟用的箱子，也表示放入第i 個(gè)箱子中物品的集合，S(Bi)為裝入該箱子中物品的大小之和。

引理2 若，則，…，Bb中的物品大小均不超過。

引理2 給出了FFD 算法的基本性質(zhì)，證明見文獻(xiàn)［18］。

由引理2，可對(duì)物品之和的大小做估計(jì)。

證明（i）由FFD 算法，可知對(duì)任意的1 ≤i ＜j ≤b，有S(Bi)+S(Bj)＞T，進(jìn)而有

由S(Bb-1)+S(Bb)＞T，可知

證畢！

1.3 P2||Cmax 及完全多項(xiàng)式時(shí)間近似方案（FPTAS）

算法將調(diào)用P2||Cmax問題的近似方案，P2||Cmax即兩臺(tái)同型機(jī)、機(jī)器不用維護(hù)、目標(biāo)為極小化工件最大完工時(shí)間。SAHNI［20］給出了該問題完全多項(xiàng)式時(shí)間的近似方案（FPTAS），其最壞情況比為1+ε，時(shí)間復(fù)雜度為實(shí)例規(guī)模與的二元多項(xiàng)式函數(shù)，其中ε為任意小的正數(shù)。

1.4 符號(hào)說明

用Cmax(σ)表示排序σ 的最大完工時(shí)間，Li(σ)表示在機(jī)器Mi上工件的最大完工時(shí)間，Pi(σ)表示在Mi上工件的總加工時(shí)間，也稱Mi的負(fù)載。用bi(σ)表示在Mi上的加工區(qū)間數(shù)，Ji，k(σ)表示在Mi上第k個(gè)加工區(qū)間內(nèi)加工的工件集。對(duì)任意工件集S，用P(S)表示工件集S 中工件的總加工時(shí)間。用CH表示算法H 給出的排序的目標(biāo)值，C*為最優(yōu)值。

2 算法的難近似性

定理1若兩臺(tái)機(jī)器中的任一臺(tái)每連續(xù)加工時(shí)長(zhǎng)至多為T 后需進(jìn)行一次時(shí)長(zhǎng)為t 的維護(hù)，則不存在最壞情況比小于1+β 的多項(xiàng)式時(shí)間近似算法，除非P=NP。

證明反證法。假設(shè)存在多項(xiàng)式時(shí)間近似算法A，其最壞情況比為α ＜1+β。用NP-完全的劃分問題［21］進(jìn)行歸約，劃分問題可描述為：給定n 個(gè)正整數(shù)e1，e2，…，en，滿足，是否存在子集X ?S，使得。

給定劃分問題的一個(gè)實(shí)例I，按照下述方法構(gòu)造原問題的實(shí)例I'。

令T=B，t=βB，有兩臺(tái)機(jī)器和n 個(gè)工件，其中工件Ji的加工時(shí)間為pi=ei(i=1，2，…，n)，顯然可以在多項(xiàng)式時(shí)間內(nèi)完成歸約。若實(shí)例I 的答案為存在，則令J1(σ)={Ji|ei∈X}，J2(σ)={Ji|ei∈SX}，可得最大完工時(shí)間為T 的排序，故實(shí)例I'的最優(yōu)最大完工時(shí)間C*≤T。

對(duì)實(shí)例I'，由算法A 得到的排序?yàn)棣褹，最大完工時(shí)間為CA。不妨假設(shè)σA滿足性質(zhì)：

如果對(duì)于某臺(tái)機(jī)器Mi，bi(σA)＞1，則

若不然，可通過合并加工時(shí)段滿足該性質(zhì)，使上述步驟在多項(xiàng)式時(shí)間內(nèi)完成且目標(biāo)值不增加。

如果CA≤T，則有Li(σA)≤T。由

如果CA＞T，不妨假設(shè)L1(σA)＞T。顯然可得P1(σA)≥P1(J1，1(σA))+P2(J1，2(σA))，b1(σA)≥2。因此L1(σA)＞t+T。由最壞情況比的定義，可知

因此劃分問題實(shí)例I 的答案是不存在。

至此，得到了劃分問題的多項(xiàng)式時(shí)間算法，這與劃分問題是NP-完全的矛盾。

證畢！

3 算法和最壞情況比分析

3.1 算 法

由定理1 可知，若不將算法的最壞情況比表示為β 的函數(shù)，當(dāng)β 為非固定數(shù)時(shí)，任意算法的最壞情況比均不是有限常數(shù)。

下面給出一種近似算法H，其最壞情況比為β的一個(gè)分段函數(shù)。

3.1.1 子過程Greedy

設(shè)在當(dāng)前排序中，機(jī)器Mi的完工時(shí)間為L(zhǎng)i，Mi有bi個(gè)加工區(qū)間，在第k 個(gè)加工區(qū)間內(nèi)加工的工件子集為Ji，k，k=1，2，…，bi，i=1，2。當(dāng)前工件子集為Bj：

（i）對(duì)i=1，2，記li為可以在Mi上加工的最早加工區(qū)間序號(hào)，為Bj在Mi上加工Mi的最早完工時(shí)間。具體地，如果存在k ≤bi，使得P(Bj)+P(Ji，k)≤T，則令

若這樣的k 不存在，則令li=bi+1，

3.1.2 算法H

運(yùn)用復(fù)合思想，當(dāng)工件總加工時(shí)間較短時(shí)，調(diào)用P2||Cmax的FPTAS；當(dāng)工件總加工時(shí)間較長(zhǎng)時(shí)，先分批，然后將各批作為一個(gè)整體在某個(gè)加工區(qū)間內(nèi)加工。

（i）將工件加工時(shí)間視為物品的大小，T 為箱子容量，構(gòu)造裝箱問題實(shí)例，并用FFD 算法進(jìn)行分批。記所得批數(shù)為 b，各批工件子集為B1，B2，…，Bb-1，Bb，不妨設(shè)P(B1)≥P(B2)≥…≥P(Bb)。

（ii）若P ≤2T，調(diào)用P2||Cmax的FPTAS，若在其中一臺(tái)機(jī)器上工件總加工時(shí)間大于T，則在該機(jī)器上增加一個(gè)維護(hù)時(shí)段，以使在維護(hù)時(shí)段前后加工的工件總加工時(shí)間不超過T。

（iii）若 P ＞2T，則對(duì)子集族{Bi} (i=1，2，…，b) 應(yīng)用子過程Greedy。

3.2 最壞情況比

下面給出算法H 的最壞情況比的上界。將算法得到的排序記為σ，先給出幾個(gè)引理。

引理4若P ＜2T，則。

證明考慮工件集為J 的兩臺(tái)無維護(hù)時(shí)段同型機(jī)排序問題，記用FPTAS 求解該實(shí)例所得的排序?yàn)棣褾，最優(yōu)排序?yàn)棣?。由FPTAS 的定義，可知Cmax(σF)≤(1+ε)Cmax(σ')。注意到有維護(hù)時(shí)段問題的最優(yōu)值不小于無維護(hù)時(shí)段問題的最優(yōu)值，即Cmax(σ')≤C*。

若在σF中，兩臺(tái)機(jī)器的負(fù)載均不超過T，則兩臺(tái)機(jī)器均不需要引入維護(hù)時(shí)段，因此

反之，假設(shè)至少有一臺(tái)機(jī)器負(fù)載大于T，注意到P ≤2T，至多有一臺(tái)機(jī)器負(fù)載超過T，不妨假設(shè)為機(jī)器M1。此時(shí)在機(jī)器M1上需要增加一個(gè)維護(hù)時(shí)段，因此CH≤Cmax(σF)+t。如果C*≤(1-ε)T，則

這與σF中M1的負(fù)載大于T 矛盾，所以C*＞(1-ε)T。此時(shí)

證畢！

引理5（i）記b*=b1(σ*)+b2(σ*)，則最優(yōu)排序；

（ii）若b*≥3，則。

證明（i）顯然成立。

（ii）若b*≥4，由（i）可知（ii）成立。若b*=3，則在σ*中完工時(shí)間較長(zhǎng)的機(jī)器上，不妨假設(shè)為M1，必有一個(gè)維護(hù)時(shí)段。若不然，則，顯然有

這與M1完工時(shí)間較長(zhǎng)矛盾。因此，必有b1(σ*)=2且b2(σ*)=1。顯然可得P1(σ*)＞T ≥P2(σ*)，否則，M1不需要維護(hù)。因此

證畢！

記

由于ε 可任意接近于0，定義

顯然f0(β)≤f (β)，且f0(β)與f (β)可任意接近。圖2 為函數(shù)f0(β)的圖，可得f (β)的性質(zhì)：

圖2 函數(shù)f0(β)的圖Fig.2 The function image of f0(β)

證畢！

定理2若兩臺(tái)機(jī)器均需周期性維護(hù)，每臺(tái)機(jī)器連續(xù)加工時(shí)長(zhǎng)至多為T 后需進(jìn)行一次時(shí)長(zhǎng)為t 的維護(hù)，算法H 的最壞情況比不超過f (β)，其中，β=。

證明根據(jù)P 的大小分情況討論。

若P ＞2T，則b*≥≥3。

若b=3，子過程Greedy 必將B1安排在M1上加工，將B2和B3安排在M2上加工。因此，

由引理5（ii）和P ≥3P(B3)，有

如果B4批決定最大完工時(shí)間，則有

由L1(σ)+L2(σ)=P+(b-2)t=P+2t，有

由引理5（ii）、式（1）和P ≥4P(B4)，有

如果B3批為決定最大完工時(shí)間，類似地可得

由引理5（ii）、式（2）和P ≥3P(B3)，有

綜上，在該情形下，由引理6（i），可得

若b ≥5 且Bb決定最大完工時(shí)間，不妨假設(shè)CH=L1(σ)。由Greedy 規(guī)則，可得

由L1(σ)+L2(σ)=P+(b-2)t，可得

由引理5（i）和P ≥bP(Bb)，有

其中，最后一個(gè)不等式由b ≥5 得到。

由引理6（ii），若b ≥5 且由最后一批決定最大完工時(shí)間，則有

若b ≥5 且Bb批不決定最大完工時(shí)間，則σ 中Bb-1批一定是決定最大完工時(shí)間的。若不然，假設(shè)σ 中L1(σ)＜L2(σ)，將Bb，Bb-1，…，Bl同時(shí)安排在M1上、Bl-1安排在M2上加工，其中l(wèi) ≤b-1。假設(shè)在安排Bl-1時(shí)，Mi的完工時(shí)間為L(zhǎng)'i(i=1，2)，則

而由FFD 算法規(guī)則，可知

這與Bl-1批被安排在M2上加工矛盾。

考慮以J{Bb}為工件集的實(shí)例I'，用FFD 算法對(duì)J{Bb}進(jìn)行分批，所得工件子集恰為B1，B2，…，Bb-1。對(duì)實(shí)例I'，注意到此時(shí)b-1 ≥4，運(yùn)用算法H所得排序σ'的最大完工時(shí)間與實(shí)例I 的排序σ 的最大完工時(shí)間相同，且σ'中Bb-1批決定最大完工時(shí)間，而C*(I')≤C*(I)，因此，由式（3）或式（5），有

證畢！

4 結(jié)論

對(duì)于可移動(dòng)周期性維護(hù)排序問題，證明了其不存在最壞情況比小于的多項(xiàng)式時(shí)間近似算法，除非P=NP，同時(shí)給出了該問題的近似算法，證明了其最壞情況比不超過。