張 敏 張興芳

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

不確定單機排序的一個新的雙目標模型和算法①

張 敏1張興芳2

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

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

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

0 引言

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

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

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

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

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

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

1 準備

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

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

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

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

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

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

則稱ξ1,ξ2,…,ξm是相互獨立的.

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

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

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

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

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

(a)

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

(b)

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

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

2 不確定單機排序的雙目標模型

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

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

(iii)每兩個相鄰任務(wù)沒有耽擱時間.

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

2.2 模型

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

(1)

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

(2)

因為每個任務(wù)在該機器上的處理時間ξjk是一個具有正規(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)因為E[η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的坐標可使模型(3)的第一個目標函數(shù)值不增.

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

因為l=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說明模型(3)的有效解滿足前邊的任務(wù)對應(yīng)的真值全為0，后邊的任務(wù)對應(yīng)的真值全為1，我們稱這樣的排序為0-1排序.

則它使得模型(3)的兩個目標值不增.

證明 (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個0,后邊m-(l-1)個1,第l-1個坐標是0.

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

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

5 結(jié)論

本文基于不確定理論，視任務(wù)的處理時間為不確定變量，提出了一個新的雙目標整數(shù)規(guī)劃模型. 引入了D-排序，1D-排序和0-1排序的概念，由此提供了該模型的性質(zhì).特別地，發(fā)現(xiàn)了該模型有一個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] 李巧云，王冰，王曉明.隨機機器故障下單機預(yù)測調(diào)度方法[J].系統(tǒng)工程理論與實踐,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

國家自然科學(xué)基金項目(11471152)資助

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

O29

A

1672-6634(2017)01-0027-06