榮建華, 侯麗英

(1. 石家莊鐵道大學(xué)四方學(xué)院 基礎(chǔ)部 河北 石家莊 050000； 2. 南京農(nóng)業(yè)大學(xué) 理學(xué)院 江蘇 南京 210095)

?

帶有到達(dá)時(shí)間和拒絕費(fèi)用工件的同類機(jī)排序問題

榮建華1, 侯麗英2

(1. 石家莊鐵道大學(xué)四方學(xué)院 基礎(chǔ)部 河北 石家莊 050000； 2. 南京農(nóng)業(yè)大學(xué) 理學(xué)院 江蘇 南京 210095)

在線排序；同類機(jī)；拒絕費(fèi)用；競爭比

JournalofZhejiangUniversity(ScienceEdition), 2016,43(5):545-549

0　引　言

排序是運(yùn)籌學(xué)與組合優(yōu)化領(lǐng)域的一類重要問題，對排序理論的研究具有重要的理論意義和廣闊的應(yīng)用前景.在經(jīng)典的排序問題中，工件不允許被拒絕，換言之，所有工件都必須被分配到機(jī)器上進(jìn)行加工.然而實(shí)際生產(chǎn)中，并非如此.因?yàn)閺S家可以接受一項(xiàng)有盈利的任務(wù)，也可以拒絕存在風(fēng)險(xiǎn)或成本過高的任務(wù)，但此時(shí)要付出相應(yīng)的罰值，所以帶有拒絕費(fèi)用的排序問題是現(xiàn)代工業(yè)生產(chǎn)中一個(gè)新的組合優(yōu)化模型，它比經(jīng)典的不可拒絕的排序問題更具普遍性.因現(xiàn)實(shí)生活中上述問題比較常見，所以工件可拒絕的排序問題被研究人員廣泛關(guān)注.

對于排序問題，人們致力于研究其近似算法，通常用競爭比ρA來衡量算法A的優(yōu)劣.設(shè)ZA(I)為用算法A安排實(shí)例I所得的目標(biāo)值，Z*(I)為離線排序下的最優(yōu)值，則定義ρA=inf{l|ZA(I)≤lZ*(I),?I}.一個(gè)排序問題具有下界ρL是指其競爭比嚴(yán)格小于ρL的算法A不存在.如果某算法A的競爭比與其相應(yīng)的下界相等，即ρA=ρL，則稱該算法為最優(yōu)近似算法.

1　Qm|rj∈{0,r},online|W的算法設(shè)計(jì)

令S為工件集，表1為文中所涉及的符號.

表1　符號及含義

證明當(dāng)△=0時(shí)，不等式顯然成立.當(dāng)△≠0時(shí)，由△和△*的定義可知，

所以

證畢.

證明設(shè)L1,L2,…,Lm為恰要分配x時(shí)機(jī)器M1,M2,…,Mm上的加工總長度.由LS算法可知：

另一方面，C(A)≤L1+tx,C(A)≤L2+tx,…,

證畢.

對S(0)中的工件，記

將S1(r)中的工件按1,2,…|S1(r)|進(jìn)行編號.

算法H:

步驟1對于S(0)中的工件，拒絕S2(0)中的工件.記σi(0)(i=0,1,…|S1(0)|)為接收S1(0)中的前i個(gè)工件并按LS算法安排加工、拒絕S1(0)中的其他工件所得到的排序.從σi(0)中選取使目標(biāo)函數(shù)最小的排序，記為π1.

步驟2對于S(r)中的工件，拒絕S2(r)中的工件.記(π1,σj(r))(j=0,1,…|S1(r)|)為接收S1(r)中的前j個(gè)工件并按LS算法安排加工、拒絕S1(r)中的其他工件所得到的排序.從(π1,σj(r))中選取目標(biāo)函數(shù)最小的排序，記為(π1,π2).

情形1S(r)=φ.

情形1.1k1=0，即在最優(yōu)排序中拒絕S1(0)中的所有工件.另外，根據(jù)S2(0)的定義，S2(0)中的工件在最優(yōu)排序中也全部被拒絕.又因?yàn)镾(r)=φ，此時(shí)算法H所得的排序是最優(yōu)的，即WH=W*.

情形1.2k1>0.根據(jù)算法有

因?yàn)?/p>

所以

情形2S(r)≠φ.

情形2.1k1=0,k2=0.此時(shí)在最優(yōu)排序中

此時(shí)算法得到的排序最優(yōu).

情形2.2k1=0,k2>0.此時(shí)在最優(yōu)排序中，

情形2.3k1>0,k2=0.

情形2.4k1>0,k2>0.

(此時(shí)在最優(yōu)排序中)

證畢.

2　結(jié)　語

[1]BARTAL Y, LEONARDI S ,MARCHETTI-SPACCAMELA A,et al. Multiprocessor scheduling with rejection[J]. SIA M J on Discrete Mathematics, 2000,13:64-78.

[2]ZHANG L,LU L,YUAN J.Single machine schedul-ing with release dates and rejection[J]. European Journal of Operational Research,2009,198:975-978.

[3]LU L,NG C T,ZHANG L.Optimal algorithms for single-machine scheduling with rejection to minimize the makespan[J]. International Journal of Production Economics, 2011,130:153-158.

[4]CAO Z, ZHANG Y. Scheduling with rejection and non-identical job arrivals[J]. Journal of Systems Science and Complexity, 2007,20:529-535.

[5]ENGELS D W, KARGER D R, KOLLIOPOULOS S G, et al. Techniques for scheduling with rejection[J]. Journal of Algorithms, 2003,49:175-191.

[6]LU L, ZHANG L, YUAN J.The unbounded parallel batch machine scheduling with release dates and rejection to minimize makespan[J]. Theoretical Computer Science, 2008,396:283-289.

[7]LU L,CHENG T C ,YUAN J,et al.Bounded single -machine parallel-batch scheduling with release dates and rejection[J]. Computers & Operations Research, 2009,36:2748-2751.

[8]GAO Q,LU X. Scheduling on single-machine and identical machines with rejection[J]. Operations Research Transactions,2014,18:1-10.

[9]閔嘯，何勇.兩臺可拒絕同類機(jī)在線排序問題近似算法的參數(shù)性能比[J].高校應(yīng)用數(shù)學(xué)學(xué)報(bào)：A輯，2000，15(3)：326-332.

MIN Xiao, HE Yong. Heuristic of scheduling with rejection on two uniform machines[J]. Applied Math-ematics A Journal of Chinese Universities,2000,15(3)：326-332.

[10]MIN X,LIU J,WANG Y. Optimal semi-online algorithm for scheduling with rejection on two uniform machines[J]. Journal of Combinatorial Optimization,2011,22:674-683.

[11]閔嘯，劉靜.拒絕可緩沖的2臺同類機(jī)半在線排序問題的近似算法[J].浙江大學(xué)學(xué)報(bào):理學(xué)版，2014,41(4)：399-405.

MIN Xiao, LIU Jing. Approximate algorithm of semi online scheduling on two uniform machines with a re-

jecting buffer[J]. Journal of Zhejiang University:Science Edition,2014,41(4)：399-405.

Uniformmachineschedulingwitharrivaltimeandrejection.

RONGJianhua1,HOULiying2

(1. Department of Basic, Shijiazhuang Tiedao University Sifang College, Shijiazhuang 050000, China; 2. College of Sciences, Nanjing Agricultural University, Nanjing 210095, China)

on-linescheduling;uniformmachine;rejection;competitiveratio

2015-10-29.

南京農(nóng)業(yè)大學(xué)青年科技創(chuàng)新基金項(xiàng)目(0506J0116);河北省高等教育教學(xué)改革研究與實(shí)踐項(xiàng)目(2015GJJG293);河北省高等教育科學(xué)研究課題(GJXH2015-291).

榮建華(1981-)，ORCID：http//orcid.org/0000-0002-7147-4866,女，碩士，講師，主要從事排序論、近似算法的研究，E-mail:rongjianhua2006@126.com.

10.3785/j.issn.1008-9497.2016.05.009

O223

A

1008-9497(2016)05-545-05