【摘要】：批處理機調(diào)度是調(diào)度問題的一個重要分支。不同于經(jīng)典調(diào)度問題,在批處理機調(diào)度問題中,一臺機器可以同時加工多個工件。由于這類調(diào)度問題不僅需要將工件指派到機器上,還包含將工件分批的決策問題,因此比經(jīng)典調(diào)度問題更為復(fù)雜,很多已知的批調(diào)度問題均是NP難解問題。 批處理機調(diào)度在現(xiàn)實生產(chǎn)環(huán)境中有著廣泛的應(yīng)用,包括半導體芯片生產(chǎn),鋼鐵制造,貨物運輸?shù)�。合理的調(diào)度方案可以大幅提高生產(chǎn)效率,節(jié)省生產(chǎn)成本,因此對批處理機調(diào)度問題的研究有著重要的現(xiàn)實意義。 盡管當前已有不少文獻對批處理機調(diào)度問題進行研究,但這些研究仍然有著不足之處。一是研究的問題主要側(cè)重于工件具有相同尺寸的較簡單情形,較少涉及不同尺寸工件情況。二是求解方法多是設(shè)計精確求解算法解決小規(guī)模問題或是用簡單啟發(fā)式算法獲得近似解,對于復(fù)雜的構(gòu)造式方法較少有人研究。三是研究的目標集中在以makespan為代表的生產(chǎn)效率型目標,而對于調(diào)度問題中的能源效率則鮮有關(guān)注。 針對當前研究中存在的問題,本研究主要做了以下工作: (1)從聚類視角下研究了不同尺寸工件批處理機調(diào)度問題。論證了差異工件單機環(huán)境下的批調(diào)度問題實質(zhì)為一種廣義聚類問題,為求解該問題提供了一個新的途徑。提出了批的空間浪費比的概念,將最小化C max的目標函數(shù)變換為最小化批的加權(quán)空間浪費比,從而可以更容易地尋找啟發(fā)式信息指導分批過程,兩者的等價性也在文中給出了證明。此外,以批的空間浪費比為基礎(chǔ),進一步定義了批間的距離度量,提出了批的約束凝聚聚類算法CACB,并通過實驗驗證了算法的有效性。 (2)將不同尺寸工件的批處理機調(diào)度問題推廣到工件動態(tài)到達的并行機環(huán)境,提出并證明了該問題的兩個不同下界。在此基礎(chǔ)上設(shè)計了兩種智能優(yōu)化算法。一是基于工件序列編碼的遺傳算法,通過工件序列和Best-Fit規(guī)則生成分批,并設(shè)計了一個ERT-LPT算法來安排批在機器上的加工。另外一種是基于構(gòu)造式分批的蟻群算法,算法同時考慮工件在尺寸和加工維度的特點作為啟發(fā)式信息,指導螞蟻不斷尋找適合的工件加入當前批,直到所有分批構(gòu)造完畢。對兩種算法的性能及偏好,通過大量仿真實驗進行了比較。 (3)將能源效率問題融入調(diào)度領(lǐng)域的研究中。構(gòu)建了在分時電價條件下,以最小化電力成本和makespan為目標的柔性流水車間批調(diào)度問題的模型。設(shè)計了三種不同的多目標優(yōu)化算法來求解該問題:即偏好向量蟻群系統(tǒng)PVACS,基于NSGA-II和基于SPEA2的進化算法,并比較了三種算法在不同評價指標下的性能。
【學位授予單位】：中國科學技術(shù)大學
【學位級別】：博士
【學位授予年份】：2011
【分類號】：F273;F224
【圖文】：

仿真實驗進行了比較。（3）考慮電力成本的柔性流水車間批調(diào)度問題的建模與多目標優(yōu)化研當前制造業(yè)的一個研究熱點就是綠色制造問題。而在生產(chǎn)調(diào)度領(lǐng)域，電在總生產(chǎn)成本中占據(jù)較高比重。如何在及時完成生產(chǎn)任務(wù)的前提下進行度，降低制造企業(yè)的電力成本，是極具現(xiàn)實意義的問題。本文以鋁片生產(chǎn)制造為背景，構(gòu)造了在分時電價條件下，柔性流水車間的批調(diào)度問題模型。以最小化最大完工時間和電力成本為目標，設(shè)計了SGA-II（Non-dominated Sorting Genetic Algorithm - II），SPEA2（Strento Evolutionary Algorithm 2）的多目標優(yōu)化算法。并將用戶偏好融入到多群算法的搜索過程，提出了 PVACS（Preference VectorAnt Colony Syste，并比較了三種算法在不同指標下的性能。2 結(jié)構(gòu)與內(nèi)容安排本文的研究主要以算法為主線展開，論文的總體結(jié)構(gòu)如圖 1.2 所示。

圖 2.1 聚類問題描述盡管如此，通常的聚類算法不能直接用于求解批調(diào)度問題，兩者還有著明顯的差別：（1）目標函數(shù)不同。傳統(tǒng)聚類算法的目標一般是最小化簇內(nèi)差異，而最大化簇間差異，因此，其目標函數(shù)一般為以下形式(Pinter and Pesti, 1991)：KpPDFDSDSKK()min||{(),,()}||1=…∈πX (2.11或abpPRFRSSabKKK( )=max||{(,),1≤≤≤}||∈πX (2.12其中aS 表示第 a 個簇， ()aD S是其直徑， (,)abR SS是簇 a 和簇 b 間的距離或相異度。Kπ 表示將對象劃分為 K 個子集的所有聚類方案的集合， {,,}K1 KP = SS是聚類的結(jié)果，符號p|| ||為pl 模。而分批問題的目標是最小化各批總加工時間。（2）距離或相異度度量不同。傳統(tǒng)聚類問題多用歐氏距離或 Minkowski距離(Xu and Wunsch, 2005)：nndDistancexx1/|| = ∑ (2.13

圖 2.2 具有不同利用率和負載均衡率的兩個批a由 2 個工件組成，加工時間和尺寸均為 ( 6,8)和 (1 ,1)。假設(shè)機器容批 a 的利用率 =0.900aUR ，負載均衡率 =0.286aBR ；批 b 由 3 個工件 ( 6,2)， (3 ,2)和 (1 ,6)。則批b 的利用率 =1.0bUR ，負載均衡率 =0.bBR a。但顯然，批a造成的浪費要明顯小于批b 。因此，很可能會出均利用率和平均負載均衡率都好于方案乙，目標函數(shù)值卻劣于方此外，因為批的利用率和負載均衡率分別從不同角度定義，兩者的度量標準，也難以進行比較和統(tǒng)一。此，本文提出批的空間浪費比的概念，并以此為基礎(chǔ)，給出聚類度量。義 2.1 批b 中由于工件加工時間差異使機器加工該批時造成的浪費空間，其量綱用工件的加工時間 p與工件尺寸s的乘積來度量下：∑= jjbIWS (b )(pp)s

【引證文獻】

相關(guān)博士學位論文 前1條

1 胡常偉;不一致熔煉任務(wù)的平行機批調(diào)度問題研究[D];廣東工業(yè)大學;2013年

相關(guān)碩士學位論文 前2條

1 宋浩;智能優(yōu)化算法在考慮加工成本的多目標差異工件平行機批調(diào)度問題中的應(yīng)用研究[D];安徽大學;2014年

2 朱鑫;平行多機模具熱處理車間動態(tài)批調(diào)度方法研究[D];廣東工業(yè)大學;2014年

本文編號：2772930