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

本文分別針對(duì)兩類學(xué)習(xí)效應(yīng)函數(shù)給出了最優(yōu)的可中斷算法,目標(biāo)是在所有加工費(fèi)用不超過(guò)給定的總費(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)用最多可以降到原來(lái)的(M?100)%.本文主要考慮工件可中斷情況,可中斷是指工件可以在加工過(guò)程中被中斷,剩余部分可在后續(xù)的時(shí)間在任意機(jī)器上加工.對(duì)于上述兩個(gè)模型,按照排序問(wèn)題的三參數(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)管理問(wèn)題.Li等[7]首先研究了云制造環(huán)境下的平行機(jī)排序問(wèn)題Pm|U≤|Cmax,分別考慮工件可中斷與不可中斷情形.對(duì)于可中斷情形,給出了一個(gè)最優(yōu)解算法,對(duì)于不可中斷情形,設(shè)計(jì)了一個(gè)最壞情況界為2的近似算法.此后,Li等[8]研究了機(jī)器帶有固定租用成本的同類機(jī)排序問(wèn)題Qm|U≤|Cmax,針對(duì)機(jī)器速度越大,機(jī)器速度與機(jī)器費(fèi)用比值也越大的特殊情況,分別給出了可中斷和不可中斷近似算法.劉淑丹等[9]則給出了同類機(jī)情形下更一般的結(jié)果.

與上述問(wèn)題密切相關(guān)的研究為帶機(jī)器購(gòu)買費(fèi)用的平行機(jī)在線排序問(wèn)題.Noga等[10]首次研究了帶機(jī)器費(fèi)用的在線排序問(wèn)題,對(duì)于機(jī)器購(gòu)買費(fèi)用為單位費(fèi)用情形,分別給出了工件兩種到達(dá)方式下的在線算法和下界,Dósa等[11]改進(jìn)了上述結(jié)果.Imreh[12]和Jiang等[13]分別研究了兩種不同加工成本的機(jī)器和可中斷情況下的在線排序問(wèn)題.Rustogi等[14]研究了增加機(jī)器數(shù)目對(duì)極小化最大完工時(shí)間和總完工時(shí)間的影響.此外Jiang等[15]和Lee等[16]分別研究了半在線情況和雙目標(biāo)函數(shù)問(wèn)題,給出了相應(yīng)的近似算法.

學(xué)習(xí)效應(yīng)問(wèn)題的研究,Wright等[17]首次在制造業(yè)中提出了學(xué)習(xí)效應(yīng)后,Gawiejnowic[18]將學(xué)習(xí)效應(yīng)引入到排序領(lǐng)域,Biskup等[19]在排序中引入了學(xué)習(xí)效應(yīng)函數(shù)Pjr=jra,其中Pjr是工件Jj在位置r上的實(shí)際加工時(shí)間,j是工件Jj的正常加工時(shí)間,a是學(xué)習(xí)因子.但是這個(gè)學(xué)習(xí)效應(yīng)函數(shù)有不足之處,即當(dāng)加工足夠多的工件時(shí),工件所需的加工時(shí)間會(huì)趨向于零.因此,根據(jù)Wrigh提出的學(xué)習(xí)的定義,DeJong等[20]提出了基于兩種假設(shè)的新模型,第一是隨著時(shí)間的推移,公司的技術(shù),設(shè)備和管理組織會(huì)逐漸完善,第二個(gè)是最終這兩種改善會(huì)逐漸穩(wěn)定.基于上述假設(shè),他提出了一個(gè)新的學(xué)習(xí)效應(yīng)函數(shù)Ts=T1(M+(1?M)/sm),其中Ts表示第s個(gè)產(chǎn)品生產(chǎn)的時(shí)間,T1表示第1個(gè)產(chǎn)品生產(chǎn)的時(shí)間,M表示不可壓縮因子(0≤M≤1),m是個(gè)學(xué)習(xí)因子(0

§2給出問(wèn)題的具體描述和符號(hào)定義.§3給出問(wèn)題Pm|pmtn,Li,U≤|Cmax最優(yōu)排序的一些相關(guān)性質(zhì).§4給出問(wèn)題Pm|pmtn,Li,U≤|Cmax的最優(yōu)算法.§5總結(jié)全文并討論今后的研究方向.

§2 問(wèn)題描述和符號(hào)定義

本節(jié)主要給出問(wèn)題的具體描述以及所需要的符號(hào)定義.

問(wèn)題具體描述如下:給定工件集J={J1,J2,···,Jn},工件Jj的加工時(shí)間為pj,工件的總長(zhǎng)度為.機(jī)器集合表示為M={M1,M2,···,Mm},機(jī)器Mi的單位時(shí)間加工費(fèi)用為li,不失一般性,假設(shè)l1≤l2≤···,lm.假設(shè)σ是n個(gè)工件的可行排序,Cj(σ)為Jj的完工時(shí)間,則可行排序σ的目標(biāo)函數(shù)Makespan 可表示為.記為機(jī)器Mi的完工時(shí)間,由于機(jī)器的加工費(fèi)用依賴于時(shí)間變化,根據(jù)兩種學(xué)習(xí)效應(yīng)模型L1和L2,機(jī)器Mi上產(chǎn)生的總加工費(fèi)用分別為

為了方便敘述,引入以下符號(hào).記pmax為所有工件中最大的工件長(zhǎng)度,為所有工件在j臺(tái)機(jī)器上加工的最優(yōu)目標(biāo)函數(shù)值.分別記Cmax(A)和Cmax(opt)為算法A的目標(biāo)函數(shù)值和最優(yōu)排序的目標(biāo)函數(shù)值.

§3 初步結(jié)論

§4 最優(yōu)算法

§5 總結(jié)和進(jìn)一步討論

本文主要研究了云制造環(huán)境下帶學(xué)習(xí)效應(yīng)的平行機(jī)排序問(wèn)題,目標(biāo)是在不超過(guò)預(yù)算成本的情形下極小化最大完工時(shí)間,對(duì)兩種學(xué)習(xí)效應(yīng)函數(shù)給出了統(tǒng)一的最優(yōu)可中斷算法.后續(xù)的研究將考慮工件不可中斷情形,由于該問(wèn)題是NP-難問(wèn)題,將主要考慮其近似算法的設(shè)計(jì)與分析或者多項(xiàng)式時(shí)間近似方案(PTAS).此外可將此類問(wèn)題的機(jī)器環(huán)境推廣到同類機(jī)情形.