帶有不可用區(qū)間中斷可恢復(fù)的平行機排序問題

張 琦, 羅成新

(沈陽師范大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院, 沈陽 110034)

帶有不可用區(qū)間中斷可恢復(fù)的平行機排序問題

張 琦, 羅成新

(沈陽師范大學(xué) 數(shù)學(xué)與系統(tǒng)科學(xué)學(xué)院, 沈陽 110034)

討論帶有不可用區(qū)間且工件中斷可恢復(fù)的兩臺平行機排序問題。其中一臺機器帶有不可用區(qū)間,在不可用區(qū)間內(nèi)不能加工工件。工件在加工時被不可用區(qū)間中斷后,可以在不可用區(qū)間之后繼續(xù)加工。目標(biāo)是最小化加權(quán)總完工時間。這個問題是一般定義下NP-難的,因此需要尋找滿足指定精確度的近似解。首先給出全多項式近似方案的定義,其次提出了一個動態(tài)規(guī)劃的算法,最后利用劃分程序的方法得到了一個全多項式近似方案(FPTAS),該近似方案的時間復(fù)雜性為O(n5L5/ε4),其中:n為輸入工件的個數(shù);L為輸入規(guī)模;ε0為誤差精度。

平行機排序; 不可用區(qū)間; 中斷可恢復(fù); NP-難; 全多項式近似方案

0 引 言

對于經(jīng)典排序問題大多數(shù)做如下假設(shè):任何時間機器都是可以加工工件的。但是在實際生產(chǎn)過程這種假設(shè)條件不能總被滿足。例如:在機器發(fā)生故障或定期維修、保養(yǎng)的一時間段內(nèi)不能加工工件,即產(chǎn)生了不可用區(qū)間,通常將這類問題稱為機器具有可用性限制問題。如果一個工件在不可用區(qū)間之前不能完工,那么該工件可以在不可用區(qū)間之后繼續(xù)加工,稱該工件是中斷可恢復(fù)的。Lee[1]考慮了不同的機器有可用性限制的排序問題。Ji[2]研究的是工件帶有線性退化加工時間的平行機排序問題。此外,文獻[3-9]對相應(yīng)的問題分別得到了全多項式時間近似方案。文獻[10-14]研究的也是帶有不可用區(qū)間的排序問題。

1 問題描述

該問題是在2臺平行機上將工件集J={1,2,…,n}中的n個互不相關(guān)工件進行排序,目標(biāo)是最小化加權(quán)總完工時間。每個工件i∈J的加工時間為pi。假設(shè)第1臺機器一直可用且第2臺機器在區(qū)間[T2,S2]內(nèi)不能加工工件,機器在每一時刻至多能加工一個工件。不失一般性,考慮所有的數(shù)據(jù)都是正整數(shù)。將工件先按WSPT規(guī)則排好(即ω1/p1≥ω2/p2≥…≥ωn/pn)。這里僅考慮所有工件不全都排在第1臺機器上且不能全都排在第2臺機器T2之前的情形。

2 全多項式近似方案

由引理1,本文的排序問題P2/r-a∑ωjCj的最優(yōu)解中,每臺機器上的工件都按ωj/pj非增的順序排列。將所有工件按ω1/p1≥ω2/p2≥…≥ωn/pn排列。引入變量xj(j=1,2,…,n),如果工件Jj在第1臺機器上加工,令xj=1;如果工件Jj在第2臺機器T2之前加工,令xj=2;如果工件Jj在第2臺機器S2之后加工,令xj=3。記X為所有向量x=(x1,x2,…,xn)所組成的向量集,其中xj={1,2,3},j=1,2,…,n。定義在集合X上的函數(shù)如下:

對于問題P2/r-a∑ωjCj給出一個FPTAS。

算法Aε

第1步 將工件按ω1/p1≥ω2/p2≥…≥ωn/pn順序排列。令Y0={(0,…,0)},j=1。

hj(x(a1,a2,a3,b))=min{hj(x):x∈Ya1,a2,a3,b}

置j=j+1,轉(zhuǎn)第2步。

定理1 問題P2/r-a∑ωjCj利用算法Aε,在O(n5L5/ε4)運行時間內(nèi)找到一向量x′∈X使得h(x′)≤(1+ε)h(x*),其中x*是最優(yōu)解。

當(dāng)xj=1時,

當(dāng)xj=2時,

當(dāng)xj=3時,

這樣導(dǎo)出

從式(1)和式(6)得

類似地有

令δk=δ+δk-1(1+δ),k=2,3,…,n-j+1。那么有

對j+2,…,n重復(fù)論證,有x′∈Yn,得到

又通過引理4有

因此

因此,通過算法Aε中的第3步,得到的x0滿足

hn(x0)≤hn(x′)≤(1+ε)hn(x*)

3 結(jié) 論

本文考慮的是一臺機器在某固定時間內(nèi)不可用且工件中斷可恢復(fù)的兩臺平行機排序問題,目標(biāo)是最小化加權(quán)總完工時間,對該問題給出了一個全多項式方案(FPTAS),其時間復(fù)雜性為O(n5L5/ε4)。

[ 1 ]LEE C Y. Machine scheduling with an availability constraint[J]. J Global Optim, 1996,9(3/4):395-416.

[ 2 ]JI Min, CHENG T C E. Parallel-machine scheduling with simple linear deterioration to minimize total completion time[J]. Eur J Oper Res, 2008,188(2):342-347.

[ 3 ]KOVALYOV M Y, KUBIAK W. A fully polynomial approximation scheme for the weighted earliness-tardiness problem[J]. Oper Res, 1999,47(5):757-761.

[ 4 ]KOVALYOV M Y, KUBIAK W. A fully polynomial approximation scheme for minimizing makespan of deteriorating jobs[J]. J Heuristics, 1998,3(4):287-297.

[ 5 ]WU C C, LEE W C. Scheduling linear deteriorating jobs to minimize makespan with an availability constraint on a single machine[J]. Inf Process Lett, 2003,87(2):89-93.

[ 6 ]KELLERER H, STRUSEVICH V A. A fully polynomial approximation scheme for the single machine weighted total tardiness problem with a common due date[J]. Theor Comput Sci, 2006,369(1):230-238.

[ 7 ]KACEM I. Approximation algorithms for the makespan minimization with positive tails on a single machine with a fixed non-availability interval[J]. J Comb Optim, 2009,17(2):117-133.

[ 8 ]KACEM I. Fully polynomial time approximation scheme for the total weighted tardiness minimization with a common due date[J]. Discrete Appl Math, 2010,158(9):1035-1040.

[ 9 ]喬玉,羅成新. 具有禁用區(qū)間的平行機排序時間表長問題的全多項式近似方案[J]. 沈陽師范大學(xué)學(xué)報:自然科學(xué)版, 2012,30(1):12-15.

[10]LEE C Y. Parallel machines scheduling with non-simultaneous machine available time[J]. Discrete Appl Math, 1991,30:53-61.

[11]LEE C Y, DANUSAPUTRO L S. Capacitated two-parallel machines scheduling to minimize sum of job completion times[J]. Discrete Appl Math, 1993,41(3):211-222.

[12]LI Shisheng, YUAN Jinjiang. Parallel-machine scheduling with deteriorating jobs and rejection[J]. Theor Comput Sci, 2010,411(40):3642-3650.

[13]KELLERER H, KUBZIN M A, STRUSEVICH V A. Two simple constant ratio approximation algorithms for minimizing the total weighted completion time on a single machine with a fixed non-availability interval[J]. Eur J Oper Res, 2009,199(1):111-116.

[14]ZOU Juan, ZHANG Yuzhong, MIAO Cuixia. Uniform parallel-machine scheduling with time dependent processing times[J]. J Oper Res Soc, 2013,1(2):239-252.

[15]GRAHAM R L, LAWLER E L, LENSTRA J K, et al. Optimization and approximation in deterministic sequencing and scheduling: a survey[J]. Ann Discrete Math, 1979,5:287-326.

Parallelmachineschedulingproblemwitharesumableavailabilityconstraint

ZHANGQi,LUOChengxin

(School of Mathematics and Systems Science, Shenyang Normal University, Shenyang 110034, China)

This paper considers a scheduling problem of two parallel machines with a resumable availability constraint. The machine is unavailable betweenT2andS2. We call a job resumable if it cannot finish before the unavailable period of a machine and can continue after the machine is available again. The objective is to minimize the sum of weighted completion times. The problem is NP-hard in the ordinary sense. Therefore, we need to find an approximate solution that fulfills the required error bound. Firstly we propose the definition of the fully polynomial-time approximation scheme. Secondly we give a dynamic programming algorithm. Finally we obtain a fully polynomial-time approximation scheme (FPTAS) by procedure partition. Its running time isO(n5L5/ε4), wherenis the number of jobs,Lis the input size andεis the required error bound.

parallel machine scheduling; non-availability interval; resume; NP-hard; FPTAS

2014-03-16。

國家自然科學(xué)基金資助項目(61070242)。

張 琦(1989-),女,遼寧沈陽人,沈陽師范大學(xué)碩士研究生;

: 羅成新(1958-),男,遼寧新賓人,沈陽師范大學(xué)教授,博士,碩士研究生導(dǎo)師。

1673-5862(2014)04-0466-05

O223

: A

10.3969/ j.issn.1673-5862.2014.04.003