張 敏 張興芳

(1.中央籌備糧聊城直屬庫(kù)，山東聊城252000; 2.聊城大學(xué)數(shù)學(xué)科學(xué)學(xué)院，山東聊城252059)

不確定單機(jī)排序的一個(gè)新的雙目標(biāo)模型和算法①

張 敏1張興芳2

(1.中央籌備糧聊城直屬庫(kù)，山東聊城252000; 2.聊城大學(xué)數(shù)學(xué)科學(xué)學(xué)院，山東聊城252059)

在單機(jī)排序問(wèn)題中，假設(shè)一些任務(wù)被分成若干組(稱為鏈)，它們分別有一個(gè)交貨截止日期和權(quán)重，任務(wù)的處理時(shí)間具有不確定性，又缺乏歷史的數(shù)據(jù).以往人們關(guān)心任務(wù)鏈如何排序使得耽誤任務(wù)的總加權(quán)數(shù)最小或任務(wù)的加權(quán)完成時(shí)間最小或它們同時(shí)最小.本文首先基于不確定理論，視任務(wù)的處理時(shí)間為不確定變量，建立了一個(gè)新的雙目標(biāo)整數(shù)規(guī)劃模型. 然后給出了其模型的性質(zhì).

單機(jī)排序, 耽誤任務(wù)總加權(quán)數(shù), 最后一個(gè)按時(shí)完工時(shí)間, 不確定理論

0 引言

現(xiàn)實(shí)生活中經(jīng)常遇到任務(wù)的各種排序問(wèn)題.本文研究下述的單機(jī)排序問(wèn)題.假設(shè)一個(gè)供應(yīng)商要在一個(gè)機(jī)器上依次處理一些代理商的任務(wù).每?jī)蓚€(gè)相鄰任務(wù)無(wú)耽擱時(shí)間.在每個(gè)時(shí)刻，機(jī)器僅能處理一個(gè)任務(wù).每個(gè)任務(wù)在機(jī)器上僅需要處理一次.代理商分別要求一定的交貨截至日期.又假定供應(yīng)商能夠基于自己當(dāng)前的利益和長(zhǎng)遠(yuǎn)的利益，各代理商的任務(wù)的數(shù)量和重要程度分別賦予各代理商一定的權(quán)重.本文關(guān)心如何將這些任務(wù)進(jìn)行排序使得耽誤任務(wù)總加權(quán)數(shù)和最后一個(gè)按時(shí)完工的任務(wù)的完成時(shí)間同時(shí)最小.

易見(jiàn), 上述問(wèn)題的解(最優(yōu)排序)具有每個(gè)代理商的任務(wù)組不打斷的特征. 所以該問(wèn)題是不中斷的鏈單機(jī)排序問(wèn)題1|chans|∑ωjUj.如果將 每個(gè) 代理商 的任務(wù)組(稱鏈) 看做一個(gè)任務(wù)，耽誤任務(wù)的總加權(quán)數(shù)可歸結(jié)為問(wèn)題1|∑ωjUj.本文又同時(shí)考慮最后一個(gè)按時(shí)完工的鏈時(shí)間最短. 因此，這是一個(gè)雙目標(biāo)整數(shù)規(guī)劃問(wèn)題.

關(guān)于單機(jī)排序的早期研究者有Smith[1]. 他們指出該問(wèn)題是一個(gè)NP(non-deterministicpolynomial-time)-難問(wèn)題. 因此,在近六十年里, 許多學(xué)者對(duì)此模型的算法進(jìn)行了大量的研究[2-9].

關(guān)于單機(jī)排序問(wèn)題的早期研究都假定任務(wù)的處理時(shí)間是一個(gè)常數(shù)[1-7]. 然而，客觀現(xiàn)實(shí)往往并非如此.于是，隨著概率論的問(wèn)世，一些學(xué)者將任務(wù)的處理時(shí)間看作隨機(jī)變量，應(yīng)用概率論解決此類問(wèn)題[8]. 注意，概率論應(yīng)用的前提要有大量的歷史數(shù)據(jù).當(dāng)缺乏歷史數(shù)據(jù)時(shí),于是人們采用專家賦予不確定數(shù)據(jù)信度的方法.有的學(xué)者認(rèn)為這是主觀概率. 然而，在主觀概率下，獨(dú)立事件的概率乘積運(yùn)算法則得到的結(jié)果和人們直覺(jué)的結(jié)果往往不一致，如P(A∩B)=P(A)×P(B)=0.5×0.5=0.25.這里數(shù)值0.25太小，往往人們不能接受它.后來(lái)，1965年，Zadeh提出了 模糊集理論.自然地，有些學(xué)者將其應(yīng)用到此問(wèn)題中[9]. 在2007年，劉寶碇又基于正規(guī)性公理，對(duì)偶性公理和次可加性公理，提出了一種新的處理缺乏歷史數(shù)據(jù)的不確定性的數(shù)學(xué)理論，稱為不確定理論[10].2010年后他又進(jìn)行了補(bǔ)充和完善[11,12].如今，已經(jīng)形成它的許多數(shù)學(xué)分支，如不確定規(guī)劃[13]，不確定邏輯[14],不確定過(guò)程[15]等.本文將應(yīng)用劉的不確定理論研究上述的單機(jī)排序問(wèn)題.

注意，以往學(xué)者們關(guān)心這些任務(wù)鏈如何排序使得耽誤任務(wù)的總加權(quán)數(shù)最小或任務(wù)的加權(quán)完成時(shí)間最小或它們同時(shí)最小.而本文關(guān)心耽誤任務(wù)的總加權(quán)數(shù)和最后一個(gè)按時(shí)完工時(shí)間同時(shí)最小.這種情況在實(shí)際中也是時(shí)常見(jiàn)到的.截止目前,作者未見(jiàn)這種研究.

以下的組織結(jié)構(gòu)如下：第二節(jié)介紹下文用到的不確定理論的基本知識(shí).第三節(jié)，基于不確定理論，將任務(wù)的處理時(shí)間看作具有不確定分布的不確定變量，建立耽誤任務(wù)的總加權(quán)數(shù)和最后一個(gè)按時(shí)完工時(shí)間同時(shí)最小模型.第四節(jié)研究其模型的性質(zhì).最后一節(jié)概括本文的主要結(jié)果.

1 準(zhǔn)備

本節(jié)介紹下文用到的不確定理論的基本知識(shí)[10-12]和雙目標(biāo)規(guī)劃模型的有效解和妥協(xié)解的概念[16].

不確定測(cè)度和不確定空間的概念已經(jīng)眾所周知，本節(jié)不再介紹它們。

定義1 如果ξ是從不確定空間(Γ,L,M)到實(shí)數(shù)集R的可測(cè)函數(shù)，即對(duì)任意Borel集{ξ∈B}={γ∈Γ|ξ(γ)∈B}是一個(gè)事件，則稱ξ為(Γ,L,M)上的不確定變量．

定義2 設(shè)ξ是不確定空間(Γ,L,M)上的不確定變量．若對(duì)?x∈R滿足Φ(x)=M{ξ≤x}, 則稱Φ是ξ的不確定分布．

定義3 如果不確定變量ξ的不確定分布Φ存在反函數(shù)Φ-1(α)，α∈(0,1)，則稱不確定分布Φ是正規(guī)的，且稱Φ-1(α)為ξ的逆不確定分布.

定義4 設(shè)ξ1,ξ2,…,ξm是不確定變量，如果對(duì)任意的Borel集B1,B2,…,Bm集B1,B2,…,Bm滿足

則稱ξ1,ξ2,…,ξm是相互獨(dú)立的.

定義5 若ξ是不確定變量,則

為ξ的期望值，其中，兩個(gè)積分中至少有一個(gè)是有限的．

定理1 設(shè)不確定變量ξ有不確定分布Φ，若其期望值存在，則

定理3 設(shè)ξ和η是存在有限的期望值并且相互獨(dú)立的不確定變量，則對(duì)任意的實(shí)數(shù)a,b，我們都有E[aξ+bη]=aE[ξ]+bE[η].

定義6[16](多目標(biāo)模型的有效解和妥協(xié)解)設(shè)模型

(a)

其中j=1,2,…,p，x=(x1,x2,…,xn)是一個(gè)n維決策向量，fi(x)(i=1,2,…,m)是目標(biāo)函數(shù)，gi(x)(i=1,2,…,p)是系統(tǒng)的約束條件，S={x|gj(x)≤0,j=1,2,…,p}.一個(gè)x*∈S稱為模型(a)有效解，如果不存在x∈S使得fi(x)≤fi(x*),=1=1,2,…,m.且不等號(hào)至少對(duì)一個(gè)序號(hào)j成立.

(b)

這里p1+p2+…+pm=1，j=1,2,…,p.模型(b)的解稱為多目標(biāo)的妥協(xié)解.

限于文章的篇幅，本文僅研究雙目標(biāo)的有效解，另文再研究其妥協(xié)解.

2 不確定單機(jī)排序的雙目標(biāo)模型

2.1 參數(shù)和變量的符號(hào)表示

(ii)鏈k的第j個(gè)任務(wù)在該機(jī)器上的處理時(shí)間ξjk是一個(gè)具有正規(guī)分布Φjk的不確定變量，k=1,2,…,m，j=1,2,…,nk.

(iii)每?jī)蓚€(gè)相鄰任務(wù)沒(méi)有耽擱時(shí)間.

(iv)在每個(gè)時(shí)刻，機(jī)器僅能處理一個(gè)任務(wù)，且每個(gè)任務(wù)在機(jī)器上僅需要處理一次.

2.2 模型

基于(i)-(viii)，我們提出下面的單機(jī)器排序的一個(gè)雙目標(biāo)不確定模型如下

(1)

于是我們給出其對(duì)應(yīng)的一個(gè)精確的數(shù)學(xué)模型如下

(2)

因?yàn)槊總€(gè)任務(wù)在該機(jī)器上的處理時(shí)間ξjk是一個(gè)具有正規(guī)分布Φjk的不確定變量，k=1,2,…,m，j=1,2,…,nk，所以根據(jù)定理2，模型(2)轉(zhuǎn)化為如下形式：

(3)

3 模型的性質(zhì)

為了求解模型(3)，本節(jié)研究其性質(zhì). 首先引入下述概念.

則(1)Ui(x1)=Ui(x0),i=1,2,…,k-1，k+p+1,…,m.(2)Ui(x1)≤Ui+1(x0),i=k,…,k+p-1.(3)Uk+p(x1)=Uk(x0)=1.

證明 (1)因?yàn)镋[ηi(x1))=E[ηi(x0)),i=1,2,…,k-1，k+p+1,…,m,所以

Ui(x1)=Ui(x0),i=1,2,…,k-1，k+p+1,…,m.

Ui(x1)≤Ui+1(x0),i=k,…,k+p-1.

(3)顯然Uk+p(x1)=Uk(x0)=1.

由引理1易得下述引理.

引理2 在引理1的假設(shè)下，有T(x1)≤T(x0)，即后移x0中真值為1的坐標(biāo)可使模型(3)的第一個(gè)目標(biāo)函數(shù)值不增.

證明 根據(jù)引理2有T(x1)≤T(x0).

因?yàn)閘=max{i|Ui(x0)=0},所以根據(jù)引理1(1),有Ui(x1)=Ui(x0)=1,i>l+1.根據(jù)引理3(2),有Ul-1(x1)≤Ul(x0)=0. 故Ul-1(x1)=0.由引理1(3),Ul(x1)=1,所以

引理1-3說(shuō)明模型(3)的有效解滿足前邊的任務(wù)對(duì)應(yīng)的真值全為0，后邊的任務(wù)對(duì)應(yīng)的真值全為1，我們稱這樣的排序?yàn)?-1排序.

則它使得模型(3)的兩個(gè)目標(biāo)值不增.

證明 (1)注意它是引理1的特別情況.

故E[ηi(x2)]=E[ηi(x1)]=E[ηi(x0)],i=1,2,…,j-1,l+1,…,m.已知Ui(x2)=Ui(x1)=Ui(x0)=0,i=1,2,…,j-1,Ui(x2)=Ui(x1)=Ui(x0)=1,i=l+1,…,m.

綜上所述T(x1)=(0,0,…,0,Uk,…,Ul-2，0,1,1,…,1),T(x2)=(0,0,…,0,Uk,…,Ul-2，0,1,1,…,1).

這里x2,x1的前邊k-1個(gè)0,后邊m-(l-1)個(gè)1,第l-1個(gè)坐標(biāo)是0.

(3)該結(jié)論是顯然的，證明略.

易見(jiàn)，定理4為我們提供了求模型(3)的有效解的方法.

5 結(jié)論

本文基于不確定理論，視任務(wù)的處理時(shí)間為不確定變量，提出了一個(gè)新的雙目標(biāo)整數(shù)規(guī)劃模型. 引入了D-排序，1D-排序和0-1排序的概念，由此提供了該模型的性質(zhì).特別地，發(fā)現(xiàn)了該模型有一個(gè)0-1排序有效解，并提供了逼近模型有效解的方法.

[1]SmithWE.Variousoptimizersforsinglestageproduction[J].NavResLogistQ, 1956,3(1) 15:102-109.

[2]TangGC.Anewbranchandboundalgorithmforminimizingtheweightednumberoftardyjobs[J].AnnalsofOperationsResearch, 1990, 24:225-232.

[3]AgnetisA,PascaleG,PacciarelliD.ALagrangianapproachtosingle-machineschedulingproblemwithtwocompetingagents[J].JournalofScheduling, 2009,12: 401-415.

[4]WangD,GenM,ChengR.Schedulinggroupedjobsonsinglemachinewithgeneticalgorithm[J].Computers&industrialengineering, 1999,36 (2):309-324.

[5]LeeK,ChoiBC,LeungJYT,etal.Approximationalgorithmsformulti-agentschedulingtominimizetotalweightedcompletiontime[J].InformationProcessingLetters, 2009,109:913-917.

[6]G.Mosheiov(2001).Schedulingproblemswithalearningeffect[J].EuropeanJournalofOperationalResearch,2001,132:687-693.

[7] 李巧云，王冰，王曉明.隨機(jī)機(jī)器故障下單機(jī)預(yù)測(cè)調(diào)度方法[J].系統(tǒng)工程理論與實(shí)踐,2011,31(12):2 387-2 393.

[8]SeoDK,KleinCM,JangW.Singlemachinestochasticschedulingtominimizetheexpectednumberoftardyjobsusingmathematicalprogrammingmodels[J] .Computers&IndustrialEngineering, 2005,48(2):153-161.

[9]SaidiMehrabadM,PahlavaniA.Afuzzymulti-objectiveprogrammingforschedulingofweightedjobsonasinglemachine[J].TheInternationalJournalofAdvancedManufacturingTechnology,2009, 45(1-2): 122-139.

[10]LiuB.Uncertaintytheory[M]. 2nded,Springer-Verlag,Berlin,2007.

[11]LiuB.Uncertaintytheory:Abranchofmathematicsformodelinghumanuncertainty[M].Springer-Verlag,Berlin, 2010.

[12]LiuB.Someresearchproblemsinuncertaintytheory[J].JournalofUncertainSystems, 2009,3(1):33-10.

[13]GaoY.UncertainModelsforSingleFacilityLocationProblemsonNetworks[J].AppliedMathematicalModelling, 2012,36(6) : 2 592-2 599.

[14]ZhangX,LiX.ASemanticStudyoftheFirst-OrderPredicateLogicwithUncertaintyInvolved[J].FuzzyOptimDecisMaking, 2014,13: 357-367.

[15]ZhangX,NingY,MengG.Delayedrenewalprocesswithuncertaininterarrivaltimes[J].FuzzyOptimDecisMaking, 2013,12: 79-87.

[16]XuJ,ZhouX.Aclassofmulti-objectiveexpectedvaluedecision-makingmodelwithbirandomcoefficientsanditsapplicationtoflowshopschedulingproblem[J].InformationSciences, 2009, 179:2 997-3 017.

A New Model and Agorithm of Two Objectives for Uncertain Sngle Mchine Sheduling Problem

ZHANG Min1ZHANG Xing-fang2

(1.Grain Depot of Centra Preparations for the Food, Liaocheng 252000, China；2. School of Mathematical Sciences,Liaocheng University, Liaocheng 252059， China )

In the sngle machine scheduling problem, suppose that some jobs are divide into some groups( called chains). They have a due date and weight respectively. Processing time of job has uncertainty and no its historical data. Previous researches are concerned with how schedule a processing sequence of chains such that the total weighted number of tardy job is minimum or the total weighted completion time of chains is minimum or they is minimum simultaneously. In the paper , a new model of integral number of two objectives first is established based on uncertainty theory. Then, its properties are given.

sngle machine scheduling, the total weighted number of tardy jobs, completion time of final a job which can be finished before due date, uncertainty theory

2016-09-30

國(guó)家自然科學(xué)基金項(xiàng)目(11471152)資助

張興芳,E-mail:zhangxingfang2005@126.com.

O29

A

1672-6634(2017)01-0027-06