榮 建 華

(石家莊鐵道大學(xué)四方學(xué)院 基礎(chǔ)部， 河北 石家莊 051132)

?

具有服務(wù)等級(jí)的可拒絕平行機(jī)排序問題

榮 建 華

(石家莊鐵道大學(xué)四方學(xué)院 基礎(chǔ)部， 河北 石家莊 051132)

在線排序；平行機(jī)；拒絕費(fèi)用；競(jìng)爭(zhēng)比；服務(wù)等級(jí)

0 引 言

排序問題是運(yùn)籌學(xué)與組合優(yōu)化領(lǐng)域一類重要的問題，對(duì)排序理論的研究具有重要的理論意義和廣闊的應(yīng)用前景.近年來，在含多個(gè)窗口的服務(wù)業(yè)，如銀行等領(lǐng)域，經(jīng)常存在以下2種現(xiàn)象：首先，提供服務(wù)的機(jī)構(gòu)通常有多個(gè)不同等級(jí)的窗口，如一般窗口、貴賓窗口；顧客也有不同的級(jí)別，如一般會(huì)員、金卡會(huì)員、銀卡會(huì)員.等級(jí)低的窗口為所有顧客服務(wù)，等級(jí)高的窗口只為高級(jí)別的顧客服務(wù).其次，服務(wù)存在雙向選擇，提供服務(wù)的一方為了考慮總體效益，可以提供服務(wù)需求，花費(fèi)一定的服務(wù)成本；顧客也會(huì)因?yàn)榈貌粌斒Ф芙^需求，但此時(shí)要付出拒絕費(fèi)用，最終希望整體利益達(dá)到最優(yōu).工件帶有拒絕費(fèi)用和服務(wù)等級(jí)的排序問題是現(xiàn)代工業(yè)生產(chǎn)中出現(xiàn)的2個(gè)新的組合優(yōu)化模型，近年來受到許多研究人員的關(guān)注.本文將工件可拒絕與具有服務(wù)等級(jí)2個(gè)模型復(fù)合起來，即研究具有服務(wù)等級(jí)的可拒絕平行機(jī)在線排序問題.基本問題描述如下：假定有2臺(tái)平行機(jī)M1,M2，加工速度一致；n個(gè)工件J1,J2,…,Jn,分別按列表在線到達(dá)，每個(gè)工件Jj含有3個(gè)參數(shù)：加工長(zhǎng)度tj，拒絕費(fèi)用pj以及服務(wù)等級(jí)gj=1,2.當(dāng)工件到達(dá)時(shí)，可以接收加工，占用一定的加工時(shí)間；也可以拒絕，付出相應(yīng)的罰值.進(jìn)一步，如果工件被接收，則等級(jí)gj=1的工件只能分配在機(jī)器M1上加工；等級(jí)gj=2的工件被分成2兩部分，分別被安排到機(jī)器M1，M2上加工.目標(biāo)為被接收工件的最大完工時(shí)間(makespan)與被拒絕工件的總罰值之和最小.為此本文設(shè)計(jì)了在線算法PH.

1 P2|gj=2,online|W的算法設(shè)計(jì)

為便于分析算法，下面引入一些常用的記號(hào)：

A、R：算法中分別被接收和拒絕的工件集；

A″k：算法中被接收最優(yōu)解中被拒絕的等級(jí)為k的工件集；

R′：算法和最優(yōu)解中均被拒絕的工件集；

R″k：算法中被拒絕最優(yōu)解中被接收的等級(jí)為k的工件集；

L(S),S?J∶S中工件的總長(zhǎng)度；

P(S),S?J∶S中工件的總罰值；

C(E)：算法中將E作為被加工工件集時(shí)的最長(zhǎng)完工時(shí)間；

C*(E)：最優(yōu)解中生成的最長(zhǎng)完工時(shí)間；

WPH：算法生成的目標(biāo)值；

W*：最優(yōu)解中生成的目標(biāo)值.

下面給出在證明競(jìng)爭(zhēng)比過程中非常有用的幾個(gè)引理.

其中tmax為A中最大工件的長(zhǎng)度.

引理2[8]設(shè)Q=(1,1,…,1)T，K=(k1,k2,…,ku)為1×u矩陣，X=(x1,x2,…,xn)T為u×1矩陣，P=(pij)u×u為可逆矩陣，其中第j行行向量記作αj.如果KP-1≥0,則?X≥0，均有KX≤(KP-1Q)max{α1X,α2X,…,αuX}.

由引理2可得

下面給出在線算法PH的具體描述：

當(dāng)工件Jj到達(dá)時(shí),

規(guī)則G1：若gj=1，則將工件Jj分配給機(jī)器M1加工；

引理4 設(shè)A為被加工的工件集，A中等級(jí)為1的工件總是分給M1加工，等級(jí)為2的工件按G2規(guī)則加工，令x為A中最后一個(gè)被加工的工件，則下列結(jié)論成立：

證明 (i)如果分配到M1上的均為等級(jí)為1的工件，則

(1)

否則，至少存在一個(gè)等級(jí)為2的工件部分分配在M1上加工，令y為最后一個(gè)分配在M1上具有等級(jí)2的工件.不妨令ty1=(1-λ)ty，ty2=λty，λ∈(0,1)，并分別將其分配給M1，M2加工，Lxy為工件x,y之間機(jī)器M1的負(fù)載(不含x,y的長(zhǎng)度)，則

(2)

C(A)=

證明 情形1 若A=φ，算法將所有工件拒絕，于是

情形2.2 若gx=2，由引理4可知，

于是有

證畢！

2 結(jié) 語

研究了復(fù)合服務(wù)等級(jí)和可拒絕2種模型的2臺(tái)平行機(jī)排序問題，在工件被接收加工的情形下，等級(jí)為2的工件允許被拆分.文中設(shè)計(jì)了在線算法PH，并證明了其競(jìng)爭(zhēng)比為1.707，下界為1.618，上下界差約0.089.下一步將致力于構(gòu)造更精確的算法，以進(jìn)一步縮小上下界差.

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

[2] HE Y,MIN X.On-line uniform machine scheduling with rejection[J]. Operations Research Transactions,2009,13(1):29-36.

[3] DOSA G, HE Y. Preemptive and non-preemptive on-line algorithms for scheduling with rejection on two uniform machines[J]. Computing,2006,76:149-164.

[4] JIANG Y W, HE Y, TANG C M. Optimal online algorithm for scheduling on identical machines under a grader of service[J]. Journal of Zhejiang University: Science A,2006,7(3):309-314.

[5] PARK J, CHANG S Y, LEE K. Online and semi-online scheduling of two machines under a grader of service provision[J]. Operations Research Letters,2006,34:692-696.

[6] JIANG Y. Online scheduling on parallel machines with two GoS levels[J]. Journal of Combinatorial Optimization,2008,16:28-38.

[7] ZHANG A, JIANG Y, TAN Z. Online parallel machines scheduling with two hierarchies[J]. Theoretical Computer Science,2009,410:3597-3605.

[8] TAN Z, ZHANG A. A note on hierarchical scheduling on two uniform machines[J]. Journal of Combinatorial Optimization, 2010,20:85-95.

RONG Jianhua

(DepartmentofBasic,ShijiazhuangTiedaoUniversitySifangCollege,Shijiazhuang051132,China)

Parallel machine scheduling with service hierarchy and rejection. Journal of Zhejiang University(Science Edition), 2016,43(6):685-688

on-line scheduling; parallel machine; penalty of rejection; competitive ratio; hierarchical

2015-12-18.

河北省高等教育教學(xué)改革研究與實(shí)踐項(xiàng)目(2015GJJG293)；河北省高等教育科學(xué)研究課題(GJXH2015-291).

榮建華(1981-)，ORCID:http://orcid.org/0000-0002-7147-4866，女，碩士，講師，主要從事組合優(yōu)化、排序理論研究,E-mail:rongjianhua2006@126.com.

10.3785/j.issn.1008-9497.2016.06.012

O 223

A

1008-9497(2016)06-685-04