榮建華 侯麗英

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

?

帶拒絕費用的平行機(jī)在線排序

榮建華1侯麗英2

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

研究了工件帶有拒絕費用的m臺平行機(jī)在線算法，假定有m臺平行機(jī)M1,M2,…,Mm，n個工件J1,J2,…,Jn,每個工件的加工時間與拒絕費用成固定的比例α(α≥0)，即pj=αtj，當(dāng)α較大時，即工件的拒絕費用相對于加工時間較大，則將此工件接收加工；當(dāng)α較小時，即每個工件的拒絕費用相對于其加工時間較小，此時將工件拒絕。文中設(shè)計出在線算法PRLS,并證明算法的競爭比為關(guān)于參數(shù)α的分段函數(shù)，且為緊界。

在線排序； 競爭比； 同型機(jī)； 拒絕費用；不可中斷;運籌學(xué)

0 引言

在經(jīng)典的排序文獻(xiàn)中，所有的工件都不允許被拒絕，換言之，任何工件都必須被安排到機(jī)器上進(jìn)行加工。然而在工廠實際生產(chǎn)過程中，生產(chǎn)決策者們并非總是如此。隨著社會經(jīng)濟(jì)的迅速發(fā)展，市場競爭也越來越激烈，為了使企業(yè)在市場競爭中立于不敗之地，良好的調(diào)度管理和有效的控制成本成為企業(yè)間競爭的重要因素。因此在現(xiàn)有的生產(chǎn)資源有限的前提下，為了使企業(yè)獲得最多的利潤，生產(chǎn)廠家有時不得不拒絕一些資源耗費較多但帶來的利潤卻較少的工件?；谠趯嶋H生產(chǎn)中上述問題比較常見，所以工件帶拒絕費用的排序問題受到研究人員廣泛的關(guān)注[1-4]。本文主要研究了工件帶拒絕費用的m臺平行機(jī)在線排序問題?；灸Ｐ兔枋鋈缦拢涸O(shè)有m臺機(jī)器M1,M2,…,Mm和n個工件J1,J2,…,Jn，每臺機(jī)器的加工速度相同，每個工件Jj帶兩個參數(shù)(pj,tj),pj表示其拒絕費用，tj表示其加工時間。當(dāng)工件Jj到達(dá)后，生產(chǎn)決策者需馬上做出決定，工件可以被拒絕，但要付出一定的拒絕費用；也可以選擇被加工，花費一定的加工時間。目標(biāo)為拒絕工件的總拒絕費用與加工工件的最晚完工時間(makespan)之和最小。文中進(jìn)一步假設(shè)每個工件的拒絕費用和加工時間成固定比例α(α≥0)，且加工不允許中斷(non-preemptive)，即工件一旦分給某個機(jī)器，必須由這臺機(jī)器連續(xù)加工直到結(jié)束。以上問題用三參數(shù)法表示為Pm|nonpmpt,rej,pj=αtj|W。

根據(jù)確定排序時了解的工件信息的多少，常將平行機(jī)排序分為“在線”(on-line)，“離線”(off-line)和“半在線”(semi on-line)。在線排序為工件一個一個到達(dá)，只有在工件到達(dá)后才知道它的信息，且工件一經(jīng)安排不得臨時改變；離線排序為所有工件信息都事先完全已知，排序者可充分利用工件信息設(shè)計算法；而實際應(yīng)用中的情況往往介于上述兩種情形之間，我們稱之為“半在線”(semion-line),即所知道的工件信息介于在線和離線之間，工件的準(zhǔn)確信息雖然未知，但一些局部信息事先已知，如：工件按從小到大的順序到達(dá),各工件的加工時間介于某個區(qū)間[t,rt]中，工件的總長度(sum),最大工件(max)等等。半在線排序中，已知的工件部分信息或條件可以幫助我們設(shè)計出比在線情形更優(yōu)的算法。

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

本文是基于閔嘯[6-7]的基礎(chǔ)上，將機(jī)器臺數(shù)推廣到任意臺m(m>3)，即討論m臺帶拒絕費用的同型機(jī)在線排序問題，每個工件的拒絕費用pj和加工時間tj之間成固定比例α，即pj=αtj(α≥0)，且加工不允許中斷(non-preemptive),問題記為Pm|nonpmpt,rej,pj=αtj|W，設(shè)計出在線算法PRLS，證明算法的競爭比ρPRLS為關(guān)于參數(shù)α和機(jī)器臺數(shù)m的分段函數(shù)。

1 Pm|nonpmpt,rej,pj=αtj|W的算法設(shè)計

Pm|nonpmpt,rej,pj=αtj|W問題的描述已在引言中介紹，其中，α為工件的加工時間和拒絕費用的比例(α≥0)，下面對符號作統(tǒng)一規(guī)定。

算法的基本思想：若α較大，即工件的拒絕費用相對于加工時間較大，則傾向于將其接收，若α較小，即每個工件的拒絕費用相對于其加工時間較小，故將其拒絕較好；因為同型機(jī)在線排序中，對于加工不可中斷情形，且m臺機(jī)器時，LS(listscheduling)算法已為最優(yōu)算法，故可按LS算法安排工件加工。

算法PRLS:

引理1.1在m臺同型機(jī)在線排序中，假設(shè)S為被加工的工件集，且按LS算法安排加工，y為最后完工的工件，最晚完工時間為C(S)，則有：

(2)L(S)≤mC(S)。

定理1.1PRLS算法的競爭比至多為：

且界是緊的。

證明：根據(jù)α的不同取值范圍，下面分情況進(jìn)行討論。

以下根據(jù)x在最優(yōu)解中是被接收還是被拒絕再分兩種子情形：

子情形2.2：若x在最優(yōu)解中被接收，則有：x∈A，

由此，得到了關(guān)于算法PRLS的上界ρPRLS。

下面構(gòu)造實例說明這個界是緊的。

2 結(jié)語

本文將帶拒絕費用的平行機(jī)排序問題推廣到m臺機(jī)器上，且不允許中斷加工，設(shè)計出在線算法PRLS，并證明了算法的競爭比為關(guān)于參數(shù)α的分段函數(shù)。但是有關(guān)該問題的下界還沒有給出，下一步將致力于構(gòu)造該問題的下界。

[1]SEIDEN S S. Preemptive multiprocessor scheduling with rejection[J].Theoretical Computer Science,2001,262:437-458.

[2]WEN J J,DU D L. Preemptive on-line scheduling for uniform processors[J].Operations Research Letters,1998,23:113-116.

[3]Epstein L,Sgall J. Approximation schemes for scheduling on uniformly related and identical parallel machines[J]. Algorithmica,2004,39:43-57.

[4]Dosa G,He Y. Preemption and non-preemption on-line algorithms for schuduling with rejection on two uniform machines[J].Computing,2006,76：149-162.

[5]Bartal Y,Leonardi S,Marchetti-Spaccamela A,et al. Multiprocessor scheduling with rejection[J].SIAM J on Discrete Mathematics, 2000,13:64-78.

[6]閔嘯. 一種特殊情形不可中斷的兩臺可拒絕同型機(jī)在線排序問題[J].數(shù)學(xué)的實踐與認(rèn)識，2006,36(4)：1-6.

[7]閔嘯. 一特殊情形的三臺可拒絕同型機(jī)在線排序問題[J].嘉興學(xué)院學(xué)報，2006,18(3)：44-47.

On-line Scheduling on Identical Machines with Rejection

Rong Jianhua1, Hou Liying2

(1.Department of basic,Shi jiazhuang Tiedao University Sifang College,Shijiazhuang 051132,China;2.College of Sciences,Nanjing Agricultural University,Nanjing 210095,China)

This paper investigates the on-line scheduling problem on m identical machines with rejection . An identical processors system denoted by and a sequence of independent jobs are given.We assume that the processing time of each job and its penalty forms the regular proportion denoted by.The objective is to minimize the sum of the makespan produced by the accepted jobs and the total penalty of the jobs which have been rejected.Preemption is not allowed.For this version,we present an on-line algorithm and prove the competitive ratio.

on-line scheduling; competitive ratio; identical machine; rejection; nonpreemptive; operations research

2015-04-06 責(zé)任編輯:車軒玉

10.13319/j.cnki.sjztddxxbzrb.2016.02.21

國家自然科學(xué)基金(11426133), 南京農(nóng)業(yè)大學(xué)青年科技創(chuàng)新基金(0506J0116)

榮建華(1981-)，女，碩士，講師，主要從事運籌學(xué)與組合最優(yōu)化研究。E-mail:rongjianhua2006@126.com

O223

A

2095-0373(2016)02-0107-04

榮建華，侯麗英.帶拒絕費用的平行機(jī)在線排序[J].石家莊鐵道大學(xué)學(xué)報:自然科學(xué)版,2016,29(2):107-110.