指派問題在鑄件產品精整任務中的應用

□盧斌

上海電氣上重鑄鍛有限公司上海200245

指派問題在鑄件產品精整任務中的應用

□盧斌

上海電氣上重鑄鍛有限公司上海200245

指派問題是一個經典的運籌學問題。介紹了鑄件產品精整任務分配的指派問題，利用微軟Office Excel軟件進行求解，得到最短產出周期，進而提高關鍵產品的產出效率，為企業的精整任務提供了一個有效解決方法。

線性規劃是一種幫助管理者制定決策和解決問題的方法，在激烈的商業競爭中應用廣泛。指派問題是一種特殊的線性規劃問題，很多決策過程中都會產生指派問題。

典型的指派問題有將工作分配給機器、向代理分配任務、將銷售人員分配給銷售區域、將合同分配給投標人等。

指派問題中一個很明顯的特征是一個代理分配且僅分配一個任務，具體而言，就是尋求一組分配，能夠使所設立的目標最優化，如成本最小、時間最短或利潤最大[1-5]。

1 指派問題的一般線性規劃模型

為了展示一個包含m個代理和n個任務的指派問題的一般線性規劃模型，設定：

則一般線性規劃模型為：

本模型的顯著特征是，一個代理只能指派給一個任務，并不存在指派問題的變形，比如代理人承擔多個任務，或多個任務由一個人承擔。本指派問題其實是一種特殊的運輸問題，即所有的需求與供給都是相等的，都為1，因此這個問題的最優解為整數，非1即0。

2 解決指派問題的現實意義

上重鑄鍛公司在鑄件造型方面有一定的技術開發能力，掌握了一定的核心技術，但是與國外水平相比，還有一定差距。實際生產中，鑄件產品的精度問題是一個有待合理安排、提高效率的瓶頸問題[6-8]。

鑄件產品是鑄鍛公司的核心產品，鑄件產品產出的多少直接影響公司的訂單數量與經濟效益。追求產出最大化，就是追求市場份額與利潤的最大化。其中，對利潤邊際貢獻最大的典型產品是高效、清潔的能源產品，如核電、超超臨界汽缸等[9]。

鑄鍛公司近4年形成銷售的關鍵典型鑄件產品的產量見表1。表1中汽缸（普）指普通汽缸，汽缸（超）指超超臨界汽缸。由表1可以看出，近4年來，鑄鍛公司汽缸類產品形成產出的最高年產量為39套，尚未達到60套，且無法滿足更多的市場需求。加之產品的轉型與市場需求的多元化，要在現有基礎上進一步增加諸如新閥殼、軍品等的產量，對生產安排與組織而言是很大的挑戰。現有的安排模式主要靠人工隨機安排，沒有清晰、科學的計算規劃。利用指派問題建立模型，可以靈活、準確地預測與安排鑄件產品精整出產，縮短交貨周期。

表1 鑄鍛公司近4年典型鑄件產品產量

3 鑄件產品精整指派模型的建立

根據鑄件的產品類別與精整代理單位，建立項目產品指派問題線性規劃模型，利用微軟Office Excel軟件“工具”中的“規劃求解”，可進行最優化求解。目標是建立一個簡單的數學模型，利用Office Excel求出模型的最優解，對求出的解進行解釋，并進行靈敏度分析。鑄件產品精整指派問題是一個最小化問題，包括9個決策變量，以及3個小于等于形式的約束條件與3個等于形式的約束條件。

Office Excel的規劃求解使用單純性算法，可以對較小規模的變量進行有效求解優化。最優化求解的目的是找出最短鑄件精整時間組合，且最快形成產品銷售，解決當前生產組織中的瓶頸因素，實現最優化生產與工藝質量控制[10]。

鑄鍛公司的鑄件產品包括很多種類，有船用件、軍品等，但隨著市場的選擇與產品升級，當前主要以汽缸和閥殼為主，其它產品的精整難度相對較低，周期相對較短。承接這些精整任務的單位主要有3家，以A、B、C代稱，還有一部分產品因為各種原因進行外協精整加工。對具體業務進行分析如下。

（1）A、B、C這3家精整代理單位由于管理與技術需求，原則上每次只能承接一套產品精整任務。3家精整單位和3種產品可以產生9種分配方案，各種可能的分配方案和預計精整完成時間見表2。

表2 鑄件各精整單位與產品精整周期天

（2）圖1為精整指派問題的一個網絡示意圖。節點對應精整單位與產品，連線代表項目精整單位與產品可能的分配。每個起點節點的供給和終點節點的需求都是1。

圖1 鑄件產品精整指派問題的網絡模型

（3）根據以上分析可以設計出一個線性規劃模型。使用雙下標決策變量，X11代表單位A精整汽缸（超），X12代表單位A精整汽缸（普），依次類推。由此，鑄件產品精整指派問題的決策變量為：

根據圖1與精整任務完成數據，可以給出精整完成時間的數學表達式：A單位完成精整任務所需要的天數為60X11+50X12+55X13，B單位完成精整任務所需要的天數為90X21+70X22+70X23，C單位完成精整任務所需要的天數為50X31+45X32+60X33。

3家單位的精整完成時間之和就是完成產品精整的總天數，因此目標函數表達為

精整指派問題的約束條件是為了保證每個單位能夠最多被分配給一個產品，且必須注意一個約束條件對應圖1中的一個節點，于是有：

將目標函數和約束條件組合在一起，形成一個模型，即具有9個變量和6個約束條件的鑄件產品精整任務指派問題線性規劃模型：

4 鑄件產品指派問題的求解結果與分析

鑄件產品精整指派問題的Office Excel計算結果如圖2所示，A單位承接普通汽缸產品精整，B單位承接閥殼及其它產品精整，C單位承接超超臨界汽缸產品精整，最短總精整天數為170天，最優解如表3所示。Office Excel建模的規劃求解，是對于現有生產技術過程控制中存在的突出問題給予針對性的解決辦法，同時對于包括企業資源計劃在內的信息系統而言，是一個有效補充，能更及時面對一線的生產任務，給出快速便捷的響應。

圖2 鑄件產品精整指派問題的求解

表3 鑄件產品精整指派問題最優解

如圖3所示為靈敏度分析報告，可以看出，終值欄就是決策變量的最優解。如前所述，3種產品的具體精整安排為A單位精整一套普通汽缸，B單位精整一套閥殼及其它產品，C單位精整一套超超臨界汽缸，最優解對應的遞減成本為0。在求解出最優解后，可以得到各單位在當前目標式系數下所對應的允許增量與減量，以及當前約束條件下的陰影價格變化。

圖3 鑄件產品精整指派任務的靈敏度分析報告

5 問題的變形

精整項目指派問題存在變形與相應調整。

（1）由于管理的需要，可能會對某些精整單位進行業務增加與減少，此時都可以通過相應的約束設置進行求解計算。如允許一個單位承接兩件產品，可以相應調節約束值為2，并進行重新規劃。

（2）實際產品精整中，可能會增加或者減少精整單位，也可能同時精整多件同樣的產品，或只有一件產品需要精整；此外，還可能面對各個單位都有產品正在制造，新任務周期需要調整的問題，諸如以上情況，都可以調整相應的決策變量和約束條件進行重新計算、指派。

6 結論

（1）鑄件產品精整的任務指派模型是一個便捷、準確、動態的任務指派模型，可以隨時根據計劃的變化做出調整，從而尋求最短精整天數，加快產出，改變當前隨機安排、效率不高的現狀。

（2）影響鑄件產品產出的因素很多，包括技術質量問題、精整單位本身不確定因素、客戶需求等，但是任務指派模型都可以對變化后的因素做出相應修訂，并提高效率。

（3）針對某一個問題的建模求解，是解決企業生產管理過程中存在突出問題的行之有效、及時便捷的方法。

[1]AHUJA R K,MAGNANTI T L，ORLIN J B.Network Flows: Theory,Algorithms,and Applications[M].London:Pearson Education Limited,1993.

[2]EVANS J R，MINIEKA E.Optimization Algorithms for Networks and Graphs[M].2nd Edition.Boca Raton:CRC Press，1992.

[3]GREENBERG H J.How to Analyze the Results of Linear Programs—Part 3:Infeasibility Diagnosis[J].Interfaces，1993，23（6）:120-139.

[4]NEMHAUSER G L,WOLSEY A.Integer and Combinatorial Optimization[M].Hoboken:Wiley-Interscience，1999.

[5]安德森，斯威尼，威廉斯，等.數據、模型與決策：管理科學篇（原書第13版）[M].侯文華，譯.北京：機械工業出版社，2012.

[6]張立波，田世江，葛晨光.中國鑄造新技術發展趨勢[J].鑄造，2005，54（3）：207-212.

[7]劉小龍，鐘海波.淺議鑄造生產線存在的問題及其解決辦法[J].中國鑄造裝備與技術，2001（2）：3-5.

[8]吳衛明.迪莎鑄造生產線舊砂冷卻自動加水系統的研制[D].上海：上海交通大學，2001.

[9]張靈芳，陳永波，宋雷鈞，等.AP1000主管道大鍛件研究[J].裝備機械，2013（2）：14-18.

[10]呂亞臣，任運來，齊作玉.構建新一代大鍛件工藝與質量控制系統[J].大型鑄鍛件，2010（6）：42-45.

（編輯：爾東）

Assignment problem is a classic operation research problem.Introduced the assignment problem of finishing tasks assignment for casting products.Microsoft Office Excel software was used to solve the shortest output period and in turn to improve the output efficiency of key products.This provides the enterprises an effective solution for the finishing tasks.

指派問題；鑄件；精整；軟件；應用

Assignment Problem；Casting；Finishing；Software；Application

TH186

A

1672-0555（2017）01-14-04

2016年10月

盧斌（1982—），男，本科，工程師，主要從事大型鑄件生產制造與管理工作