【www.zhangdahai.com--学生作文作业】
钟宏扬 彭乘风 廖 勇 李 翔
（①广东工业大学广东省计算机集成制造重点实验室，广东 广州 510006；
②湘南学院物理与电子电气工程学院，湖南 郴州 423000）
在新冠疫情肆虐，人力成本逐渐攀升的制造业大背景下，传统车间的智能化改造需求日益迫切。传统车间通常制定独立的任务作业计划与物料搬运计划，再由管理者经验式协调，这种割裂式的生产计划制定手段将难以适用智能车间[1]。物料储运系统是智能车间生产闭环的关键环节，自动导航小车(automated guided vehicle,AGV)作为重要承运设备已经成为物料有序流转的重要保障，作业车间符合定制化企业多品种小批量的生产特点，但相关调度研究却鲜有将物料运输过程控制纳入考量[2]，故如何制定AGV 搬运计划以快捷响应作业车间机床生产需求的联合调度优化问题应运而生。
作业车间AGV 联合调度可以解耦成作业车间机器调度与AGV 调度两个关联耦合的子问题，由于两个子问题均已被证实为NP-hard[3-4]，所以作业车间AGV 联合调度也属于NP-Hard 问题。表1 为作业车间环境下AGV 联合调度文献分类汇总，早期研究通过构建混合整数规划模型以精确法求解，例如Sigrid Knust[5]等基于上/下界约束松弛的算法求解联合调度问题，尽管全局优化算法可以获取最优解，但全局优化局限于小规模场景问题求解，在现实场景中难以推广。在中等规模以上的问题求解上，元启发式算法提供了有效的途径，如混合粒子群搜索算法[6]、遗传算法[7]等，但随着问题规模逐渐变大，问题求解空间也指数型剧增，算法陷入早熟与局部最优的概率随之增加，有效邻域搜索产生的时间代价与解的优度控制相互掣肘，故此类算法性能相对依赖参数设置。启发式规则因其高效快速、符合经验直觉的特点被广泛应用于在线调度领域[8-10]。陈敏[9]等以单环布局多AGV 调度问题为背景，比较分析了7 种调度规则的性能差异；
郭沛佩[10]等在离散事件系统建模仿真技术下，分析了不同任务到达模式下AGV 调度规则与工件路由规则的组合性能。作为在线调度的常用策略，启发式规则被认为存在工况适应的局限性，根据No free lunch 定律[11]单个规则无法在所有指标上都完全胜过其他规则。因此，亟待提出一套组合规则设计框架，通过融合差异化规则的特征以期增强启发式规则的场景适应性。
表1 作业车间环境下AGV 联合调度文献
本文对研究问题进行结构化分析后，构建数学模型并设计一套组合规则算法框架，通过导入分属不同子决策的规则以生成大量组合规则算法。鉴于组合规则的耦合性能受到任务和资源等多方面因素的影响，设计差异化的算例实验，以评估不同组合规则受实验参量敏感程度，进而验证算法的有效性与稳定性。
如图1 所示，作业车间AGV 联合调度问题可以描述为：已知待加工工件集合J={J1,J2,···,Jn}，任意工件的工艺路径已知且唯一，工艺路径有nj道工序，每道工序有且仅有一台设备可以加工，作业车间中的加工设备资源集记为M={M1,M2,···,Mm}。物料储运系统由车间铺设的轨道与r台AGV 组成，AGV 往返于原料池、车间、成品仓之间执行物料转运操作，搬运集合记为R={R1,R2,···,Rr}。为使研究更为聚焦，现对问题所涉及的其他因素做抽象化假设：
图1 运输能力有限的作业车间运行示意图
（1）所有待加工工件在零时刻都可加工，且工艺路径、加工工时等信息已知。
（2）所有加工/搬运设备在零时刻都处在空闲状态，且设备在生产过程中一直可用，不考虑各类机器故障。
（3）加工工件的工艺路径信息固定，同一个工件工序间的紧前紧后关系不得违背。
（4）同一台加工设备在同一时刻只可以加工一个工件，且工序一旦开始加工就不可中断。
（5）同一台搬运设备在同一时刻只能搬运一个工件，且搬运过程不可中断。
（6）AGV 搬运耗时仅与生产节点之间的距离、AGV 运输速度相关，不考虑工件在设备上的装卸时间。
（7）AGV 在各节点之间搬运路线的选择上遵循最短路径原则，各AGV 执行搬运任务过程中互不干扰。
参数设置
j,l待加工工件编号
m加工设备编号
M0原料池
s,k搬运设备编号
h,q加工工序编号
H一个极大的数
pjh:工序h的加工工时
J: 待加工工件集合，J={J1,J2,···,Jn}
M: 加工设备集合，M={M1,M2,···,Mm}
R: AGV 集合，R={R1,R2,···,Rr}；
Oj: 任意工件j的工序集合，Oj={Oj1,Oj2,···,Ojk}
Tjh: 工件j任意工序Ojh完工转移到紧后工序Oj(h+1)的搬运任务
bjh: 工序Ojh的加工开始时间
fjh: 工序Ojh的加工完成时间
βjh,s搬运任务Tjh由AGV 设备s执行则为1，否则为0
δjh,lq搬运任务Tjh优先比搬运任务Tlq执行则为1，否则为0
γjh,lq搬运任务Tjh与搬运任务Tlq均由同一台AGV 执行则为1，否则为0
本文所考虑的优化目标为最小化最大完成时间，记为Cmax。
模型的相关约束条件如上所示，式（2）定义了最大完成时间为所有工件都完工时最后一道搬运工序的完工时间；
式（3）和（4）表示工件在执行加工过程中不可中断；
式（5）表示工件加工工序的开工时间需要考虑前一道工序的转运时间；
式（6）和（7）表示一道工序的运输操作需等待其加工操作完成；
式（8）表示加工设备执行任务的唯一性；
式（9）为一台设备同一时刻只能加工一个工件；
式（10）表示一个工件同一时刻只能由一台设备加工；
式（11）表示搬运任务只能由一台AGV 执行；
式（12）～（16）表示搬运任务的唯一性：一台AGV 同一时刻只能搬运一个工件，一个搬运任务仅可由一台AGV 服务。式（17）表示忽略空载/装载运输的时间偏差。
作业车间AGV 联合调度问题可以解耦成AGV选择与加工工序排序两个强关联的子决策，如图2所示对两个子问题进行问题特征提取与分析，构建适应问题特征的规则库，通过决策耦合将两类规则算法进行规则重组，最终生成求解联合调度问题的组合规则集合。
图2 联合调度组合规则算法框架
2.1 规则算法设计
启发式规则是将任务、资源的某种特征属性作为准则对工件加工优先级顺序、AGV 选择优先级顺序进行设定以快速生成一个合适的解决方案。先设计不同的工序排序规则（加工设备前队列的优先级设定）、AGV 选择规则（待转运的工件选择AGV 的优先级），再将规则嵌入图2 所示的算法框架生成组合规则算法。通过相关文献调研[9-10,14]，本文对经典AGV 选择与工序排序规则在联合调度问题下作出适应性改进，最终拟采用的规则集合如表2 所示。
表2 启发式规则汇总分类
2.2 组合规则算法生成
通过对问题特征分析后，将表2 所设计的3 种AGV 选择规则与4 种工序排序规则导入图2 所构建的组合规则算法生成框架，共生成12 个组合调度规则。12 个组合调度算法执行流程的伪代码如下所示。
基于组合规则的作业车间AGV 联合调度算法
1：输入：工件集合JobSet，总工序集合T_OperSet，已完工工序集合F_OperSet，AGV 数量Num_AGV
2：初始化AGV 执行任务信息矩阵MA、加工设备释放时间矩阵MR、待加工工件状态矩阵MJ
3：for i=1 : length(T_OperSet)
4：检索JobSet 中未完工的工件集合UF_JSet；
5：for j=1 : length(UF_JSet)
6：锁定待转运工件的位置Trans_P；
7：for k=1 : Num_AGV
8：锁定第k 台AGV 的所在位置节点AGV_P，统计AGV 空载与满载运输时间
9：end for
10：按照组合规则的AGV 选择规则选择执行搬运任务的AGV
11：确定加工工件搬运的目标节点，计算工序的最早开工与最晚完工时间
12：end for
13：按照组合规则的工序排序规则确定已转运任务的加工优先级，更新MA、MR、MJ
14：end for
3.1 仿真算例设计
为进一步探索前文所生成算法的有效性与场景适应性，设计生产特征差异化的算例对组合规则算法进行对比分析。参考Ümit Bilge,[15]等人的研究，在已知车间布局、轨道导向与加工工件信息等条件下进行小规模问题的案例设计，下图3 所示为小规模测试场景所涉及的4 种车间布局图(编号分别记为a/b/c/d)，包含了4 台加工设备与一个中转仓。中、大规模测试场景的车间布局参考Ham A[16]，其包含的加工设备节点数量分别为11、16 个，因中、大规模问题车间布局(编号记为e/f)同质化程度比较高且过于复杂，此处不予展示。作业车间AGV 小车的数量为2 台，在轨道定向的前提下匀速行驶。
图3 小规模测试案例的车间布局图
本文拟采用美国Gurobi Optimization 开发的新一代优化求解器Gurobi 和组合规则算法进行求解。将组合规则算法解与Gurobi 解对比以衡量规则解与最优解的优度差。考虑到实际生产对运算时效性的需求，设定Gurobi 的求解时间上限为1 800 s。
本文所开发的作业车间调度仿真模型、组合规则算法与Gurobi 求解环境均采用Matlab R2019b 编程实现，其运行环境如下：计算机系统为Windows10，处理器为Intel® Core™ i5-10200H @ 2.40GHz，RAM内存为16.0GB。
3.2 实验研究内容
通过对AGV 联合调度问题的文献调研总结，了解到对规则算法性能产生影响的实验因素有车间布局(g)，任务规模(s)，工序排序规则(o)，AGV选择策略(h)，AGV 行驶速度(v)。如表3 所示为本实验所涉及影响因子的汇总：车间布局按照节点数量、轨道导向路径区分共有6 种规模；
任务规模分为5/6/20 三个数量级；
工序排序规则与AGV 选择规则按照2.1 小节所设计的维度分别有4 种工序排序与3 种AGV 选择规则；
最后小车行驶速度作为搬运设备的关键参量设置了1 m/s 与2 m/s 两种水平。本文共设计了50 个算例，按照加工设备/任务数量可以划分为40 个小规模场景测试案例与10 个中大规模场景测试案例。本文的实验路线按照以下3 个步骤推进：
表3 实验影响因素汇总
（1）精确法求解最优解：借助所构建的混合整数规划模型进行精确法求解，即在有限时间范围内，通过Gurobi 求解小规模问题的最优解，以此作为衡量组合规则算法有效性的标杆。
（2）组合规则算法有效性验证：将不同AGV选择与工序排序规则耦合作用于联合调度决策以生成组合规则，将组合规则嵌入仿真模型运行出规则解的Cmax值，比较不同组合规则与最优解标杆之间在优化目标上的性能差异。
（3）组合规则算法适应性分析：评估12 种组合规则在中、大规模场景算例的性能，评价指标包括优化目标Cmax，AGV 平均利用率、AGV 平均空载距离和总运输距离等4 个指标。
3.3 结果分析
3.3.1 精确法求解结果与分析
由于精确法仅能求解小规模问题，故采用加工节点数量为4 台设备的40 组算例进行Gurobi 求解。分别统计每组案例的优化目标Cmax值和CPU 运算时间tcpu，表4 与表5 依次为AGV 行驶速度1m/s 与2m/s 下Gurobi 的运算结果。
表4 为AGV 行驶速度为1 m/s 时，Gurobi 的精确解结果。同一个车间布局方案下，不同算例之间的Cmax值之间存在一定的差异，差异的根源来自于算例之间在任务规模与任务的工艺路径差异；
再比较相同任务信息下，不同布局方案下各算例最优解在Cmax和求解时间上的差异，可以发现不同布局方案对最终结果存在一定影响，差异不仅体现在解的质量上，在运算耗时上更为突出。因为设定了求解时间上限的缘故，所以在某些算例下Gurobi 只能求解出近似解。
表4 小规模问题Gurobi 精确解结果(v=1 m/s)
表5 是设置AGV 行驶速度为2 m/s 的Gurobi 运算结果，跟AGV 低速运行结果的差异主要体现在Cmax值在各个算例下都有不同程度的提升，因为运输能力的提升使得各待加工工件的流转周期得到一定程度的缩短，进而减少了Cmax值；
另外一方面，各算例在Gurobi 的运算时间消耗不同程度地降低，且给定时间内无法求解到最优解（tcpu=1 800 s）的算例相对有所减少。
表5 小规模问题Gurobi 精确解结果(v=2 m/s)
3.3.2 组合规则算法有效性验证
为评价组合算法的有效性，将12 种组合规则解与Gurobi 最优解在40 个小规模问题算例下进行比较，并通过设置不同AGV 行驶速度以验证组合规则解与最优解之间的差异，有效性实验结果如图4 与图5 所示。
图4 各算法优化目标比较(v=1 m/s)
图5 各算法优化目标比较(v=2 m/s)
如图4 所示，AGV 行驶速度为1m/s 时，不同组合规则相比Gurobi 在求解质量上存在不同程度的差异。从布局方案的角度进行观察：在布局方案a、b下，性能最优的组合规则各在4 个算例下优于Gurobi 求出的近优解，因为在这4 个算例下Gurobi都没能在给定的时间内求解出最优解；
布局方案c、d 下，表现最优的组合规则也各在6 个算例下性能发挥胜于Gurobi 求出的近优解。另外，观察组合规则解与最优解的差距，最大的偏离程度（布局方案c 的算例#5）也仅为34%，考虑到单个组合规则运算时间消耗控制在毫秒级，虽然组合规则最优方案要在所有组合规则都运算完才能选出，但如表6所示，所有组合规则总耗时也不超过0.1 s。相比Gurobi 高耗时下的有限性能提升，组合规则算法的求解质量是完全可以接受的。
表6 小规模问题下组合规则算法运算时间
图5 为AGV 行驶速度为2 m/s 时优化算法与组合规则算法的优化目标差异。通过观察分析可以总结出，相比AGV 行驶速度设定为1m/s 时，AGV 以较高速度行驶的场景下组合规则算法仅能在少数算例上贴近或者胜过Gurobi 的解质量：布局方案为a、c、d 时，组合规则仅在一个算例下胜过Gurobi；
布局方案为b 时，有两个算例等于或者胜过Gurobi，其中布局方案b 在算例#6 下组合规则(JAT+EFR)也达到了Gurobi 求解的最优解。
综上所述，AGV 在行驶速度设置较低时，组合规则算法能以极短的运算时间得到性能接近Gurobi的近优解。AGV 行驶速度设置变高，Gurobi 更容易求得最优解，但组合规则算法性能发挥依旧可观。
3.3.3 组合规则算法适应性分析
经过预实验测试，在给定时间内Gurobi 求解器无法求得中、大规模问题（布局方案e/f）的可行解，故此节将进一步评估规则算法在中、大规模问题算例上的适应性发挥。算例#1-#5 为中等规模算例（加工设备11 台，20 个待加工任务），算例#6-#10 为大规模算例（加工设备16 台，20 个待加工任务）。
表7 为中大规模下组合规则算法的运算时间，跟前文小规模运算时间统计方法类似，运算时间为所有组合规则在某一个案例下运行的总耗时，通过观察对比发现，中大规模下组合规则的运算时间相比小规模问题有明显增加，但最长运行耗时的算例仍未超出1 s。在调度方案的性能评价指标方面，除去优化目标Cmax值以外，还引入AGV 平均利用率、平均空载距离和总运输距离3 个观察指标来辅助分析组合规则的内在特性。
表7 中大规模问题下组合规则算法运算时间
图6 为AGV 行驶速度1 m/s 下，各组合规则算法在中、大规模算例下的表现性能。先从优化目标Cmax值分析，图6a 中基于不同工件排序规则的组合规则算法出现多级分化的趋势，JAT 和JEO类组合规则性能表现要完全胜过MER、JFO 类规则。通过分析AGV 利用率以解析优化目标的差异，不难发现JFO 类规则的AGV 平均利用率最为低下，说明AGV 小车在JFO 类规则下频繁的无效移动造成了较长的空载距离，图6c、6d 的观察指标进一步印证了这一结论。
图6 组合规则算法大规模算例适应性实验结果（v=1 m/s）
图7 为AGV 行驶速度设定为2 m/s 时，各规则算法的性能比较。通过比较图6a 与图7a 可以发现所有规则算法在Cmax指标上都有不同程度的性能提升，JAT、JEO 类规则相比MER、JFO 类规则在Cmax值上的差距有略微缩小。在AGV 平均利用率指标上，由于搬运效率的提升，造成了AGV 小车的有效运输时间减少，故AGV 利用率有所下降，且AGV 小车的平均空载距离也有所上升。最后，不同行驶速度设置下，各组合规则在AGV 总运输距离指标上没有显著变化趋势。
图7 组合规则算法大规模算例适应性实验结果(v=2 m/s)
综上所述，工序排序规则在Cmax值上对组合规则的影响较为显著，且JAT、JEO 类规则在AGV较低速度行驶时相比其他工序排序规则有明显优势。
本文以具有AGV 储运系统的作业车间联合调度为研究对象，首先以最小化最大完成时间为优化目标构建了联合调度的混合整数规划模型，然后分别从基于Gurobi 求解器的精确法与基于组合规则的近似算法两套思路对问题求解，最后，设计了具有不同布局方案、任务规模等生产特征的算例对所涉及的组合规则生成算法框架进行有效性验证，实验结果表明：
（1）小规模问题算例下，Gurobi 精确解普遍优于组合规则算法解，但在AGV 速度较低时，组合规则算法与Gurobi 的解差异缩小。
（2）从算法的求解时间来看，Gurobi 算法无法在可观时间内求解大规模问题精确解，甚至在小规模问题上也要耗费很多运算时间，相比之下组合规则算法秒级的运算时间具有很大优势。
（3）组合规则算法在不同布局方案下的Cmax值差异相对明显，工序排序规则的选择很大程度影响组合规则的性能表现。
未来研究可以考虑更多实际生产的动态因素，例如工时不确定、AGV 故障等。引入交货期类目标做进一步场景拓展也是一个潜在方向。
猜你喜欢 算例工件工序 带服务器的具有固定序列的平行专用机排序杭州电子科技大学学报(自然科学版)(2022年4期)2022-08-23120t转炉降低工序能耗生产实践昆钢科技(2022年2期)2022-07-08带冲突约束两台平行专用机排序的一个改进算法杭州电子科技大学学报(自然科学版)(2022年3期)2022-06-08工业机器人视觉引导抓取工件的研究智能制造(2021年4期)2021-11-04两台等级平行机上部分处理时间已知的半在线调度∗计算机与数字工程(2021年7期)2021-08-08基于B/S 架构的钻井全工序定额管理系统设计与应用中国管理信息化(2021年11期)2021-07-30浅谈SDS脱硫技术在炼焦工序中的运用昆钢科技(2021年1期)2021-04-13提高小学低年级数学计算能力的方法速读·中旬(2018年4期)2018-04-28电缆行业成本核算中原材料损耗算法分析科技视界(2016年24期)2016-10-11论怎样提高低年级学生的计算能力读写算·教研版(2016年10期)2016-06-08本文来源：http://www.zhangdahai.com/gerenwendang/xueshengzuowenzuoye/2023/0604/607111.html
