帶有到達時間和拒絕費用工件的同類機排序問題

榮建華, 侯麗英

(1. 石家莊鐵道大學四方學院 基礎部 河北 石家莊 050000； 2. 南京農業大學 理學院 江蘇 南京 210095)

?

帶有到達時間和拒絕費用工件的同類機排序問題

榮建華1, 侯麗英2

(1. 石家莊鐵道大學四方學院 基礎部 河北 石家莊 050000； 2. 南京農業大學 理學院 江蘇 南京 210095)

在線排序；同類機；拒絕費用；競爭比

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

0　引　言

排序是運籌學與組合優化領域的一類重要問題，對排序理論的研究具有重要的理論意義和廣闊的應用前景.在經典的排序問題中，工件不允許被拒絕，換言之，所有工件都必須被分配到機器上進行加工.然而實際生產中，并非如此.因為廠家可以接受一項有盈利的任務，也可以拒絕存在風險或成本過高的任務，但此時要付出相應的罰值，所以帶有拒絕費用的排序問題是現代工業生產中一個新的組合優化模型，它比經典的不可拒絕的排序問題更具普遍性.因現實生活中上述問題比較常見，所以工件可拒絕的排序問題被研究人員廣泛關注.

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

1　Qm|rj∈{0,r},online|W的算法設計

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

表1　符號及含義

證明當△=0時，不等式顯然成立.當△≠0時，由△和△*的定義可知，

所以

證畢.

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

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

證畢.

對S(0)中的工件，記

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

算法H:

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

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

情形1S(r)=φ.

情形1.1k1=0，即在最優排序中拒絕S1(0)中的所有工件.另外，根據S2(0)的定義，S2(0)中的工件在最優排序中也全部被拒絕.又因為S(r)=φ，此時算法H所得的排序是最優的，即WH=W*.

情形1.2k1>0.根據算法有

因為

所以

情形2S(r)≠φ.

情形2.1k1=0,k2=0.此時在最優排序中

此時算法得到的排序最優.

情形2.2k1=0,k2>0.此時在最優排序中，

情形2.3k1>0,k2=0.

情形2.4k1>0,k2>0.

(此時在最優排序中)

證畢.

2　結　語

[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].高校應用數學學報：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].浙江大學學報:理學版，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.

南京農業大學青年科技創新基金項目(0506J0116);河北省高等教育教學改革研究與實踐項目(2015GJJG293);河北省高等教育科學研究課題(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