单件离散型生产作业排程的多目标协同优化

开篇：润墨网以专业的文秘视角，为您筛选了一篇单件离散型生产作业排程的多目标协同优化范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

摘要： 以某重机企业为背景，分析了单件离散型生产作业排程的特征，提出多目标协同优化问题。基于改进的田口质量损失函数，确立质量、工期与成本之间的非线性关系，综合考虑单件离散型的约束条件，构建了生产作业排程多目标协同优化模型。集成仿真技术和遗传算法，为模型求解提供了有效方法。最后将模型和算法应用到企业的生产实践中，验证了其实用性和有效性，为解决单件离散型生产排程问题提供了科学方法。

Abstract： Heavy machinery enterprise as research object， this paper analyses the feature of production scheduling for one-piece discrete manufacturing and proposes the collaborative multi-objective optimization problem. Based on the improved Taguchi loss function， nonlinear relationship of quality， delivery and cost is established. And the multi-objective collaborative optimization model of production scheduling is created as well as synthetically considering of one-piece discrete constraints. The effective solution was explored for solving the model Integrating simulation technique and genetic algorithm. Further， through the enterprise empirical study， the practicability and validity of the model and algorithm is verified. This study provides scientific method of production scheduling for one-piece discrete and improves the efficiency and scientific of the production scheduling.

关键词： 单件离散型；生产作业排程；田口质量损失函数；协同优化；集成算法

Key words： one-piece discrete；production scheduling；Taguchi loss function；collaborative optimization；integrated algorithm

中图分类号：TB497 文献标识码：A 文章编号：1006-4311（2014）15-0060-05

0 引言

单件离散型生产作业排程属于多零件、多目标、多约束、随机性等特征的协同优化问题。在制造业中，典型的如重型机械行业（简称重机）企业的生产方式，其特点是产品按订单设计，按客户需求生产，产品类型多，结构复杂，生产工艺流程长，制造周期长，生产设备以通用型为主[1]。质量、工期和成本成为排程的重要目标，工艺的时序性、时间、资源等成为主要约束条件，急件插单、撤单、机器故障具有随机不确定性，故此类问题的研究是个世界性难题[2，3]。当前此类企业生产作业排程主要是凭经验、以静态为主，工期难保证，效率低、科学性差，缺少多目标协同优化理论方法。因此，本研究既具有理论意义又具有实用价值。

生产作业排程优化这一NP-Hard难题吸引了国内外学者持续研究。但是关于生产作业排程多目标协同优化问题还缺少研究，关于单件离散型生产排程的协同优化研究成果更少。当前相关研究成果集中在优化模型和算法方面[4-9]，

而优化目标多数是考虑单目标，考虑多目标的较少，已有的多目标研究多以加权集成优化为主，李衍飞等[10]以工期、生产移动量、瓶颈设备最大产能利用率为多目标，进行加权集成优化；施国洪等[11]以项目总工期和在制品库存为优化目标，使用混合智能算法实行多资源约束调度；林薇[12]以制造周期、资源利用率、制造成本等为目标，使用启发式规则与遗传算法实现资源优化与作业调度。本课题组对此类问题也在持续研究，杨晓英等[1]采用的是多目标的简单加权法，建立了基于精益物流的质量、工期、成本的多目标、多约束、不确定性和非线性问题的组合优化模型，但是没有充分考虑多目标之间的相互联系相互制约的关系。实际生产排程中，多目标中的单个目标不是独立存在的，它们是相互影响、相互制约、相互耦合的关系。同时它们之间的竞争性和复杂性也使得其优化问题变得十分困难。因此本课题的研究具有一定的挑战性。

田口质量损失函数是描述质量特性值波动所造成的损失与偏离目标值的差平方或偏差均方成正比[13]。它较好地说明了质量指标与成本费用之间的非线性关系。田口质量损失函数已经成功应用于质量与成本的关系模型上[14]。本文在以往研究的基础上，以某重机企业为背景，分析单件离散型生产作业排程特征，应用改进型的田口质量损失函数[15]，确立质量、工期和成本三目标之间的关系，综合考虑多种约束条件建立三目标协同优化模型，集成仿真技术和遗传算法，求解这类复杂问题的局部最优和全局最优解。通过企业实例验证模型与算法的实用性和有效性。预期最大程度的提高质量、工期、成本三者之间的协同度，为企业生产排程提供一套行之有效的理论方法。

1 问题提出

重机企业是为基础工业提供包括矿山设备、起重运输设备、工矿车辆和冶金专用设备等机械装备的企业，其生产是典型的单件离散型制造。当前，随着市场需求的多样化、个性化和准时化，生产作业排程问题已经成为制约企业生产经营的一大瓶颈。质量、工期和成本成为生产排程的主要目标，然而质量、工期和成本三目标之间存在相互依赖、相互制约和相互耦合的关系，不能简单地加权相加。协同优化是一种针对分布式的、多级的复杂系统问题的优化方法[16]。它将复杂优化问题分解为各变量的优化，并通过系统及约束条件协调各变量之间的共享变量和耦合状态变量，最终目的是使整个系统目标最优，并通过等式约束条件来保证变量之间的耦合状态变量和共享变量的一致性。因此，运用协同优化方法将三目标转化成单目标进行优化，具有可操作性和实用性。

2 基于改进型田口质量损失函数的三目标关系模型

2.1 改进型田口质量损失函数 田口质量损失函数是由日本质量管理学家田口玄一（Taguchi）提出的，其定义为：设质量特性为X，目标值为m。当X≠m时，则造成损失，X-m越大，损失越大。设相应质量特性值X的损失函数为L（X），若L（X）在X=m处存在二阶导数，则有：

L（X）=K（X-m）2（1）

式中K是不依赖于X的常数，由功能界限Δ0和丧失功能的损失A0决定，K=A0/Δ■■。由于客户对质量特性值所能容忍的质量变异程度不同，则目标值两边损失函数曲线也不相同，即质量损失函数呈现不对称，如图1所示。

为此，潘尔顺等[15]对田口损失函数进行了改进，提出了不对称的田口损失函数，并建立了相应数学模型如

式（2）：

L（X）=■■k■（X-μ）■×exp-■dX

+■■k■（X-μ）■×exp-■dX（2）

式中：k1=LL/ΔT■■，为下限对应的质量损失系数；k2=LU/ΔT■■，为上限对应的质量损失系数，ΔT1为质量特性值规定的下限变异；ΔT2为质量特性值规定的上限变异，LL为质量特性值下限对应的质量损失；LU为质量特性值上限对应的质量损失；μ为质量特性值均值；σ为质量特性值标准差。该模型真实地表达了质量与损失之间的关系，X代表每个产品零部件的实际质量特性值。以下基于改进型的田口质量损失函数建立质量成本关系模型。

2.2 参数设置 设有M台机器和N个待加工工件，每个工件包含n道工序，各工序之间有工艺时序约束。qij表示产品i的第j个零件加工质量（如加工精度等级），tij表示产品i的第j个零件的工期，μ■■表示产品i的第j个零件加工质量均值（即目标值），Δqij表示产品i的第j个零件加工质量的下限变异，Δq′ij表示产品i的第j个零件加工质量的上限变异，μ■■表示产品i的第j个零件的工期平均值（即目标值），Δtij表示产品i的第j个零件的工期下限变异，Δt′ij表示产品i的第j个零件的工期上限变异，k■■表示产品i的第j个零件在加工质量目标值下限变异范围内的质量损失系数，k■■表示产品i的第j个零件在加工质量目标值上限变异范围内的质量损失系数，k■■表示产品i的第j个零件在工期下限变异范围内的质量损失系数，k■■表示产品i的第j个零件在工期上限变异范围内的质量损失系数，σq是产品加工质量标准差，σt是产品工期标准差，σ■■为产品i的加工质量标准差，σ■■为产品i的工期标准差，C■■为第i个产品第j个零件的正常目标成本，C■■为第i个产品第j个零件的质量损失费用，C■■为第i个产品第j个零件的工期损失费用，C表示产品的实际成本，等于所有零件的正常目标成本成本加上质量损失费用、工期损失费用之和。

2.3 质量成本关系模型 产品或项目质量、成本、工期三者之间存在非线性，如图2所示。

基于改进型质量损失函数式（2），建立质量成本关系模型。产品成本包括正常目标成本与因过程变异引起的质量损失。设第i个产品的j个零件正常目标成本为C■■（含直接成本和间接成本），质量损失为C■■，若产品质量特性值在均值下限公差范围内，说明产品质量特性值高于均值，成本就会增加，此时kqij=L■■/Δqij，L■■为加工质量在规定下限对应的质量损失；若产品质量特性值在均值上限公差范围内，说明产品质量特性值低于均值，也会造成一定的损失，此时kq ′ij=L■■/Δq′ij，L■■为加工质量在规定上限对应的质量损失。本文所指的质量特性均值即质量特性值的目标值。因此质量成本关系模型如式（3）：

C■■=■■k■■（q■-μ■■）■×exp-■dq+

■■k■■（q■-μ■■）■×exp-■dq（3）

2.4 成本工期关系模型 依据图2可见，成本与工期关系与质量成本关系类似，也是非线性关系，工期要求越短成本越高。由于需要通过赶工、提高效率等措施缩短工期，则成本相应增加。工期和成本都有一个目标值，超过目标值，随着时间的延长也会相应增加成本。依据改进型质量损失函数同样可以得到工期损失函数。

设第i个产品的j个零件工期变动造成的损失为

C■■，若产品工期在规定工期下限公差范围内，说明产品工期在规定工期范围内，此时认为无损失，k■■=0；若产品工期在规定工期均值的上限公差范围内，说明产品实际工期超过规定工期，此时造成一定的损失，此时k■■=L■■/Δt′■，L■■为超过工期一天对应的费用损失，超过一天的费用损失按合同规定计算。则工期损失函数为式（4）所示：

C■■=■■k■■（t■-μ■■）■×exp-■dt+

■■k■■（t■-μ■■）■×exp-■dt（4）

3 多目标协同优化模型建立

本文针对重机企业的生产作业排程优化问题，依据式（3）和（4），将三个目标（质量、工期和成本）协同为总成本单目标进行优化，建立多目标协同优化模型。

3.1 模型假设 本文的基本假设：所有工件的工序已经确定且不能改变；所有工件各道工序的加工时间已确定；任意时刻工件只能在一台机器上加工；工件的加工是非抢占式的，工件的加工不许中断；各种搬运工具的运输费率相等[1]。本文中提到的制造质量特性均值均用产品的粗糙度（Ra）来表示。

3.2 质量工期成本三目标协同优化模型 依据式（3）和（4），将质量、工期和成本三目标协同转换为总成本目标，建立质量-成本-工期三目标协同优化模型如式（5），产品总成本等于所有零件的目标成本、质量损失和工期损失之和。C=min■■

C■■+■■k■■（q■-μ■■）■×exp-■dq+

■■k■■（q■-μ■■）■×exp-■dq+■■k■■（t■-μ■■）■×exp-■dt+

■■k■■（t■-μ■■）■×exp-■dt（5）

S.t

ts■x■？叟[ts■+t■]x■（6）

1？燮Me？燮M（7）

tij（1+ζ）？燮t′ij，？坌t∈T，T？叟0，0

X■=1，表示机器M■被选中=0，表示机器M■未被选中（9）

R■=1，工序r在M■上先于工序q加工=0，工序r在M■上后于工序q加工（10）

■X■=1 1？燮i？燮N，1？燮j？燮N，1？燮r？燮ni（11）

式（6）为工艺时序、时间约束，零件的第r道工序的开始时间要大于等于第r-1道工序的开始时间和加工时间之和；式（7）为设备能力约束；式（8）为不确定约束，考虑随机因素宽ζ；式（9）式（10）为调节变量；式（11）为其他约束，工序在固定时刻只能在一台机器上加工。

4 算法设计和仿真建模

4.1 遗传算法

①编码：本文采用基于产品零件符号的编码方法，染色体由所有零件的代码组成。排程方案由零件基因在染色体中的出现的先后顺序构成。假设pij表示产品i的第j个零件，染色体基因编码为p（n=1，2，…，i×j），染色体长度为i×j。pij的工序编码为r（r=1，2，…，q），Me为机器设备其编码为e（e=1，2，…，Ne），矩阵[ij，r，Me，tijrs，tijre]为作业排程解码结果空间，各个零件的加工工序、设备及其开工时间与完工时间是由该矩阵转化成甘特图得到的。

②适应度评估：本文根据适应函数，利用每个个体在种群中的适应函数值来进行进化搜索[17]。适应度函数由目标函数公式（5）经尺度变换得到，如公式（12）：

fitness（x）=-min■β■Z■（12）

③遗传操作：本文的操作设置是采用生产系统仿真软件中的的遗传算法功能模块进行的，其中包括群体规模M、时代级别、变异概率pm、世代数、交叉概率pc和终止的代数等。

④终止条件确定：规定一个最大的遗传代数T，进行算法迭代，当达到预先设定的最大繁殖代数的次数时，算法自动停止。

4.2 仿真建模

Step1：仿真建模。基于某重机企业的机器设备、产品型号、零件制造工艺等实际生产情况构建离散型的系统物理模型，在此基础上根据系统各要素之间的关系构建数学模型。根据订单、产品和设备等信息采用Plant Simulation仿真软件构建系统仿真模型，设置相应的模型参数，对比模型与现实系统，反复进行模型的调试、校正和确认。

Step2：仿真实验。为模型设定初始条件、运行的时间长度、仿真次数等，同时运行模型，观察实验结果。若模型中途停止运行，则返回Step1，对遗传算法模块语言进行修改；如果模型运行无误，则进行Step3。

Step3：仿真结果分析。仿真评估阶段，分析仿真结果，同时对比企业的实际生产排程结果，以验证模型和算法的有效性和实用性。

5 实例研究

5.1 数据分析 本文的排程研究以某重机企业生产的水泥磨机为例。水泥磨回转部分包括筒体、（进出料）端盖、（进出料）中空轴等三大关键零部件。现有3.2×13型、2.4×13型与2.6×13型三类水泥磨的筒体、端盖、中空轴的产品名称、代号、加工质量目标值、加工质量实际值、加工质量上下限、数量需求、交货期、单件重量等订单信息，如表1所示，从实际应用出发，加工质量目标值、Δqij、Δq■■和实际加工质量为：筒体和中空轴采用的是同轴度（mm）；端盖采用的是粗糙度（μm）。产品和产品零件分别用Pi和Partij（i=1，2，3；j=1，2，3）表示。主要需求是运用协同优化模型和集成算法提出某计划期内生产作业排程最优方案。

表2所示的是设备代码、设备数量的信息表，本实例共用到13种设备机型，代码为Me（e=1，2，…，13），其中M2、M4有2台，M12、M13有若干台。表3给出了零件的加工工艺和各工序工时定额。若产品加工质量在目标值下限变异范围内，说明产品加工质量高于目标值，成本就会增加，此时每吨增加成本为L■■=45元，若产品加工质量在目标值上限变异范围内，说明产品加工质量低于目标值，此时每吨成本增加为L■■=45元。若产品交货期在规定交货期上限变异范围内，说明产品实际交货期超过规定交货期，此时造成一定的损失，拖期一天按合同金额的千分之一计算，产品的正常目标成本根据企业调研一般占销售金额的百分之九十，加工质量标准差σ■■和交货期标准差σ■■根据企业实际调研得出经验值分别为0.1mm（同轴度标准差），0.04μm（粗糙度标准差）和0.6天（交货期标准差）。根据企业实际情况，若产品在交货期目标值下限范围内，则不考虑造成的损失费用，即k■■=0，因此不再考虑Δtij。

5.2 仿真模型建立 根据产品、设备和工艺等基本信息，嵌入多目标协同优化模型，建立系统的Plant Simulation仿真模型对实例进行验证。根据实际情况，产品制造从某年10月28日开始。零件质量指标按收集的企业实际数据嵌入协同优化模型中进行计算。各种零件从Source对象进入系统，从Drain对象离开系统。其中Source对象的触发形式为表格触发，在触发delivery表格里设置零件毛坯的到达时间和需求量，每个零件的开工时间。在各个分流对象FlowControl中设置退出策略，即有零件退出对象时调用distribute方法实现零件工艺路线的选择。所有零件走的是一个环形路线，Part11，Part21，Part31加工完之后经过FCO1走3路线，Part12，Part22，Part32加工完之后经过FCO1走4路线，然后在M12上进行装配；Part13，Part23，Part33加工完之后经过FCO1走5路线，最终和其他零件在M12进行装配。仿真模型和其中Part12的具体路线如图3所示。

5.3 基于遗传算法的最优解搜索 将遗传算法嵌入以上的仿真模型中，设交叉概率为0.9，变异概率为0.15，遗传种族为20，种群规模为100。优化参数按照零件达到的先后来设置，适应度函数为协同优化目标函数。通过仿真优化后得到的适应度收敛值如图4所示，其中红线代表最优解，绿线代表平均值，蓝线代表最劣解，种族数代数在图中以横坐标来表示，适应度值用纵坐标来表示。适应度最优评估值为2.78982万元，获得的计划安排最优方案甘特图如图5所示。

5.4 结果分析 通过以上协同优化模型及其算法，经过仿真+遗传算法试验，取得了生产排程的满意解。经过质量工期成本的协同优化，获得了综合三目标的优化方案。将这种方法与企业实际人工排程结果进行对比，如表4所示。结果显示，该生产排程经过协同优化，最终为企业减少了成本损失10.834万元，提高生产排程效率近55.8%。

6 结论

本文引入改进型田口质量损失函数对单件离散型生产排程进行了研究，将质量、工期和成本三目标协同转换为产品总成本目标，包括所有零件的目标成本、质量损失和工期损失之和，综合考虑工艺时序、时间、设备能力、随机不确定性因素等约束条件，建立了多目标、多约束、随机性问题的协同优化模型，运用仿真建模和遗传算法对模型进行了求解。并将模型与算法进行实际应用，得到了生产作业排程的最优解，校验了模型的有效性和实用性。较之简单的加权法，协同优化方法可以更大程度提高质量、工期、成本三者之间的协同度，取得的解分布更加均匀，提高了生产排程的合理性和高效性，更大程度地降低了企业的成本损失。该方法为单件离散型生产排程问题的优化研究提供了一种新的思路。

参考文献：

[1]杨晓英，施国洪，王雪，孙华岳.基于精益物流的单件离散型生产作业排程优化研究[J].工业工程与管理，2013，18（3）：11-18.

[2]K.G. Kempf.et.al. Planning Production and Inventories in the Extended Enterprise：A State of the Art Handbook [J]. Springer New York Dordrecht Heidelberg London，2011，1.

[3]周光明.多品种小批量生产作业计划控制优化研究[J].现代制造工程，2010（10）：38-42.

[4]Susan K. Monkman， Douglas J. Morrice， Jonathan F. Bard. A production scheduling heuristic for an electronics manufacturer with sequence-dependent setup costs[J]. European Journal of Operational Research，2008（187）：1100-1114.

[5]Jennifer Mu oz Blás. Development of a time-efficient heuristic method for production scheduling with resource constraints and changeover considerations. INDUSTRIAL ENGINEERING UNIVERSITY OF PUERTO RICOMAYAG ■ EZ CAMPUS December，2007.

[6]于晓义，孙树栋，褚崴.基于并行协同进化遗传算法的多协作车间计划调度[J].计算机集成制造系统，2008，14（5）：991-1000.

[7]易军，李太福.求解作业车间调度的变邻域细菌觅食优化算法[J].机械工程学报，2012，48（12）：178-183.

[8]Massimiliano Caramia， Stefano Giordani. A fast metaheuristic for scheduling independent tasks with multiple modes[J]. Computers & Industrial Engineering，2010（58）： 64-69.

[9]AntonioLova，PilarTormos，Mariamar Cervantes， Federico Barber. An efficient hybrid genetic algorithm for scheduling projects with resource constraints and multiple execution modes[J]. Int. J. Production Economics，2009（117）： 302-316.

[10]李衍飞，江志斌.半导体晶圆制造系统的时变多目标生产调度优化[J].上海交通大学学报，2008（2）：209-213.

[11]施国洪，陈敬贤等.基于混合智能算法的多资源约束项目优化调度[J].工程设计学报，2008，04.

[12]林薇.多目标多约束环境下的生产计划与作业调度方法研究[D].东华大学硕士学位论文，2008.

[13]李佳翔，韩之俊.基于田口方法的小批量生产过程控制[J].工业工程与管理，2009（1）：31-35.

[14]杨晓英.云制造模式下大型装备成套服务运作协同与优化[D].江苏大学博士论文，2013：06.

[15]潘尔顺，李庆国.田口损失函数的改进及在最佳经济批量中的应用[J].上海交通大学学报，2005，39（7）：1120-1122.

[16]薛飞，余雄庆，姚卫星.轻型飞机机翼气动/结构协同优化研究[J].计算力学学报，2005，22（4）：488-491.

[17]郑波克，杨晓英.转移批量自适应的作业排程优化方法[J].河南科技大学学报：自然科学版，2012，33（2）：17-21.