華榮偉,潘虹,嚴甜海
(1.杭州醫(yī)學院,浙江 杭州 310053;2.浙江大學 數(shù)學科學學院,浙江 杭州 310058)
在實際生產中,可能因機器發(fā)生故障在一段時間內不能加工工件,也可能因預防性檢修暫時停止加工,這就引出了在機器維護時段的排序問題。對機器在維護時段的排序問題研究始于20 世紀80 年代[1-2],相關模型和結果可參考綜述文獻[3-5]。根據(jù)工件在加工過程中因機器維護被打斷后的不同處理方式,分為三類[4]:(1)維護時段結束后,已經完成的部分作廢,需重新加工該工件,稱不可恢復(nonresumable);(2)維護時段結束后,只需繼續(xù)加工該工件尚未完成的部分,稱可恢復(resumable);(3)維護時段結束后,除繼續(xù)加工該工件尚未完成的部分,還需處理已完成的部分,稱半可恢復(semiresumable)。下文若不特別說明,所涉及的均為不可恢復問題。根據(jù)機器維護時段是否具有規(guī)律性,分為周期性維護(periodic maintenance)和非周期性維護。在周期性維護中,同一臺機器兩個相鄰的維護時段之間具有某種規(guī)律。目前已有研究的模型大致可分為三類:相鄰維護時段之間間隔恰為T,稱為不可移動[6];相鄰維護時段之間間隔不超過T,稱為可移動[7];相鄰維護時段之間間隔不小于-T,不超過-T,稱為雙向可移動[8]。一般假定維護時長t 為一固定值。對非周期性維護問題,一般均假設每臺機器至多只有一個維護時段,否則很可能不存在最壞情況比為常數(shù)的近似算法[9]。因此,對有多個維護時段的周期性維護問題研究更困難,研究成果也相對較少。對于單臺機、目標為極小化工件最大完工時間(makespan)、不可移動周期性維護問題,JI 等[6]證明了當時,除非P=NP,否則不存在最壞情況比小于2 的多項式時間近似算法,而最長加工時間優(yōu)先(longest processing time,LPT)算法的最壞情況比恰為2。YU 等[10]以最優(yōu)解所含維護次數(shù)為參數(shù),給出了多個算法的參數(shù)最壞情況比。對單臺機、目標為極小化總完工時間、可移動周期性維護問題,QI 等[7]證明了當t >T 時,問題是強NP-難的。QI[11]證明了最短加工時間優(yōu)先(shortest processing time,SPT)算法的最壞情況比至少為,至多為。若目標為極小化工件最大完工時間、維護時段為雙向可移動,XU 等[12]證明了不存在最壞情況比小于2 的多項式時間近似算法。CHEN[8]給出了最壞情況比恰為2 的算法。
平行機周期性維護排序問題以兩臺同型機、目標為極小化工件最大完工時間為主。對只有一臺機器需要周期性維護且不可移動、另一臺機器可持續(xù)加工的問題,XU 等[13]證明了列表排序(list scheduling,LS)算法和LPT 算法的最壞情況比分別為2 和。LI 等[14]給出了最壞情況比為的算法。對該問題的可恢復情形,同樣存在最壞情況比為的算法。當兩臺機器均需周期性維護時,若維護時段不可移動,SUN 等[15]給出了最壞情況比為的算法。若維護時段雙向可移動,XU 等[16]給出了最壞情況比為的算法,并證明了若P ≠NP,則不存在最壞情況比小于2 的多項式時間算法。對兩臺同型機,維護時段可移動、目標為極小化總完工時間的問題,SUN 等[15]給出了最壞情況比為的算法。LIU 等[17]分別研究了m臺同型機和兩臺同類機的排序問題,其中一臺機器存在不可移動周期性維護時段,其他機器均可持續(xù)加工,目標為極小化工件最大完工時間,給出了該問題相應的算法和最壞情況比。
主要研究兩臺同型機需周期性維護且維護時段可移動、工件不可恢復、目標為極小化工件最大完工時間的排序問題。具體地,在兩臺機器M1,M2上分別安排n 個工件J={J1,J2,…,Jn}進行加工,工件Jj的加工時長為pj。每臺機器連續(xù)加工時長不超過T后需進行一次時長為t 的維護,記。稱每臺機器上每個工件的連續(xù)加工時段為加工區(qū)間,k=1,2,…,共有k 個加工區(qū)間,如圖1 所示。本文將給出算法的參數(shù)形式的最壞情況比。
圖1 需周期性維護且維護時段可移動的兩臺同型機Fig.1 The two parallel machines with flexible periodic maintenance activities
可移動周期性維護排序問題與裝箱問題類似。裝箱問題(bin-packing)[18]描述如下:
有一組物品L={a1,a2,…,an},物品ai的大小s(ai)∈(0,T],需將這些物品裝入容量為T 的箱子,問至少需要啟用幾只箱子?裝箱問題也是NP-難的,本文主要涉及裝箱問題的按物品大小遞減的最先用(first fit decreasing,F(xiàn)FD)算法。
對物品重新排序: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,可知
證畢!
算法將調用P2||Cmax問題的近似方案,P2||Cmax即兩臺同型機、機器不用維護、目標為極小化工件最大完工時間。SAHNI[20]給出了該問題完全多項式時間的近似方案(FPTAS),其最壞情況比為1+ε,時間復雜度為實例規(guī)模與的二元多項式函數(shù),其中ε為任意小的正數(shù)。
用Cmax(σ)表示排序σ 的最大完工時間,Li(σ)表示在機器Mi上工件的最大完工時間,Pi(σ)表示在Mi上工件的總加工時間,也稱Mi的負載。用bi(σ)表示在Mi上的加工區(qū)間數(shù),Ji,k(σ)表示在Mi上第k個加工區(qū)間內加工的工件集。對任意工件集S,用P(S)表示工件集S 中工件的總加工時間。用CH表示算法H 給出的排序的目標值,C*為最優(yōu)值。
定理1若兩臺機器中的任一臺每連續(xù)加工時長至多為T 后需進行一次時長為t 的維護,則不存在最壞情況比小于1+β 的多項式時間近似算法,除非P=NP。
證明反證法。假設存在多項式時間近似算法A,其最壞情況比為α <1+β。用NP-完全的劃分問題[21]進行歸約,劃分問題可描述為:給定n 個正整數(shù)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'的最優(yōu)最大完工時間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-完全的矛盾。
證畢!
由定理1 可知,若不將算法的最壞情況比表示為β 的函數(shù),當β 為非固定數(shù)時,任意算法的最壞情況比均不是有限常數(shù)。
下面給出一種近似算法H,其最壞情況比為β的一個分段函數(shù)。
3.1.1 子過程Greedy
設在當前排序中,機器Mi的完工時間為Li,Mi有bi個加工區(qū)間,在第k 個加工區(qū)間內加工的工件子集為Ji,k,k=1,2,…,bi,i=1,2。當前工件子集為Bj:
(i)對i=1,2,記li為可以在Mi上加工的最早加工區(qū)間序號,為Bj在Mi上加工Mi的最早完工時間。具體地,如果存在k ≤bi,使得P(Bj)+P(Ji,k)≤T,則令
若這樣的k 不存在,則令li=bi+1,
3.1.2 算法H
運用復合思想,當工件總加工時間較短時,調用P2||Cmax的FPTAS;當工件總加工時間較長時,先分批,然后將各批作為一個整體在某個加工區(qū)間內加工。
(i)將工件加工時間視為物品的大小,T 為箱子容量,構造裝箱問題實例,并用FFD 算法進行分批。記所得批數(shù)為 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。
下面給出算法H 的最壞情況比的上界。將算法得到的排序記為σ,先給出幾個引理。
引理4若P <2T,則。
證明考慮工件集為J 的兩臺無維護時段同型機排序問題,記用FPTAS 求解該實例所得的排序為σF,最優(yōu)排序為σ'。由FPTAS 的定義,可知Cmax(σF)≤(1+ε)Cmax(σ')。注意到有維護時段問題的最優(yōu)值不小于無維護時段問題的最優(yōu)值,即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(σ*),則最優(yōu)排序;
(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 為函數(shù)f0(β)的圖,可得f (β)的性質:
圖2 函數(shù)f0(β)的圖Fig.2 The function image of f0(β)
證畢!
定理2若兩臺機器均需周期性維護,每臺機器連續(xù)加工時長至多為T 后需進行一次時長為t 的維護,算法H 的最壞情況比不超過f (β),其中,β=。
證明根據(jù)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 規(guī)則,可得
由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(wèi) ≤b-1。假設在安排Bl-1時,Mi的完工時間為L'i(i=1,2),則
而由FFD 算法規(guī)則,可知
這與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),有
證畢!
對于可移動周期性維護排序問題,證明了其不存在最壞情況比小于的多項式時間近似算法,除非P=NP,同時給出了該問題的近似算法,證明了其最壞情況比不超過。