可移動周期性維護排序問題的算法研究

華榮偉，潘虹，嚴甜海

（1.杭州醫學院，浙江 杭州 310053；2.浙江大學 數學科學學院，浙江 杭州 310058）

0 引言

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

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

1 可移動周期性維護排序問題

1.1 可移動周期性維護排序問題介紹

主要研究兩臺同型機需周期性維護且維護時段可移動、工件不可恢復、目標為極小化工件最大完工時間的排序問題。具體地，在兩臺機器M1，M2上分別安排n 個工件J={J1，J2，…，Jn}進行加工，工件Jj的加工時長為pj。每臺機器連續加工時長不超過T后需進行一次時長為t 的維護，記。稱每臺機器上每個工件的連續加工時段為加工區間，k=1，2，…，共有k 個加工區間，如圖1 所示。本文將給出算法的參數形式的最壞情況比。

圖1 需周期性維護且維護時段可移動的兩臺同型機Fig.1 The two parallel machines with flexible periodic maintenance activities

1.2 裝箱問題與FFD 算法

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

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

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

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

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

引理2 給出了FFD 算法的基本性質，證明見文獻［18］。

由引理2，可對物品之和的大小做估計。

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

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

證畢！

1.3 P2||Cmax 及完全多項式時間近似方案（FPTAS）

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

1.4 符號說明

用Cmax(σ)表示排序σ 的最大完工時間，Li(σ)表示在機器Mi上工件的最大完工時間，Pi(σ)表示在Mi上工件的總加工時間，也稱Mi的負載。用bi(σ)表示在Mi上的加工區間數，Ji，k(σ)表示在Mi上第k個加工區間內加工的工件集。對任意工件集S，用P(S)表示工件集S 中工件的總加工時間。用CH表示算法H 給出的排序的目標值，C*為最優值。

2 算法的難近似性

定理1若兩臺機器中的任一臺每連續加工時長至多為T 后需進行一次時長為t 的維護，則不存在最壞情況比小于1+β 的多項式時間近似算法，除非P=NP。

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

給定劃分問題的一個實例I，按照下述方法構造原問題的實例I'。

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

對實例I'，由算法A 得到的排序為σA，最大完工時間為CA。不妨假設σA滿足性質：

如果對于某臺機器Mi，bi(σA)＞1，則

若不然，可通過合并加工時段滿足該性質，使上述步驟在多項式時間內完成且目標值不增加。

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

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

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

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

證畢！

3 算法和最壞情況比分析

3.1 算 法

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

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

3.1.1 子過程Greedy

設在當前排序中，機器Mi的完工時間為Li，Mi有bi個加工區間，在第k 個加工區間內加工的工件子集為Ji，k，k=1，2，…，bi，i=1，2。當前工件子集為Bj：

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

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

3.1.2 算法H

運用復合思想，當工件總加工時間較短時，調用P2||Cmax的FPTAS；當工件總加工時間較長時，先分批，然后將各批作為一個整體在某個加工區間內加工。

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

（ii）若P ≤2T，調用P2||Cmax的FPTAS，若在其中一臺機器上工件總加工時間大于T，則在該機器上增加一個維護時段，以使在維護時段前后加工的工件總加工時間不超過T。

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

3.2 最壞情況比

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

引理4若P ＜2T，則。

證明考慮工件集為J 的兩臺無維護時段同型機排序問題，記用FPTAS 求解該實例所得的排序為σF，最優排序為σ'。由FPTAS 的定義，可知Cmax(σF)≤(1+ε)Cmax(σ')。注意到有維護時段問題的最優值不小于無維護時段問題的最優值，即Cmax(σ')≤C*。

若在σF中，兩臺機器的負載均不超過T，則兩臺機器均不需要引入維護時段，因此

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

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

證畢！

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

（ii）若b*≥3，則。

證明（i）顯然成立。

（ii）若b*≥4，由（i）可知（ii）成立。若b*=3，則在σ*中完工時間較長的機器上，不妨假設為M1，必有一個維護時段。若不然，則，顯然有

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

證畢！

記

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

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

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

證畢！

定理2若兩臺機器均需周期性維護，每臺機器連續加工時長至多為T 后需進行一次時長為t 的維護，算法H 的最壞情況比不超過f (β)，其中，β=。

證明根據P 的大小分情況討論。

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

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

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

如果B4批決定最大完工時間，則有

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

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

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

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

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

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

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

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

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

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

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

而由FFD 算法規則，可知

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

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

證畢！

4 結論

對于可移動周期性維護排序問題，證明了其不存在最壞情況比小于的多項式時間近似算法，除非P=NP，同時給出了該問題的近似算法，證明了其最壞情況比不超過。