指派问题在铸件产品精整任务中的应用

□卢斌

上海电气上重铸锻有限公司上海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—），男，本科，工程师，主要从事大型铸件生产制造与管理工作