竇文卿,范靜

一類資源費(fèi)用可變的平行機(jī)排序問題

竇文卿,范靜

(上海第二工業(yè)大學(xué)理學(xué)院,上海201209)

研究了資源費(fèi)用可變的排序問題起源于服務(wù)系統(tǒng)和某些特定的生產(chǎn)系統(tǒng),在這些服務(wù)系統(tǒng)中均存在著隨著資源使用時(shí)段的不同而產(chǎn)生不同的費(fèi)用。在資源費(fèi)用可變的排序問題中,工件具有整數(shù)加工時(shí)間,工件在加工過程中允許中斷。假定把機(jī)器的時(shí)間窗口劃分為T個(gè)單位時(shí)間段,在某個(gè)時(shí)間段使用機(jī)器加工工件就要付出相應(yīng)的費(fèi)用,要求在給定的時(shí)間窗口內(nèi)加工完所有的工件。問題的目標(biāo)函數(shù)是經(jīng)典排序的目標(biāo)函數(shù)與所使用的總資源費(fèi)用之和。對(duì)于目標(biāo)函數(shù)為完工時(shí)間和與所使用的總資源費(fèi)用之和的排序問題,給出了2個(gè)近似算法。

排序;平行機(jī);資源費(fèi)用;可中斷

0 引言

在經(jīng)典的排序模型中考慮的目標(biāo)函數(shù)是Cmax、∑Cj、Lmax、Tmax、∑Uj等。經(jīng)典的排序模型不考慮資源的使用費(fèi)用,這是因?yàn)榻?jīng)典的排序模型均來源于生產(chǎn)與制造管理,而在制造業(yè)中用于工件處理的機(jī)器設(shè)備均為固定投資,一旦投資購買即為固定成本。然而在許多服務(wù)系統(tǒng)中,均存在著隨著資源使用時(shí)段的不同而產(chǎn)生不同的費(fèi)用。把資源的使用費(fèi)用集成到排序與調(diào)度模型中,研究可變資源使用費(fèi)用的排序問題,對(duì)于提升服務(wù)系統(tǒng)的績(jī)效非常重要。由于資源的使用費(fèi)用隨時(shí)間段的變化而變化,故可假定把機(jī)器的時(shí)間窗口劃分為T個(gè)單位時(shí)間段,在某個(gè)時(shí)間段使用機(jī)器加工工件就要付出相應(yīng)的費(fèi)用,要求在給定的時(shí)間窗口內(nèi)加工完所有的工件。問題的目標(biāo)函數(shù)就變?yōu)榻?jīng)典排序的目標(biāo)函數(shù)與所使用的總的資源費(fèi)用之和。

排序與調(diào)度模型和算法一直是運(yùn)作管理、運(yùn)籌學(xué)和計(jì)算機(jī)科學(xué)領(lǐng)域的重要研究課題。經(jīng)過多年發(fā)展,經(jīng)典的排序與調(diào)度模型和算法已經(jīng)非常成熟,并得到廣泛的應(yīng)用,顯著增加了經(jīng)濟(jì)效益以及社會(huì)效益[1-2]。近年來,又出現(xiàn)了許多新型的排序與調(diào)度問題,比如：供應(yīng)鏈排序、分批排序等。盡管對(duì)服務(wù)系統(tǒng)的運(yùn)作排序與調(diào)度模型、算法和應(yīng)用方面的研究有了一定的進(jìn)展,但隨著社會(huì)的進(jìn)步與發(fā)展,相關(guān)的研究工作不管是在理論還是應(yīng)用方面均顯不足。本文要研究的內(nèi)容是如何把資源的使用費(fèi)用集成到排序與調(diào)度模型中,國內(nèi)外與本文相關(guān)的文獻(xiàn)不多,對(duì)該類問題的研究尚屬起步階段。

從目前的文獻(xiàn)可以看出,對(duì)于考慮資源使用費(fèi)用的排序與調(diào)度的研究大多考慮的是資源的啟動(dòng)費(fèi)用[3-6]。與上述研究不同,Dogan等[7]研究了智能電網(wǎng)中獨(dú)立工作的排序問題,考慮了隨時(shí)間變化的資源使用費(fèi)用,其目標(biāo)是滿足各種服務(wù)要求。Wan等[8]考慮的是存在時(shí)變資源使用費(fèi)用的單機(jī)排序與調(diào)度模型,討論了所有正則目標(biāo)函數(shù)和各類不同條件下模型的計(jì)算復(fù)雜性和求解方法,證明了資源費(fèi)用結(jié)構(gòu)為一般情形時(shí),模型是難以求解的,并對(duì)一類重要特例(資源費(fèi)用為時(shí)間單調(diào)函數(shù)的情形)給出了多項(xiàng)式或擬多項(xiàng)式動(dòng)態(tài)規(guī)劃算法,這類模型在服務(wù)系統(tǒng)的運(yùn)作排序與調(diào)度中具有重要意義。Zhong等[9]沿著這一方向,考慮了排序的目標(biāo)函數(shù)為Cmax的模型,證明了問題是難解的并對(duì)一類特例給出了多項(xiàng)式時(shí)間算法。Zhao等[10]研究了存在時(shí)變資源使用費(fèi)用的2臺(tái)機(jī)器的排序模型,工件在加工過程中不可中斷,證明了當(dāng)資源費(fèi)用按照特定的模式(包括線性遞減、凹遞減和凸遞減)遞減時(shí)問題是可以多項(xiàng)式時(shí)間可解的。但是他們研究的資源使用費(fèi)用隨時(shí)間變化的排序問題都未能考慮服務(wù)運(yùn)作中的眾多約束條件。在上述所有的研究中,幾乎沒有考慮服務(wù)系統(tǒng)其他特征的模型(例如在線處理、可中斷處理過程等),而且只有Zhao等[10]對(duì)算法進(jìn)行了研究。

本文著重對(duì)目標(biāo)函數(shù)為完工時(shí)間和與使用的總資源費(fèi)用之和的工件可中斷的平行機(jī)排序進(jìn)行了分析,并給出了2個(gè)近似算法。

1 問題介紹

現(xiàn)有n個(gè)工件{J1,J2,···,Jn}要在m臺(tái)機(jī)器上加工,其中每個(gè)工件Jj具有整數(shù)加工時(shí)間pj,工件在加工過程中允許中斷;由于資源的使用費(fèi)用隨時(shí)間段的變化而變化,故可假定把機(jī)器的時(shí)間窗口劃分為T個(gè)單位時(shí)間段,其中第t個(gè)單位時(shí)間段是從時(shí)刻t-1到t的時(shí)段(t=1,2,···,T),πkt表示使用第k臺(tái)機(jī)器的第t個(gè)單位時(shí)間段所需的資源費(fèi)用(k=1,2,···,m,t=1,2,···,T),要求在給定的時(shí)間窗口內(nèi)加工完所有的工件;目標(biāo)函數(shù)是經(jīng)典排序的目標(biāo)函數(shù)f與所使用的總的資源費(fèi)用之和π,其中f為Cmax、∑Cj、Lmax、Tmax、∑Uj等。令集合Sk表示第k臺(tái)機(jī)器上用來加工工件的時(shí)間段(k=1,2,···,m),則總的資源使用費(fèi)用。由于一個(gè)工件不可能同一時(shí)間在兩臺(tái)機(jī)器上加工,故為了確?？尚行?假設(shè)本文考慮的排序模型的目標(biāo)函數(shù)為Cj+π,用三參數(shù)法可分別表示為

2 問題的近似算法

對(duì)于上述問題,先分析最優(yōu)解的性質(zhì),然后尋求問題的算法。

2.1近似算法CS

引理如果問題Pm|slot cost,pm tn|Cj+π存在最優(yōu)解,那么在其最優(yōu)解中,每臺(tái)機(jī)器上的工件的加工順序應(yīng)該是服從SPT序的。

因此,按照上述引理,本文采用安排工件順序→選擇時(shí)間段的思想來設(shè)計(jì)算法。由于問題Pm|pm tn|∑Cj已經(jīng)證明是多項(xiàng)式時(shí)間可解的,可以用SPT規(guī)則求解。

SPT規(guī)則將加工時(shí)間最小的工件安排到最早空閑的機(jī)器上加工。

經(jīng)過上述分析可提出算法CS。

算法CS執(zhí)行步驟如下：

(1)先不考慮時(shí)間段費(fèi)用,利用SPT規(guī)則得到Pm|slot cost,pm tn|∑Cj的一個(gè)排序π′,同時(shí)計(jì)算排序π′中工件的最大完工時(shí)間Cmax;

(2)若Cmax＞T,則此算法無解;若Cmax≤T,則跳轉(zhuǎn)到步驟3;

(3)將時(shí)間段按照其費(fèi)用的非減序排列;

(4)對(duì)于Cmax≤t≤T,從每臺(tái)機(jī)器的前t個(gè)時(shí)間段中選擇費(fèi)用最小的若干個(gè)時(shí)間段,將工件按照第1步得到的排序π′順序不變放到選出的時(shí)間段上加工,并計(jì)算完工時(shí)間和(記為C(t))以及所使用的資源費(fèi)用π(t);

定理1算法CS可在O(n log n+m T2)時(shí)間內(nèi)得到問題的解。

2.2近似算法Π

所研究問題Pm|slot cost,pm tn|∑Cj+π的目標(biāo)函數(shù)有兩部分,算法CS的設(shè)計(jì)思想是讓∑Cj盡量小,但是這樣會(huì)導(dǎo)致使用的資源費(fèi)用比較高。由于一個(gè)工件不可能同時(shí)安排在兩臺(tái)機(jī)器上加工,故使用的資源費(fèi)用比較高的原因是選擇的時(shí)間段比較多,尤其是實(shí)例中包含了某個(gè)(或某幾個(gè))加工時(shí)間比較大的工件時(shí)。所以,要想降低使用的資源費(fèi)用,就必須讓排序π′中的Cmax盡可能的小,利用該思想設(shè)計(jì)算法Π如下。

算法Π把算法CS第1步中對(duì)工件的預(yù)排序所依據(jù)的規(guī)則稍作改動(dòng),先把pj比較大的工件(加工時(shí)間大于的工件)單獨(dú)安排在一個(gè)機(jī)器上,剩余工件按照SPT規(guī)則安排在剩余機(jī)器上。

顯然,算法Π與算法CS的時(shí)間復(fù)雜性相同。

接下來給出Pm|slot cost,pm tn|Cj+π問題最優(yōu)值的一個(gè)下界。令L為Pm|pm tn|Cj的最優(yōu)值,由于問題Pm|pm tn|∑Cj與問題Pm‖∑Cj的最優(yōu)值相等,而問題Pm‖∑Cj可以用SPT規(guī)則解決。令V表示問題中費(fèi)用最小的LB個(gè)時(shí)間段的費(fèi)用之和,其中是問題Pm|pm tn|Cmax的一個(gè)下界,這是因?yàn)镻m|pm tn|Cmax的最優(yōu)解C不會(huì)小于任何工件的加工時(shí)間,也不會(huì)小于各臺(tái)機(jī)器的平均∑負(fù)荷。由上述分析,可得問題Pm|slot cost,pm tn|Cj+π(S)的一個(gè)下界,即：

定理2 L+V是問題Pm|slot cost,pm tn|∑Cj+π(S)的一個(gè)下界。

2.3特殊情形

從算法CS的設(shè)計(jì)可以看出,工件加工時(shí)間差別越小,算法CS的性能就越好。顯然,當(dāng)所研究的問題為Pm|pj=1,slot cost,pm tn|Cj+π,即所有工件的加工時(shí)間都為單位時(shí)間時(shí),算法CS是一個(gè)最優(yōu)算法,即：

定理3算法CS可得到問題Pm|pj=1,slot cost,pm tn|∑Cj+π的最優(yōu)解。

3 結(jié)語

本文研究了一類考慮可變資源使用費(fèi)用的工件加工過程可中斷的平行機(jī)排序問題,目標(biāo)函數(shù)為Cj+π,其中π是所使用的總資源費(fèi)用。對(duì)于該排序問題,本文給出了2個(gè)近似算法。下一步將研究目標(biāo)函數(shù)Lmax+π等的可中斷的平行機(jī)排序或不可中斷的排序問題的算法。

[1]PINEDO M L.Scheduling：Theory,algorithms and systems[M].4th Edition.Berlin Heidelberg：Springer,2012. [2]BLAZEW ICZ J,ECKERKH,PESCHE,etal.Scheduling computers andmanufacturing processes[M].2nd Edition. Berlin Heidelberg：Springer,2001.

[3]CAO D,CHENM,WAN G H.Parallelmachine selection and job scheduling tom inim izemachine costand job tardiness[J].Computersand OperationsResearch,2005,32(8)：1995-2012.

[4]LEE I.Artificial intelligence search methods for multimachine two-stage scheduling w ith due date penalty,inventory,andmachining costs[J].Computers&Operations Research,2001,28(9)：835-852.

[5]LEUNG JY T,LEEK,PINEDOM L.Bi-criteria schedulingw ithmachine assignment costs[J].International Journalof Production Economics,2012,139(1)：321-329.

[6]PANWALKAR S S,LIMAN S D.Single operation earliness-tardiness scheduling w ith machine activation costs[J].IIE Transactions,2002,34(5)：509-513.

[7]DOGAN A,OZGUNER F.Scheduling independent tasks w ith qos requirementsin grid computingw ith time-varying resource prices[C]//InternationalWorkshop on Grid Computing.Berlin Heidelberg：Springer,2002：58-69.

[8]WANGH,QIX T.Schedulingw ith variable timeslotcosts [J].NavalResearch Logistics,2010,57(2)：159-171.

[9]ZHONG W Y,LIU X L.A single machine scheduling problem w ith timeslotcosts[M]//Recentadvancesin computer science and information engineering.Berlin Heidelberg：Springer,2012：677-681.

[10]ZHAO Y C,QIX T,LIM M.On scheduling w ith nonincreasing time slot cost tominim ize totalweighted completion time[J].Journalof Scheduling,2016,19(6)：759-767.

A Classof ParallelM achine Scheduling Problem w ith Varible Time SlotCosts

DOUWenqing,FAN Jing
(Schoolof Science,ShanghaiPolytechnic University,Shanghai201209,China)

Thescheduling problem w ith variable timeslotcostsstudied isoriginated from servicesystem and certain production systems, inwhich the resourceusage costs variesover time period.In the scheduling problem w ith variable time slotcosts,an integer processing time is given for each job the jobs and preemption is allowed.Suppose that the planning horizon consists of T time slotsw ith unit length,the corresponding costmustbe paid if some time periods is taken to process jobs,and all the jobsmustbe processed in thegiven time horizon.The objective function is one traditional performancemeasure plus the total time slot costs.For the scheduling problem w ith the total completion time plus the total time slotcosts,two approximation algorithmswaspresented.

scheduling;parallelmachine;slotcosts;preemption

O223

A

1001-4543(2017)02-0128-03

10.19570/j.cnki.jsspu.2017.02.009

2016-12-01

范靜(1979—),女,山西長(zhǎng)治人,副教授,博士,主要研究方向?yàn)榕判蛘?。E-mail：fanjing@sspu.edu.cn。

上海第二工業(yè)大學(xué)青年教師培養(yǎng)科研項(xiàng)目(201515)資助