一种基于多级邻域搜索混合遗传算法的单件流柔性混线排产方法与流程
本发明属于生产调度、智能制造与制造执行控制,涉及一种基于多级邻域搜索混合遗传算法的单件流柔性混线排产方法。
背景技术:
1、车间计划排产是制造企业生产组织的基础工作。对于电子产品装配生产线,通常需要依据工单数量、产品工艺路线、工位类型、物理工位数量、工位日历以及交期与优先级等信息,对装配、焊接、点胶、图像采集、检验等工序进行资源配置和时间安排。随着产品订单向多品种、小批量、短交期方向发展,产线也由原本的单件流水式装配,逐步调整为工位组合和工艺路线可动态重构的柔性可重构生产线。该类产线中,同一工位类型往往配置多个可并行使用的物理工位,不同工单同时竞争这些物理资源的使用数量和顺序,排程问题呈现较强的组合优化特征。
2、现有技术中,针对上述排程问题主要采用遗传算法、粒子群算法等智能优化算法对计划排程方案进行寻优,以获得最大完工时间最小、设备利用率最大等单目标或多目标最优的排程方案。其中,柔性作业车间调度算法主要围绕传统的“工件-工序-设备”关系建立模型,其基本决策是确定各工件各工序的加工先后顺序,以及从若干候选设备中为每道工序选择一台加工设备;针对变批量场景,现有方案进一步引入批量拆分或分批调度机制,将工单数量预先拆分为若干批次或子批,分别绑定至各加工设备后再进行排程优化。
3、然而,上述现有技术与柔性可重构产线的实际生产组织方式存在明显差异。一方面,在实际产线中,同一工单的一道工序并非固定选择一台设备,而是可能根据订单数量、设备负荷及全线资源状态,临时从多个同类型物理工位中选择若干工位组成作业资源集合,共同完成该工单在该工序上的全部产品;调度决策不仅包括工序顺序和设备选择,还需要同时确定并行投入的物理工位数量以及具体成员物理工位组合,现有“工件-工序-设备”模型难以直接表达此类多工位动态组合的资源形态。另一方面,实际产线的产品按照单件或单个料箱在工序之间流转,任一单件完成当前工序后即可立即进入下一道工序,而当前工单在前一道工序上的其他产品仍可继续加工,相邻工序之间存在明显的单件流重叠关系;若采用固定批次或固定子批方式将产品数量预先拆分并分别绑定至各加工设备,则无法描述现场按单件实际完成情况动态派工的机制,且以批次整体完工时间作为后续工序的启动条件将产生不必要的等待。
4、因此,现有面向批次或批量流转的通用排程方法难以直接适用于工位可重构、工艺动态调整、单件流水生产的柔性可重构产线的排产需求,需要一种能够同时满足动态并行工位配置、成员物理工位选择、工单工序优先排序、单件即时转序以及现场动态派工等要求的排产方法。
技术实现思路
1、本发明要解决的技术问题是:现有面向批次或批量流转的通用排程方法难以适用于工位可重构、工艺动态调整、单件流水生产的柔性可重构产线,无法同时满足动态并行工位配置、成员物理工位选择、工单工序优先排序、单件即时转序以及现场动态派工的排产要求。
2、为解决上述技术问题,本发明采用如下技术方案。
3、第一方面,本发明提供一种基于多级邻域搜索混合遗传算法的单件流柔性混线排产方法,包括:
4、获取车间调度数据,所述车间调度数据至少包括待排产工单、各工单的生产数量、释放时间、优先级和工艺路线,各基础工序对应的工位类型、在各物理工位上的单件加工用时、可用物理工位集合和最大允许并行工位数量,以及各物理工位的可用日历;
5、针对每个工单的每道基础工序构建一个动态可重构作业单元,所述动态可重构作业单元用于从对应工位类型的物理工位中选择至少一个成员物理工位,并连续完成对应工单在对应基础工序上的全部单件生产;
6、构建k-m-s三层染色体,其中k编码段用于表征各动态可重构作业单元的并行成员物理工位数量,m编码段用于表征各动态可重构作业单元的成员物理工位集合,s编码段用于表征不同工单基础工序之间的安排顺序;
7、基于所述k-m-s三层染色体生成初始种群,并对种群个体执行单件流主动解码,确定各动态可重构作业单元的启动时间、首件流出时间、末件完成时间和成员物理工位占用区间;
8、基于解码结果计算个体评价值,在不满足求解退出条件时,对种群执行选择、交叉和变异操作,并对至少部分个体执行关键链变邻域搜索,在检测到进化停滞时执行停滞灾变操作,形成下一代种群并继续迭代;
9、在满足求解退出条件时,输出目标排产方案,所述目标排产方案至少包括各工单各基础工序的并行成员物理工位数量、成员物理工位集合、作业单元时间计划和物理工位占用计划。
10、进一步地,构建所述动态可重构作业单元具体包括:对工单j的基础工序o构建作业单元ru[j,o];将该工单的生产数量q[j]个单件全部作为所述作业单元的作业对象;将并行成员物理工位数量k[j,o]设置为1至最大允许并行工位数量kmax[j,o]之间的整数;从所述基础工序对应的可用物理工位集合中选取k[j,o]个互不相同的物理工位形成成员物理工位集合m[j,o];所述作业单元启动后锁定所述成员物理工位集合m[j,o],直至该工单在该基础工序上的末件完成后解组并释放全部成员物理工位;其中,不依据k[j,o]对q[j]进行固定子批均分。
11、进一步地,所述k-m-s三层染色体中:每个工单的基础工序作业单元在k编码段中占一个位置;每个作业单元在m编码段中预留kmax个成员位置,前k个位置存储有效物理工位编号,其余位置存储非激活标识,其中kmax为对应基础工序的最大允许并行工位数量,k为该作业单元的并行成员物理工位数量;s编码段由工单标识构成,每个工单标识的出现次数等于该工单的基础工序数量,该工单标识第n次出现映射为该工单的第n道基础工序。
12、进一步地,所述单件流主动解码包括:将第一道基础工序的全部单件到达时间设置为对应工单的释放时间,将后续基础工序的单件到达时间设置为同一单件在前一道基础工序的完成时间;针对待排作业单元读取其并行成员物理工位数量k值和成员物理工位集合m;搜索所述成员物理工位集合m共同可用的最早可行占用区间;在候选启动时刻下,针对按到达时间排序的每一单件,分别计算其在各成员物理工位上的候选开始时间和候选完成时间,并将所述单件分配给候选完成时间最早的成员物理工位;以全部单件完成时间中的最小值作为首件流出时间,以最大值作为末件完成时间;在所述末件完成时间之前保持全部成员物理工位处于该作业单元的锁定状态;其中,搜索所述成员物理工位集合m共同可用的最早可行占用区间具体包括:设置所述候选启动时刻为首件到达时间、工单释放时间和各成员物理工位下一可用日历起点中的最大值;基于所述候选启动时刻执行单件流模拟得到候选末件完成时刻;检查所述候选启动时刻至所述候选末件完成时刻之间是否与任一成员物理工位已排作业单元占用区间冲突,以及是否位于全部成员物理工位的日历可用窗口内;若无冲突则确定为所述最早可行占用区间,若存在冲突则将所述候选启动时刻右移至冲突结束时刻或下一日历可用窗口起点,并重新执行单件流模拟。
13、进一步地,生成初始种群包括优先级-最早完成启发式初始化、全局物理工位负荷均衡启发式初始化和约束随机初始化中的至少两种;其中,优先级-最早完成启发式初始化根据工单优先级、交期和剩余工作量构造s编码段,并针对多个合法k值和成员物理工位集合估算作业单元完成时间;全局物理工位负荷均衡启发式初始化根据同类型物理工位累计负荷选择k值和成员物理工位集合;约束随机初始化在合法k值、合法成员物理工位集合和工单标识重复次数约束下随机生成个体。
14、进一步地,所述交叉操作包括k-m单元块交叉和s顺序交叉;所述k-m单元块交叉将同一作业单元对应的k值及其全部m成员位置作为不可分割的交叉块,使子代从任一父代整体继承所述交叉块;所述s顺序交叉基于随机选择的工单标识集合保留一个父代中对应工单标识的位置,并按另一父代中的相对顺序填充剩余位置;所述变异操作包括k变异、m变异和s变异中的至少一种;k变异在合法范围内改变作业单元的并行成员物理工位数量k,并同步增加或删除m编码段中的有效成员位置;m变异在保持k值不变的情况下替换至少一个合法成员物理工位或重新采样成员物理工位集合;s变异在保持各工单标识出现次数不变的情况下执行交换、插入或工单标识前移;当某一作业单元在当前轮发生k变异并同步调整m编码段时,该作业单元的m编码段在当前轮普通m变异中冻结。
15、进一步地,所述局部搜索为固定k的关键链变邻域搜索,包括:从决定最大完工时间的末件完成事件开始,回溯上游单件到达事件、成员物理工位占用事件和当前成员物理工位的前序加工事件,并将所述事件归并为关键作业单元链;在保持k编码段不变的条件下,依次执行成员物理工位替换邻域、关键作业单元前移邻域和阻塞作业单元后移邻域;采用首次改进方式接受更优候选,并在接受候选后重新识别关键作业单元链。
16、进一步地,当连续预定代数未获得历史最优改善且种群综合多样性低于预设阈值时执行灾变操作,所述综合多样性至少基于k编码段差异、有效m成员集合差异和s编码段顺序差异确定;所述灾变操作保留部分质量合格且差异较大的个体,并通过重新选择至少部分作业单元的并行成员物理工位数量k值、同步重采样成员物理工位集合m、扰动s编码段顺序以及重新初始化个体中的至少一种方式重构活动种群;历史最优个体独立存储于活动种群之外。
17、进一步地,所述目标排产方案用于控制柔性可重构电子单机装配线的生产执行:在作业单元启动时锁定成员物理工位集合m中的k个成员物理工位;将已到达的单件派发至空闲成员物理工位;任一成员物理工位完成一个单件后,将该单件释放至下一基础工序,并在本作业单元仍有已到达未加工单件时继续向该成员物理工位派发下一单件;在暂时无已到达单件时保持该成员物理工位处于本作业单元的锁定等待状态;在本作业单元末件完成后解组并释放全部成员物理工位。
18、第二方面,本发明提供一种电子设备,包括至少一个处理器和与所述至少一个处理器通信连接的存储器;所述存储器存储有可被所述至少一个处理器执行的指令,所述指令被执行时,使所述至少一个处理器实施权利要求1至9中任一项所述的方法。
19、第三方面,本发明提供一种计算机可读存储介质,所述计算机可读存储介质上存储有计算机程序,所述计算机程序被处理器执行时实现权利要求1至9中任一项所述的方法。
20、与现有技术相比,本发明的有益效果在于:
21、本发明通过工单-工序动态可重构作业单元,将多个同类型物理工位共同连续完成一个工单工序的生产组织方式直接写入排程模型,使排程模型能够直接表达多工位动态组合的资源形态;配合k-m-s三层染色体对并行成员物理工位数量、成员物理工位集合和工单工序安排顺序的联合编码,在同一模型中统一表达单工位单件流、多工位并行组元以及固定子工序等多种生产模式,在计划层同时完成资源组合优化与优先顺序优化,且染色体规模保持在工单-工序级别,避免任务规模随工单数量和产品数量膨胀而产生大量同质单件等价排列,有效控制搜索空间。
22、本发明通过单件流主动解码,在成员物理工位共同可行的最早占用区间内依据单件到达事件动态派发单件,获得单件到达、首件流出、末件完成和物理工位占用时间,无需将工单数量预先拆分为固定批次或固定子批,从机制上消除以批次整体完工时间作为后续工序启动条件所带来的不必要等待;通过单件完成即时转序、成员物理工位持续锁定服务和末件完成整体解组的协同机制,使计划层排程与现场“谁先完成谁取下一箱”的动态派工自然衔接,作业速度较快的成员物理工位自然承担更多单件,提高排程方案对成员物理工位实际速度差异的适应性,同时保持工单工序总数量守恒。
23、本发明通过以有效平均利用率为主、最大完工时间和成员物理工位锁定等待时间为辅的个体评价,引导搜索方向贴近现场真实产出能力;通过固定k的关键链变邻域搜索,在有限评价预算内对决定最大完工时间的关键作业单元链实施定向改进,并通过基于综合多样性的停滞检测与灾变重构跳出长期停滞,提高复杂混线场景下的搜索能力、求解稳定性和排产方案的工程可执行性,能够获得实际生产中相对较优的排程。
24、本发明的其他优点、目标和特征在某种程度上将在随后的说明书中进行阐述,并且在某种程度上,基于对下文的考察研究对本领域技术人员而言将是显而易见的,或者可以从本发明的实践中得到教导。本发明的目标和其他优点可以通过下面的说明书来实现和获得。
版权声明:本站专利文献数据主要来源于国家知识产权局等公开渠道,由 技术新讯 进行整理汇编。页面设计及数据汇编的著作权归本站所有。全部内容仅供个人学习、科研评估与技术交流参考,严禁用于任何商业用途(包括但不限于直接生产制造、技术转让、倒卖数据等)。
免责条款:专利技术具有时效性,本站不对资料的绝对准确性、完整性和可实施性提供任何明示或暗示的担保。因参考本站内容造成的直接或间接损失,本站不承担相关法律责任。若您认为本站内容有侵权问题,请及时提供权属证明与我们联系,本站将在核实后依法处理。反馈意见:yyfuon@163.com