□盧斌

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

指派問題在鑄件產(chǎn)品精整任務(wù)中的應(yīng)用

□盧斌

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

指派問題是一個經(jīng)典的運籌學(xué)問題。介紹了鑄件產(chǎn)品精整任務(wù)分配的指派問題，利用微軟Office Excel軟件進(jìn)行求解，得到最短產(chǎn)出周期，進(jìn)而提高關(guān)鍵產(chǎn)品的產(chǎn)出效率，為企業(yè)的精整任務(wù)提供了一個有效解決方法。

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

典型的指派問題有將工作分配給機(jī)器、向代理分配任務(wù)、將銷售人員分配給銷售區(qū)域、將合同分配給投標(biāo)人等。

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

1 指派問題的一般線性規(guī)劃模型

為了展示一個包含m個代理和n個任務(wù)的指派問題的一般線性規(guī)劃模型，設(shè)定：

則一般線性規(guī)劃模型為：

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

2 解決指派問題的現(xiàn)實意義

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

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

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

表1 鑄鍛公司近4年典型鑄件產(chǎn)品產(chǎn)量

3 鑄件產(chǎn)品精整指派模型的建立

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

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

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

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

表2 鑄件各精整單位與產(chǎn)品精整周期天

（2）圖1為精整指派問題的一個網(wǎng)絡(luò)示意圖。節(jié)點對應(yīng)精整單位與產(chǎn)品，連線代表項目精整單位與產(chǎn)品可能的分配。每個起點節(jié)點的供給和終點節(jié)點的需求都是1。

圖1 鑄件產(chǎn)品精整指派問題的網(wǎng)絡(luò)模型

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

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

3家單位的精整完成時間之和就是完成產(chǎn)品精整的總天數(shù)，因此目標(biāo)函數(shù)表達(dá)為

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

將目標(biāo)函數(shù)和約束條件組合在一起，形成一個模型，即具有9個變量和6個約束條件的鑄件產(chǎn)品精整任務(wù)指派問題線性規(guī)劃模型：

4 鑄件產(chǎn)品指派問題的求解結(jié)果與分析

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

圖2 鑄件產(chǎn)品精整指派問題的求解

表3 鑄件產(chǎn)品精整指派問題最優(yōu)解

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

圖3 鑄件產(chǎn)品精整指派任務(wù)的靈敏度分析報告

5 問題的變形

精整項目指派問題存在變形與相應(yīng)調(diào)整。

（1）由于管理的需要，可能會對某些精整單位進(jìn)行業(yè)務(wù)增加與減少，此時都可以通過相應(yīng)的約束設(shè)置進(jìn)行求解計算。如允許一個單位承接兩件產(chǎn)品，可以相應(yīng)調(diào)節(jié)約束值為2，并進(jìn)行重新規(guī)劃。

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

6 結(jié)論

（1）鑄件產(chǎn)品精整的任務(wù)指派模型是一個便捷、準(zhǔn)確、動態(tài)的任務(wù)指派模型，可以隨時根據(jù)計劃的變化做出調(diào)整，從而尋求最短精整天數(shù)，加快產(chǎn)出，改變當(dāng)前隨機(jī)安排、效率不高的現(xiàn)狀。

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

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

[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]安德森，斯威尼，威廉斯，等.數(shù)據(jù)、模型與決策：管理科學(xué)篇（原書第13版）[M].侯文華，譯.北京：機(jī)械工業(yè)出版社，2012.

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

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

[8]吳衛(wèi)明.迪莎鑄造生產(chǎn)線舊砂冷卻自動加水系統(tǒng)的研制[D].上海：上海交通大學(xué)，2001.

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

[10]呂亞臣，任運來，齊作玉.構(gòu)建新一代大鍛件工藝與質(zhì)量控制系統(tǒng)[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.

指派問題；鑄件；精整；軟件；應(yīng)用

Assignment Problem；Casting；Finishing；Software；Application

TH186

A

1672-0555（2017）01-14-04

2016年10月

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