云制造中帶學(xué)習(xí)效應(yīng)平行機(jī)排序問題的最優(yōu)可中斷算法

蔣義偉, 張振宇, 魏 麒, 季 敏

(1.浙江工商大學(xué)管理工程與電子商務(wù)學(xué)院,浙江杭州310018;2.寧波財(cái)經(jīng)學(xué)院國(guó)際經(jīng)濟(jì)貿(mào)易學(xué)院,浙江寧波315100)

§1 引 言

云制造是云計(jì)算,大數(shù)據(jù),物聯(lián)網(wǎng)等技術(shù)上發(fā)展起來的一種新型制造模式,以互聯(lián)網(wǎng)為紐帶將分散在各地的制造資源整合在一起,然后通過云平臺(tái)發(fā)布制造資源當(dāng)前的使用狀況,通過資源整合和共享完成生產(chǎn)制造,極大地提高資源的利用率和生產(chǎn)效率.本文主要研究云制造環(huán)境下的帶有學(xué)習(xí)效應(yīng)的平行機(jī)排序問題,目標(biāo)是在一定費(fèi)用約束下,如何購(gòu)買資源并給出最優(yōu)的生產(chǎn)調(diào)度方案.

本文分別針對(duì)兩類學(xué)習(xí)效應(yīng)函數(shù)給出了最優(yōu)的可中斷算法,目標(biāo)是在所有加工費(fèi)用不超過給定的總費(fèi)用?U的情況下,極小化最大完工時(shí)間,即Makespan.機(jī)器Mi的單位時(shí)間加工費(fèi)用為li,考慮以下加工費(fèi)用依賴于時(shí)間變化的兩種學(xué)習(xí)效應(yīng)函數(shù).第一種學(xué)習(xí)效應(yīng)函數(shù)是基于指數(shù)函數(shù)的DeJong學(xué)習(xí)效應(yīng)函數(shù),即

L1=li(M+(1?M)e?αt)(0≤M<1,α>0).

第二種是基于冪函數(shù)的學(xué)習(xí)效應(yīng)函數(shù),即

L2=li(M+(1?M)(t+1)α)(0≤M<1,α<0).

從上述函數(shù)中可以看到,隨著t不斷增大,機(jī)器Mi的加工成本不斷減少并趨于一個(gè)常量Mli,這里M(0≤M<1)是一個(gè)不可壓縮因子,即加工費(fèi)用最多可以降到原來的(M?100)%.本文主要考慮工件可中斷情況,可中斷是指工件可以在加工過程中被中斷,剩余部分可在后續(xù)的時(shí)間在任意機(jī)器上加工.對(duì)于上述兩個(gè)模型,按照排序問題的三參數(shù)法可表示為Pm|pmtn,Li,U≤|Cmax,i=1,2.

2009年李伯虎等[1-3]首先提出了云制造這一概念并對(duì)其進(jìn)行了定義.現(xiàn)有的大多數(shù)文獻(xiàn)主要研究云制造的服務(wù)模式以及服務(wù)技術(shù)層面[4-6],很少考慮云制造環(huán)境下的資源調(diào)度和生產(chǎn)管理問題.Li等[7]首先研究了云制造環(huán)境下的平行機(jī)排序問題Pm|U≤|Cmax,分別考慮工件可中斷與不可中斷情形.對(duì)于可中斷情形……