一种基于改进遗传算法的设备排产和场内物流调度优化方法.pdf

(19)国家知识产权局(12)发明专利申请(10)申请公布号CN114971317A(43)申请公布日2022.08.30(21)申请号202210611119.7(22)申请日2022.05.31(71)申请人浙江大学地址310058浙江省杭州市西湖区余杭塘路866号(72)发明人宋执环李丹宁杨春节何川(74)专利代理机构杭州求是专利事务所有限公司33200专利代理师刘静(51)Int.Cl.G06Q10/06(2012.01)G06Q50/04(2012.01)G06N3/12(2006.01)权利要求书3页说明书11页附图2页(54)发明名称一种基于改进遗传算法的设备排产和场内物流调度优化方法(57)摘要本发明公开了一种基于改进遗传算法的设备排产和场内物流调度优化方法，属于制造过程生产调度和优化领域。本发明基于离散制造系统的混合整数规划模型，使用改进遗传算法分别对设备排产和物流调度进行优化，在排产优化部分插入时间片预留出运输时间，获得最优设备排产方案，在此基础上求解最优物流调度方案。本发明比现有排产调度优化方法具有更快的计算速度和更好的优化效果，有利于提高制造企业的运行效率、增强企业竞争力。CN114971317ACN114971317A权利要求书1/3页1.一种基于改进遗传算法的设备排产和场内物流调度优化方法，其特征在于，包括以下步骤：步骤(1)：获取订单信息、设备信息和AGV状态；订单信息包括订单编号、订单内产品的种类和数量、订单产品的工序种类和总数、每个工序可以使用的设备和在不同设备上的加工时间、不同状态的物料所需的装卸时间；根据订单划分产品批次，同一批次内的产品种类相同，以批次作为排产调度的基本单位；在获得所有批次产品的工艺路线后，确定工序和对应的运输任务并编号；设备信息包括设备种类、数量和位置坐标，并给每台设备唯一编号；AGV状态包括正常工作的AGV编号，以及根据AGV当前性能计算出的在不同设备之间的行驶时间；步骤(2)：根据需求设定优化目标，选择对应的遗传算法种群适应度函数；步骤(3)：设置种群大小、最大迭代次数和收敛阈值，初始化一个种群用于求解最优的设备排产方案；使用MSOS编码方法，每个个体由一条设备选择串和一条工序顺序串组成；使用遗传算法对种群进行迭代优化，具体操作包括解码计算适应度、选择操作、交叉操作和变异操作；特别地，在将染色体组解码为排产方案、递推各工序的起止时间时，同一产品的相邻工序之间需要插入时间片，长度为预估的运输时间；当停止迭代的条件满足，输出适应度最高的个体对应的染色体组；步骤(4)：设置种群大小、最大迭代次数和收敛阈值，重新初始化一个种群用于求解当前最优排产方案下最优的AGV调度方案；每个个体由四条染色体子串组成，包括设备选择串、工序顺序串、AGV选择串和运输顺序串，其中设备选择串和工序顺序串为步骤(3)输出的最优个体染色体组，AGV选择串和运输顺序串按照MSOS编码规则随机生成；使用遗传算法对种群进行迭代优化，但迭代过程中只对AGV选择串和运输顺序串执行交叉和变异操作；重复迭代直至停止条件满足，输出适应度最高的个体对应的排产调度方案。2.根据权利要求1所述的方法，其特征在于，步骤(2)所述优化目标为最小化整个排产调度方案的执行时间，即最小化所有产品完成加工并运输到仓库的时间第一项为产品n完成最后一道加工工序的时刻；Onp为工序标号，代表产品n的第p个工序，产品n的工序总数为Pn；第二项为产品n装载上AGV所用时间；为0‑1变量，当工序在编号为j的设备上加工则为1，否则为0，TDj0是AGV从设备j行驶到仓库所用时间，从而公式第三项代表AGV从加工工序的设备处行驶到仓库所用时间；第四项是卸货时间；优化目标是使Tmax最小，取作为适应度函数，C＞0为常数，将优化目标转换为最大化f。3.根据权利要求1所述的方法，其特征在于，步骤(3)所述过程可具体表示如下：步骤(3.1)设置种群大小、最大迭代次数和收敛阈值，初始化一个种群用于求解最优的设备排产方案，使用MSOS编码方法，每个个体由一条设备选择串和一条工序顺序串组成；步骤(3.2)将种群中的染色体解码为具体的排产方案，计算每个个体的适应度；在将染色体组解码为排产方案、递推各工序的起止时间时，同一产品的相邻工序之间需要插入时间片，长度为预估在两工序执行设备之间运输所用时间；步骤(3.3)根据精英保留策略，保留种群中适应度最高的个体；再对当前种群应用二元2CN114971317A权利要求书2/3页锦标赛选择算子，选出适应度更高的个体加入新一代种群；步骤(3.4)按照设定的概率，随机对种群中的染色体进行交叉和变异操作，得到新的种群；步骤(3.5)当种群迭代进化的总次数达到最大迭代次数，或者收敛性参数达到收敛阈值，结束迭代并输出适应度最高的个体；否