榮建華 侯麗英

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

?

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

榮建華1侯麗英2

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

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

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

0 引言

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

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

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

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

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

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

算法的基本思想：若α較大，即工件的拒絕費(fèi)用相對(duì)于加工時(shí)間較大，則傾向于將其接收，若α較小，即每個(gè)工件的拒絕費(fèi)用相對(duì)于其加工時(shí)間較小，故將其拒絕較好；因?yàn)橥蜋C(jī)在線排序中，對(duì)于加工不可中斷情形，且m臺(tái)機(jī)器時(shí)，LS(listscheduling)算法已為最優(yōu)算法，故可按LS算法安排工件加工。

算法PRLS:

引理1.1在m臺(tái)同型機(jī)在線排序中，假設(shè)S為被加工的工件集，且按LS算法安排加工，y為最后完工的工件，最晚完工時(shí)間為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)造實(shí)例說明這個(gè)界是緊的。

2 結(jié)語

本文將帶拒絕費(fèi)用的平行機(jī)排序問題推廣到m臺(tái)機(jī)器上，且不允許中斷加工，設(shè)計(jì)出在線算法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]閔嘯. 一種特殊情形不可中斷的兩臺(tái)可拒絕同型機(jī)在線排序問題[J].數(shù)學(xué)的實(shí)踐與認(rèn)識(shí)，2006,36(4)：1-6.

[7]閔嘯. 一特殊情形的三臺(tái)可拒絕同型機(jī)在線排序問題[J].嘉興學(xué)院學(xué)報(bào)，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-)，女，碩士，講師，主要從事運(yùn)籌學(xué)與組合最優(yōu)化研究。E-mail:rongjianhua2006@126.com

O223

A

2095-0373(2016)02-0107-04

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