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

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

§1 引 言

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

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

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

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

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

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

2009年李伯虎等[1-3]首先提出了云制造這一概念并對其進行了定義.現(xiàn)有的大多數(shù)文獻主要研究云制造的服務(wù)模式以及服務(wù)技術(shù)層面[4-6],很少考慮云制造環(huán)境下的資源調(diào)度和生產(chǎn)管理問題.Li等[7]首先研究了云制造環(huán)境下的平行機排序問題Pm|U≤|Cmax,分別考慮工件可中斷與不可中斷情形.對于可中斷情形,給出了一個最優(yōu)解算法,對于不可中斷情形,設(shè)計了一個最壞情況界為2的近似算法.此后,Li等[8]研究了機器帶有固定租用成本的同類機排序問題Qm|U≤|Cmax,針對機器速度越大,機器速度與機器費用比值也越大的特殊情況,分別給出了可中斷和不可中斷近似算法.劉淑丹等[9]則給出了同類機情形下更一般的結(jié)果.

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

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

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

§2 問題描述和符號定義

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

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

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

§3 初步結(jié)論

§4 最優(yōu)算法

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

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