基于多約束聚類的企業生產計劃與質量設計優化模型

朱曉寧，張 群，顏 瑞，馬風才

（北京科技大學 東凌經濟管理學院，北京 100083）

0 引言

現在鋼鐵產品的需求越來越呈現多品種、小批量的特點，而鋼鐵產品的生產批量又很大，為了在多品種、小批量的生產模式下節能降耗和減少成本，鋼鐵企業通常采用基于成組技術的同成分合同合爐冶煉、同規格訂單合批軋制的批量計劃方案組織生產[1]。在這種生產模式下，質量設計不僅需要基于標準對單個產品進行設計，還需要對不同鋼級產品的批量質量進行標準+α[2]的設計,α是高于或嚴于標準規定的產品特性，是為了保證批量生產的不同產品既能達到質量要求,又盡可能減少因質量等級過高而產生的質量浪費現象。目前，對于煉鋼合爐生產計劃的研究大多集中在煉鋼—連鑄階段最優爐次計劃的確定上。軋鋼批量生產計劃的研究大多集中在板帶鋼、型鋼和無縫鋼管以及煉鋼—連鑄—連軋的集成生產批量計劃與調度上。張文學和李鐵克[3]在分析鋼鐵生產中的鋼軋一體化批量計劃編制問題基本特征的基礎上給出了一體化編制策略,并建立了問題的約束滿足優化模型。針對模型的NP難特性，提出了一種將改進離散粒子群算法、約束滿足和鄰域搜索相結合的混合算法。Kim等[4]建立了質量設計與生產計劃集成概念模型，但是并沒有提出定量模型。楊靜萍等[5]分析了面向組批生產計劃的鋼鐵產品質量設計的特點及生產計劃的集成性，提出了基于帶空間和容量約束的聚類分析的組批質量設計方法，但是其模型沒有考慮成本因素，本文則在文獻[4]、[5]的基礎上進行改進，增加了生產成本約束和爐成本約束，研究如何在盡可能滿足爐容量、生產成本、爐成本、規格范圍和交貨時間約束下，盡可能將質量差別小的訂單安排在相同的爐次生產，從而優化鋼鐵企業批量生產計劃與質量設計的集成模型。

1 面向訂單的鋼鐵企業批量生產計劃與質量設計集成原理

（1）根據客戶需求對各單一合同進行質量特性設計。

（2）對于相似合同，根據質量特性差異大小，按照批量容量限制對這些合同進行聚類劃分，將質量特性取值范圍相同或相近的合同盡量分在同一組批中，以便減少由于低要求高標準生產而帶來的質量損失。

（3）計算各組批聚類的中心，得到組批質量特性值及α值。

2 面向訂單的鋼鐵企業生產計劃與質量設計集成優化模型

2.1 模型建立

然后把所有合同按質量特性向量進行分類，歸入不同的集合中，使得每個集合內的質量特性差異最小。

模型描述如下：

（1）有不同型號（容量不同）的爐，每個爐有不同的固定成本和變動成本；

（2）有多組質量特性不同的生產合同，將所有生產合同按質量特性分成不同的批次形成生產計劃；

（3）根據產品質量要求安排對應爐完成生產計劃，每個爐可以完成一個批次的生產合同，每個批次只能交給一個爐完成，爐與批次是一一對應的關系；

（4）每個爐安排的生產任務不能超過其容量限制，每個爐的總生產成本不能超過其總成本上限；

（5）目標函數是各個批次內生產合同的質量特性差異之和最小，質量特性差異由質量特性向量之間的歐氏距離表示。

給出各個符號的意義，如表1所示。

表1 鋼鐵企業批量生產計劃與組批質量設計的優化模型符號及解釋

2.2 算法設計

遺傳算法是一種有效的全局搜索算法，由美國Michigan大學的J.Holland[6]教授在1975年提出的。遺傳算法各部分的策略為：

（1）編碼規則。根據問題特點，采用混合編碼方式，對決策變量xlt采用二進制編碼方式，對決策變量Ot采用實數編碼。例如，假設把3個合同分成2個批次，每個合同有2個維度的質量特性，則染色體表示的生產計劃為合同1、2劃入第一個批次，合同3劃入第二個批次，其中批次1的質量特性中心點為（0.1,0.2），批次2的質量特性中心點為（0.15,0.15）。

（2）適應度函數。模型為求最小值問題，對于此類問題通常選擇目標函數的倒數作為適應度函數，但是考慮到目標函數取值范圍未知，為了提高算法的泛化能力，考慮用如下公式作為適應度函數：

（3）選擇算子。選擇操作提供了遺傳算法的驅動力，驅動力太大則遺傳搜索將過早終止，驅動力太小則進化過程將非常緩慢。本文采用輪盤賭選擇策略，其基本原理是根據每個染色體適應度的比例來確定該個體的選擇概率或生存概率。為了實現最優保存策略，當前種群中的最優染色體直接進入下一代。

（4）交叉算子。交叉操作是交換兩個染色體部分基因的遺傳操作。根據交叉概率Pc選擇進入配對池的父代個體，把父代染色體中的部分基因加以替換重組，產生子代個體。由于本文染色體編碼由兩部分組成，所以需要采用混合交叉算子，具體方法為：第一部分采用均勻交叉；第二部分采用雙點交叉。均勻交叉算子：首先隨機地產生一個與染色體第一部分基因串等長的二進制串，0表示交換，1表示不交換，根據二進制串判斷是否交換父代個體對應位置上的基因。雙點交叉算子：首先隨機產生兩個個基因位置，然后直接將配對染色體對應位置上的基因互換。

（5）變異算子。變異操作是產生新個體的輔助方法，它決定了遺傳算法的局部搜索能力，同時保持種群的多樣性。變異操作依據變異概率Pm對每代種群中的染色體進行基因突變，常用的基因突變方式有均勻、交換、逆轉和位移等，根據本文編碼規則的特點，采用混合變異算子。對染色體第一部分基因串使用均勻變異算子，對應基因直接在0和1之間進行變異，對染色體第二部分基因串使用雙點變異算子，對應基因分別以0.5的概率翻倍或減半。

（6）調整非可行解。對于交叉操作和變異操作中產生的非可行解進行調整。每個合同都必須且只能劃入一個批次中，因此同一合同的所有基因只能有一個取值為1，其余基因取值為0，當同一合同的基因有兩個或兩個以上取值為1時，隨機選擇一個位置令該基因值為零，當所有基因均為零時，隨機選擇一個位置令該基因值為1。染色體第二部分采用實數編碼，所有操作均不會導致非可行解情況出現。

根據遺傳算法各部分的策略，得到算法步驟如下：

（1）參數初始化：設定最大迭代次數G，初始種群規模Popsize，交叉概率Pc，變異概率Pm；

（2）種群初始化：隨機產生Popsize個可行解作為染色體，構成初始種群，令g=0；

（3）種群更新：更新當前種群，用第g代種群替代當前種群；

（4）計算適應度：計算當前種群中各染色體的適應度值，適應度值最高的染色體直接進入下一代；

（5）遺傳操作：對當前種群進行選擇、交叉和變異操作，產生新的種群；

（6）非可行解調整：對新的種群中非可行解進行調整；

（7）終止條件：若g=G，則算法終止，輸出當前種群中的最優染色體；若g＜G，則更新當前種群，轉Step3，g=g+1。

3 實例分析

選取包鋼2011年7～8月訂單進行實例研究，包鋼現在共有10個轉爐，210t×2，150t×2，120t×2，80t×4，每種類型爐的固定成本（元/爐次）和單位成本（單位：元/t）如表2所示。

表2 不同爐類型基本情況表

選取了7～8月的61個訂單(訂單信息略)。

表3 不同鋼鐵產品標準聚類情況表

首先對訂單進行預處理，預處理的步驟如下：

（1）剔除可以整爐生產的訂單；

（2）將同標準的訂單歸到一起，計算同標準的訂單需求總量；

（3）同標準訂單需求量減去整爐生產量，得到該類標準產品合爐量；

（4）對質量設計參數進行預處理。

通過預處理后，共有16種標準，各標準的訂單情況。對各合同質量設計參數均值結果進行主成分分析，根據主成分分析結果，可得到主成分表達式：

將各訂單的質量設計參數上下限值范圍代入主成分表達式，按照以上模型及算法進行求解，可得到聚類結果（表3），最終煉鋼批量生產計劃方案結果如表4所示，表明較好的解決了鋼鐵企業需求、批量生產計劃與質量設計集成問題。

表4 煉鋼批量生產計劃方案結果

4 結束語

面向訂單的批量生產計劃與質量設計集成模型基于質量特性聚類為鋼鐵產品批量生產計劃的決策提供依據，能夠滿足多品種、小批量的鋼鐵產品生產過程中不同產品批量生產的質量要求。該模型在滿足爐容量、生產成本、爐成本、規格范圍和交貨時間約束下，對不同鋼級產品的質量進行標準+α的設計，不僅滿足了多約束條件，同時降低成本。采用主成分分析法進行數據預處理，在保證數據單位和量綱一致的前提下，縮小了問題域的規模，考慮到遺傳算法較為成熟，并且對于各種特殊問題可以提供極大的靈活性來混合構造領域獨立的啟發式，從而保證算法的有效性的優點，采用遺傳算法進行求解，并針對模型特點進行算法設計。最后通過實例研究證實了該模型的科學性和有效性，能夠減少由于質量不合格或過高帶來的質量浪費，同時減少由于未滿足設備容量約束而造成的能源、人力等資源的浪費，為生產組織人員提供了定量決策依據，降低生產成本。

[1]唐立新.CIMS下生產批量計劃理論及其應用[M].北京：科學出版社,1999.

[2]那寶魁.解讀質量管理[M].北京：冶金工業出版社,2006.

[3]張文學，李鐵克.基于粒子群和約束滿足的鋼軋一體化批量計劃優化[J].計算機集成制造系統，2010，16（4）.

[4]Kim J,Seong D,Jung S,et al.Integrated CBR Framework for Quality Designing and Scheduling in Steel Industry[J].Lecture Notes in Com puter Science，2004，3155.

[5]楊靜萍，劉曉冰，王宇春等.基于多約束聚類的鋼鐵合同組批質量設計方法[J].計算機集成制造系統,2009,15(11).

[6]Holland J.Adaptation in Natural and Artificial Systems[M].Cambridge,MA：MIT Press,1975.