一种基于设计结构矩阵的车间机床调度方法

文章编号1000-5269（2024）06-0063-07

DOI：10.15958/j.cnki.gdxbzrb.2024.06.10

摘要：为了解决制造企业内部加工机床合理排产问题，提出了一种基于设计结构矩阵（design structure matrix， DSM）的车间机床调度方法。构建了零件工艺与车间机床之间的关联矩阵调度模型；采用矩阵遍历算法，实现了加工机床根据待加工零件的工序信息自动合理分配机床；提出了最优机床排产方案评价指标、准则，采用多属性决策方法解决了最优机床排产方案的选择问题；通过开发的原型系统，实例验证了本文提出方法的可行性。

关键词：机床调度；设计结构矩阵；调度模型；机床排产方案

中图分类号：TP391

文献标志码：A

生产调度是现代制造企业的一项重要业务活动，它指在产品全生命周期内，为完成某个产品的加工，对生产资源（刀具、机床、夹具、生产人员等）进行合理分配，同时保证达到一定的预期目标，如生产成本低、生产时间少、加工能耗低。

合理的生产调度能提高企业的生产效率，减少加工资源的闲置浪费，从而提高企业的生产力、竞争力。而不合理的生产调度会延误生产周期，对企业的生产计划产生扰动，不利于企业的正常生产，无法保证产品的按时交货期。生产调度已成为影响制造企业快速响应市场能力的一项重要内容。

合理分配机床是生产调度过程中的重要环节。不同的机床在加工过程中的能耗差异性大。随着节能生产，绿色制造模式的提出，制造企业对机床的分配提出了更高的要求。机床的合理、快速分配问题已成为当前生产管理领域研究的热点。

目前调度方法分为两类：（1）人工分析法；（2）基于人工智能的方法。人工分析法调配资源耗时长、效率低，只适宜用于小作坊式的机床调度。当前人工智能方法主要有遗传算法（genetic algorithm，GA ）［1］、蚁群算法（ant colony algorithm，ACA）［2-3］、模拟退火算法（simulated annealing algorithm，SAA）［4］等。国内外学者们已经采用人工智能方法（GA、ACA、SAA等）来解决调度问题。刘琼等［5］提出了一种改进的GA，解决了柔性车间的调度问题。王晓圆等［6］提出了基于GA的齐停调度约束处理方法，解决了多工序间的加工时间齐停控制问题。GA解决调度问题的局限性表现为最优解的精度严重依赖迭代次数和种群规模大小，种群规模越大越接近最优解；而种群规模越大将导致计算量急剧增加，消耗的计算资源就越多。PAN等［7］采用蚁群优化算法解决流水线车间的加工资源调度问题。ACG虽然在解决车间调度优化问题时能准确得到可行解，但是在算法初期，信息素的积累需要耗费较多搜索时间。因此，采用蚁群优化算法获得最优解或者近似最优解需要花费较长时间。李俊等［8］采用改进的SAA解决柔性作业车间调度优化问题。SAA的优点是局部搜索能力强；缺点是由于缺乏对整个搜索空间的预知，搜索过程往往需要较长时间才能趋于稳定。

针对以上方法的不足，本文提出了一种基于DSM的机床调度方法。

1机床调度问题描述

车间机床调度问题一般可描述为在机床状态、规格、加工能力约束和工序与机床之间关联约束条件下，对于已知加工工艺规程的某个待加工零件，分解其工艺中不同工序的内容和加工顺序，合理调配加工机床，保证在完成零件加工基础上，达到加工时间最短或者加工成本最低或者能源消耗最低等目标。用数学集描述如下：

lt;Mcongt;：：=Msta| Mspe |Rpm

lt;Pgt;：：=P1|P2|…| Pm

lt;Mgt;：：=M1| M2|…| Mm

Mi=f（Pi），1≤i≤m

Ti=fti （Pi， Mi），1≤i≤m

lt;Tgt;：：=T1| T2|…| Tm

Ttotal=∪mi=1Ti

Ci=fci （Pi， Mi），1≤i≤m

lt;Cgt;：：=C1| C2|…| Cm

Ctotal=∪mi=1Ci

Ei = fei （Pi， Mi），1≤i≤m

lt;Egt;：：= E1| E2|…| Em

Etotal=∪mi=1Ei

［Min］Ttotal|Ctotal|Etotal "lt;Pgt;Mconlt;Mgt;

其中，Mcon表示机床选择的约束条件集;Msta表示机床状态约束;Mspe表示机床规格约束;Rpm表示工序与机床之间关联约束；P表示待加工零件的所有加工工序集合;Pm表示第m道工序，且m为工序总数；M表示完成待加工零件的加工所选全部机床集合；Mm表示第m道工序选用的机床；fi表示从Pi到Mi的映射函数；Ti表示工序Pi由机床Mi完成所花费的时间;fti表示从（Pi，Mi）到Ti的映射函数;T表示所有工序完成加工的时间集合;Ttotal完成全部加工工序的总完成时间；Ci表示工序Pi由机床Mi完成的生产成本;fci表示从（Pi，Mi）到Ci的映射函数;C表示完成全部工序的生产成本集合;Ctotal表示完成全部工序的总生产成本；Ei表示工序Pi由机床Mi加工完成的能耗；fei表示从 （Pi， Mi）到Ei的映射函数;E表示完成全部工序机床的能耗集;Etotal表示完成全部工序机床的总能耗；最后的式子表示为实现最小Min（Ttotal或Ctota或Etotal），根据工序集，在约束Mcon条件下排产，机床分配方案为P对应M。

绝大多数复杂零件由于工序之间存在差异性，导致所有加工操作不能由同一台机床来完成。这就要求调度员根据零件的加工工序信息，合理调配车间机床。对于简单零件，人工调度很容易解决排产问题。但对于工序繁多的复杂零件，人工分配机床方法时间长，且容易出错，造成机床分配调度不合理。因此，制造企业急需一种加工机床的自动调配方法及系统工具，实行机床的自动排产。本文要解决的问题描述如下：

（1）研究对象。制造企业内部车间的机床。

（2）给定条件。车间的所有机床状态；待加工零件的操作规程（包含零件的加工工序信息、具体的加工尺寸要求等）；加工工序名称与加工机床之间的关联映射关系。

（3）目标。开发一种调度方法，根据零件加工工序，自动合理分配机床，保证零件加工顺利完成，达到加工时间最短，或者能耗最低，或者成本最低，或者综合最优的效果。

2机床调度方法

受DSM［9-14］矩阵技术在设计、工程更改等领域的应用启发，本文提出了基于DSM矩阵的机床调度方法，具体调配流程如图1所示。

2.1调度模型构建

根据零件加工工序与机床之间关联关系，构建工序与机床的关联调度矩阵。不失一般性，设零件的加工工序共有m道（P1，P2，…，Pm），车间共有加工机床n台（M1，M2，…，Mn）。将各工序与机床之间的选择关系映射为矩阵，矩阵的行对应机床，列对应工序，构成一个m×n阶矩阵，称为基于DSM关联调度矩阵。调度矩阵中，矩阵的行数m表示总的工序数，列的数目n表示车间的机床总数。矩阵元素aij∈{0，1}，1≤i≤m，1≤j≤n。若aij=0则表示第i道工序不能由第j台机床加工完成;若aij=1则表示第i道工序能由第j台机床加工完成。图2显示了m×n阶的关联调度矩阵。

2.2矩阵赋值策略

由2.1节可知，调度矩阵元素取值反映了工序选择加工机床的状态。矩阵元素的取值策略，体现的是工序选择对应加工机床的条件，用数学集描述aij的取值策略，即aij=1的条件如下：

lt;Mconijgt;：：=Mstaj|Mspej|Rpmij

Val（Mstaj）∈{0，1}

Val （Rpmij）∈{0，1}

If Val（Mstaj）=1 ∪Proi∈ Scope（Mspej）∪Val（Rpmij）=1 then aij=1

其中，Mconij表示第i道工序选第j台机床加工完成的约束条件集合；Mstaj表示机床Mj当前状态，其值域为{0，1}。当Val （Mstaj）=0表示机床Mj当前状态不能选，机床处于机床检修、损坏或者正在加工其它零件状态；Mspej表示第j台机床的加工规格约束，主要指工作台大小对加工零件的约束；Rpmij表示第i道工序名称与第j台机床类型的关联约束;Val （Rpmij）表示第i道工序是否与机床Mj类型匹配，值“1”表示匹配，“0” 表示不匹配。例如，工序Pi的工序名称为钻孔，机床Mj类型为钻床，则称“钻孔”与“钻床”匹配，即Val （Rpmij）=1。具体工序名称与机床类型的关联关系如表1所示；最后一行表示机床同时满足三个条件（1、机床状态可选；2、工序加工尺寸在机床规格许可范围内；3、工序名称与机床类型匹配）时，调度矩阵元素（aij）取值为1，即第i道工序可由第j台机床加工完成。

2.3排产方案分配

分配加工任务时存在某道工序能由多台机床分别独立完成的情况。因此，依据工序分配机床时可能出现多个排产方案。如何快速从关联调度矩阵中找到可行的排产方案是本节要解决的主要问题。

对关联调度矩阵赋值后，依次从矩阵中每行选择一个值为1的元素，就能形成一个可行排产方案，图3显示了一个赋值后的4×4阶的关联调度矩阵。从图3所示的关联调度矩阵中依次每行取出一个元素，存入单向链表，可得4条单链表，对应机床排产方案有4个。采用矩阵遍历算法实现可行的机床排产方案分配（搜索）。

2.4排产方案评价指标

为了从2.3节多个机床分配方案中选择最优的方案指导实际生产，需要评价分配方案优劣的评价指标。本文采用三个指标：加工时间、加工成本、能耗，对分配方案进行评价。

（1）加工时间

加工时间指零件在所有工序阶段花费在各个机床上加工时间的总和。加工时间的计算公式如下：

Ttotal=∑mi=1Ti（1）

式中：Ttotal指零件完成全部（m道）工序在对应机床上花费的加工时间总和。Ti指工序Pi在其选择的机床上花费的加工时间。

（2）加工成本

加工成本指零件在所有工序阶段花费在各个机床上加工成本的总和。加工成本的计算公式如下：

Ctotal=∑mi=1Ci（2）

式中：Ctotal指零件完成全部（m道）工序在对应机床上花费的加工成本总和。Ci指工序Pi在其选择的机床上花费的加工成本。

（3）能耗

能耗指零件在所有工序阶段消耗在各个机床上的能源（本文主要指机床消耗的电能）总和。能耗的计算公式如下：

Etotal=∑mi=1Ei（3）

式中：Etotal指零件完成全部（m道）工序在对应机床上消耗的能源总和。Ei指工序Pi在其选择的机床上消耗的能源。

2.5排产方案优选

企业根据自身业务需求从多个机床排产方案中选择一种最优排产方案指导企业的实际生产，需要评价准则或标准。本文遵循制造企业的特点，提出了4条机床排产方案优选准则。

准则1：针对交货期比较紧的制造企业，优选加工时间花费最少的排产方案。

准则2：针对高度关注成本控制的制造企业，优选加工成本最低的排产方案。

准则3：针对供能（电能）紧张的制造企业，优选能耗最低的排产方案。

准则4：针对交货期有要求，同时考虑成本、能耗的制造企业，选用加工时间/加工成本/能耗综合最优的方案。

准则1实施起来比较容易，直接采用公式（1）计算每个排产方案的加工时间，最后将结果排序，取值最少的那个机床排产方案即推荐为最终优选的排产方案。准则2或准则3的实施类似于准测1，只是将公式（1）换成对应的公式（2）或（3）。而准则4，实施起来比较困难，这是因为加工时间的单位是分钟，加工成本的单位是元，能耗的单位是焦耳，隶属于不同的量纲。针对准则4中的不同因素（加工时间、加工成本、能耗），采用多属性决策方法［15］解决最优排产方案的选择问题。

3试验验证和方法评价

3.1试验验证

为了验证本文提出的基于DSM机床调度方法可行性，专门开发了一个原型系统“车间机床调配系统V1.0”。该原型系统以Microsoft Visual Studio 2018为开发平台，采用C++语言和Microsoft SQL Server 2020数据库进行开发。调配系统的核心功能模块有两个：（1）搜索可行的排产方案，即分配合理的机床排产方案；（2）优选出最佳的排产方案指导车间的实际生产。这两个核心功能模块分别采用了本文提出的基于DSM矩阵的可行机床排产方案分配（搜索）方法与机床排产方案优选方法。

试验设计：在郑州某小型机械制造企业，采用本文开发的原型系统对该企业生产的零件“轴”进行合理排产试验。轴的零件加工图如图4所示，轴的加工工艺规划如表2所示，原型系统工作界面如图5所示。导入企业机床信息模块中机床状态‘1’表示机床正常，处于空闲状态，可以被选择；‘0’表示机床处于维修保养中，或已损坏，或者有其它加工任务正被使用，该机床不能被选择。当导入企业机床信息和待加工零件的工序信息，通过系统分配可行的机床排产方案，选用综合最优的机床排产标准，就得到一条最优的机床排产方案（方案3），从而指导实际生产。该机床排产方案3与采用人工分析法得到的分配方案一致，从而验证了本文方法的正确、可行性。

3.2方法评价

为了客观评价本文方法的优劣性，在同等条件下，分别采用本文方法、基于GA的调配方法、人工分析法进行对比试验。以解决机床分配所花费的时间为评价指标，时间花费少的方法优。

表3分别列出了采用本文方法、基于GA的调配方法、人工分析法解决机床分配问题的平均时间。根据表3的试验结果，在同等条件下，以解决机床分配所花费时间为评价指标，本文方法要优于其它两种方法。

4结论

本文提出了一种基于DSM矩阵的机床调度方法。该方法根据待加工零件的加工工序信息与企业内部机床之间的关系，构建调度分配矩阵，给定矩阵元素赋值策略、调配方案优选指标和准则。通过实例验证了该方法正确、可行。以调配机床花费的时间为评价指标，本文的方法优于人工分析方法和基于GA的调配方法。

本文的研究成果可应用于车间机床调配系统，缩短调度人员合理分配机床进行加工准备的时间，从而提高企业的生产效率。本文方法的局限性是由于采用调度矩阵，矩阵的阶数太大，则会增加算法的时间复杂度。因此，该方法只适宜用于中小型企业（企业机床总数不超过20台，单个零件工序总数不超过20道）。后续我们将在矩阵聚类研究基础上改进本文的方法，增加本文方法的普适性，以适应大型企业多机床、多工序环境下的机床调配。

参考文献：

[1]

MORADI M H， ABEDINI M. A combination of genetic algorithm and particle swarm optimization for optimal DG location and sizing in distribution systems［J］. International Journal of Electrical Power amp; Energy Systems， 2012， 34（1）： 66-74.

［2］ REED M， YIANNAKOU A， EVERING R. An ant colony algorithm for the multi-compartment vehicle routing problem［J］. Applied Soft Computing， 2014， 15： 169-176.

［3］ KEFAYAT M， ARA A L， NIAKI S A N. A hybrid of ant colony optimization and artificial bee colony algorithm for probabilistic optimal placement and sizing of distributed energy resources［J］. Energy Conversion and Management， 2015， 92： 149-161.

［4］ JOSE T J， IDELFONSO I M， ALBERTO G R， et al. A dual representation simulated annealing algorithm for the bandwidth minimization problem on graphs［J］. Information Sciences， 2015， 303： 33-49.

［5］ 刘琼， 张超勇， 饶运清， 等. 改进遗传算法解决柔性作业车间调度问题［J］. 工业工程与管理， 2009， 14（2）： 59-66.

［6］ 王晓圆， 王爱民， 范瑞成， 等. 基于遗传算法的配作齐停类调度约束处理技术［J］. 计算机集成制造系统， 2014， 20（11）： 2788-2797.

［7］ PAN Q K， TASGETIREN M F， SUGANTHAN P N， et al. A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem［J］. Information sciences， 2011， 181（12）： 2455-2468.

［8］ 李俊， 刘志雄， 张煜， 等. 柔性作业车间调度优化的改进模拟退火算法［J］. 武汉科技大学学报， 2015， 38（2）： 111-116.

［9］ CLARKSON P J， SIMONS C， ECKERT C. Predicting change propagation in complex design［J］. Journal of Mechanical Design， 2004， 126（5）： 788-797.

［10］唐敦兵， 徐荣华， 唐吉成， 等. 基于设计结构矩阵的工程变更影响分析［J］. 机械工程学报， 2010， 46（1）： 154-161.

［11］李中凯， 殷文卫. 基于3D CAD模型的设计结构矩阵自动化生成系统［J］. 计算机工程与科学， 2020， 42（3）：483-492.

［12］KONSTANTINIDIS E I， KATSAVOUNIS S， BOTSARRIS P N . Design structure matrix （DSM） method application to issue of modeling and analyzing the fault tree of a wind energy asset［J］. Wind Energy， 2020， 23（3）：731-748.

［13］JIANG Y， YIN B， JIA D. Research for aircraft design process optimization based on design structure matrix［J］. Journal of Physics Conference Series， 2021，16（1）：1732-1742.

［14］陈思. 基于分层设计结构矩阵的航空产品工装模块划分［J］. 机床与液压， 2021， 49（4）：73-77.

［15］李美娟， 潘瑜昕， 徐林明，等. 改进区间数动态TOPSIS评价方法［J］. 系统科学与数学， 2021， 41（7）：1891-1904.

（责任编辑：于慧梅）

Abstract：

To reasonably solve the machine scheduling problem in manufacturing enterprises， this paper presented a workshop machine scheduling method based on the design structure matrix （DSM）. The DSM scheduling model was constructed. The matrix traversal algorithm was utilized to realize machines automatic allocation based on the process information of a part that would be produced. The evaluation indexes and standards of optimal machine scheduling plan were put forward， and the technique for order preference by similarity to ldeal solution method was used to solve the problem of choosing the most optimal machine scheduling plan. The feasibility of the method was verified by a real case using the developed prototype.

Key words：

machine scheduling; design structure matrix; scheduling model; machine production scheduling plan

收稿日期：2023-10-23

基金项目：河南省高等学校重点科研资助项目（23A460013）；河南省软科学研究资助项目（232400410364）；河南省科技攻关资助项目（242102220082）；郑州航空工业管理学院学科基础创新能力提升资助项目（XKZX24057）

作者简介：陈进平（1979—），男，副教授，博士，研究方向：产品数字化设计、车间数字化生产管理研究， E-mail：380853214@qq.com.

*通讯作者：陈进平，E-mail：380853214@qq.com.