基于改进粒子群算法的柔性制造系统无死锁优化调度  

Deadlock-free scheduling based on improved particle swarm algorithm for flexible manufacturing systems

作　　者：刘慧霞 张铭心 LIU Huixia;ZHANG Mingxin(School of Electrical Engineering,Nantong University,Nantong 226019,China)

机构地区：[1]南通大学电气工程学院,江苏南通226019

出　　处：《南通大学学报（自然科学版）》2024年第1期38-48,共11页Journal of Nantong University(Natural Science Edition)　

基　　金：山东省自然科学基金面上项目(ZR2018MF024);江苏省“双创博士”项目(JSSCBS20211103);南通市基础科学研究项目(JC2021203);烟台市科技创新发展计划(2022XDRH005)。

摘　　要：柔性制造系统的优化调度问题是一个复杂的组合优化和NP-hard问题。以赋时Petri网为模型、最小化最大完工时间为优化目标,利用改进粒子群算法对一类柔性制造类系统建立了一种新的无死锁优化调度方法。该方法首先采用2层编码方式对路径和工序进行编码,建立工序与粒子位置之间的一一映射关系;其次,基于实时在线的死锁避免策略对粒子进行死锁检测与修复,保证所搜索的粒子均能解码为无死锁的可行调度序列;然后,设计了2种改进策略:粒子工序定向调整策略和局部搜索策略,以提高算法的寻优效率和局部搜索能力,保证快速得到最优或次优的可行序列;最后,利用2个仿真实验验证所提算法的有效性。实验结果表明:与其他已有算法相比,改进粒子群算法在求解柔性制造系统无死锁优化调度问题上具有较好的寻优能力。The optimization scheduling problem of flexible manufacturing systems is a complex combinatorial optimization and NP-hard issue.Using timed Petri nets as the model and aiming to minimize the maximum completion time,a novel deadlock-free optimization scheduling method for a class of flexible manufacturing systems has been established through an improved particle swarm optimization algorithm.This method first adopts a two-layer coding strategy for paths and processes,establishing a one-to-one mapping relationship between processes and particle positions.Secondly,it employs a real-time online deadlock avoidance strategy to check and repair the feasibility of particles,ensuring that the searched particles can be decoded into a deadlock-free feasible scheduling sequence.Then,two improvement strategies are designed:a particle process directional adjustment strategy and a local search strategy,to enhance the algorithm′s optimization efficiency and local search capability,ensuring the rapid acquisition of optimal or sub-optimal feasible sequences.Finally,the effectiveness of the proposed algorithm is verified through two simulation experiments.Experimental results demonstrate that,compared to other existing algorithms,the improved particle swarm optimization algorithm exhibits superior optimization capability in solving the deadlock-free optimization scheduling problem of FMSs.

关 键 词：柔性制造系统 死锁避免策略 粒子群算法 定向调整 局部搜索 

分 类 号：TP301[自动化与计算机技术—计算机系统结构]