一种基于有限缓存约束的多目标进化生产调度方法与流程

摘要: 本发明涉及,尤其涉及一种基于有限缓存约束的多目标进化生产调度方法。背景技术:1、在精益生产理念的驱动下,国内制造业正经历着一场的产线升级改造浪潮。这一变革旨在通...
一种基于有限缓存约束的多目标进化生产调度方法与流程

本发明涉及,尤其涉及一种基于有限缓存约束的多目标进化生产调度方法。

背景技术:

1、在精益生产理念的驱动下,国内制造业正经历着一场的产线升级改造浪潮。这一变革旨在通过深化专业化分工、缩短生产周期、提升资源利用率,并确保生产过程按既定节拍平稳运行,从而构建高效协同的制造体系。本质上,生产线是一个高度集成化的生产系统,它严格遵循产品的设计要求与工艺规范,将各类零部件、组件及子系统按照预定的顺序进行制造与组装,最终实现各类产品的高效产出。

2、产线调度问题是处理工件加工顺序的排列组合爆炸问题,为np-hard问题,具有高度的复杂性和多约束性。现实的产线中,工序间的缓冲区容量往往是有限的。当有限缓存空间被占满时,上游设备将被迫停止作业,处于阻塞状态,无法释放已加工完毕的工件,进而导致整条产线停顿甚至死锁。

3、针对考虑缓存的产线调度问题,传统的精确算法(如分支定界法、整数规划)在小规模问题上虽能求得最优解,单随着调度问题规模不断扩大,算法求解耗时将呈指数级增长,难以满足实际生产的实时性要求;启发式多目标进化算法因其构造简单、求解速度快、求得解具备可解释性的特点,已在工业生产调度场景得到普遍应用,但其优化解的综合性能仍存在较大提升空间;在此背景下,多目标进化算法凭借较快的优异的多维度寻优能力,逐步成为复杂产线调度问题的重要求解方案。

技术实现思路

1、本发明的目的在于提供一种基于有限缓存约束的多目标进化生产调度方法,以解决上述背景技术中提出的问题。

2、为实现上述目的,本发明提供如下技术方案:

3、一种基于有限缓存约束的多目标进化生产调度方法,包括如下步骤:

4、s110,构建生产线调度模型,建立车间中工单集合,建立资源类集合,相邻资源类设置缓存b,其缓存容量为;

5、s120,定义有限缓存约束的生产线调度模型的参数变量,设定总拖期时长和制造周期目标函数,对参数变量施加约束条件;

6、s130,工单集合每个个体进行编码,生成初始种群p0,根据改进的nsga-ii算法进化迭代,生成当前父代种群和当前子代种群,得到当前父代种群和当前子代种群的总拖期时长和制造周期的目标值,并根据目标值进行非支配排序,选择生成新父代种群;结合贪心算法迭代计算获取最终父代种群;

7、s140,基于有限缓存的并行调度方法,设置候选工单集合以及缓存占用集合,从候选工单集合调取最优先工序对应的工件至相应的资源类进行生产,实时缓存占用集合,从最终父代种群中寻优,确定生产线调度模型的最优方案。

8、优选的,所述s110包括如下步骤:

9、s110-1,对每个工单执行工序建立工序集合,其中每个工单的工序顺序不尽相同,每个工单的交货期为;

10、s110-2,资源类内包括工位类和设备类,每个工位类对应的设备类包括多台相同设备,同一设备类的设备加工速度相同;

11、s110-3,对于任一工单内的单件工件,分派其第k道工序至对应资源类,对应资源类内采用任意一台设备上加工,单件工件的加工时间为;

12、s110-4,在任一资源类与其后置资源类之间设置缓存b,每个缓存b可容纳工件数量,若缓存b内工件数量已占满,则其对应的前置资源类工件加工完成发生阻塞。

13、优选的,所述s120中参数变量包括:

14、:连续变量,表示工单的第 k 道工序的第n件的开始加工时间;

15、:连续变量,工单的第 k 道工序的第n件的完工时间;

16、:二进制变量,工单早于进入投产,则为1;否则为0;

17、:二进制变量,表示单件工序分配到对应资源类下设备m上加工,则为1,否则为0;

18、:第k道工序分派至对应资源类内任意一台设备上工件的加工时间。

19、优选的,所述s120中总拖期时长目标函数为:

20、 (1)

21、式(1)中表示为总拖期时间最小,其中总拖期时间为每一个工单 的拖期时间(tardiness)之和;单工单拖期为工单完工时刻与交货期差值同0的较大值,取全部工单拖期的和作为总拖期时间;

22、 (2)

23、式(2)中表示为制造周期最小,其中,取每一个工单 全部工序完工时刻的最大值作为制造周期;

24、所述s120中参数变量的约束条件为:

25、 (3)

26、式(3)表示每个工单的每个工件在每道工序必须且只能分配到对应资源类下的一台设备上加工;

27、 (4)

28、式(4)表达同一工单在同一道工序 k 上,若多个工件分配到同一台设备,需保持顺序流转,即必须在上件工件完工后才能开始加工下件工件;

29、 (5)

30、式(5)表达若工单早于工单投产,并且均有工序在同一资源类w上加工,可以确定均有工序的加工优先级;

31、       (6)

32、式(6)表达若工单早于工单投产,并且均有工序在同一资源类w上加工,可以确定均有工序的加工优先级;

33、                 (7)

34、式(7)表达根据缓存容量限制,确保了当前置资源类将工件加工完成时,后置资源类对应的缓存b必然有空位接纳,从而避免死锁或非法调度;

35、                          (8)

36、式(8)表达资源类设置的缓存b容纳工件数量不大于缓存最大容量。

37、优选的,所述s130包括如下步骤:

38、s130-1,基于工序顺序对工单集合每个个体编码设计,并生成初始种群p0,初始化参数;其中,初始化参数包括包括每个工单交货期为,单个工件加工时间、最大迭代次数;

39、s130-2,通过选择、交叉和变异操作执行进化过程并进行迭代循环,生成当前父代种群和当前子代种群;

40、s130-3,对当前父代种群解码和子代种群内的每个个体进行解码,执行总拖期时长和制造周期的目标函数,获得当前父代种群和当前子代种群内每个个体的目标值;

41、s130-4,将当前父代种群和当前子代种群内的所有个体的目标值进行非支配排序分组;

42、s130-5,基于上述非支配排序分组,依次将各组纳入下一代父代种群中;若下一代父代种群个体数量小于预设数量n时,通过贪心算法计算其余组中所有的最小距离,选择其中最大值对应的种群挪入下一代父代种群中;

43、s130-6,继续执行步骤s130-2~s130-5,直到达到最大迭代次数,获取最终父代种群。

44、优选的,所述s140包括如下步骤:

45、s140-1,初始化参数变量,设定当前阶段g=1,即时刻,设定已完成工单集合、执行工单集合、以及缓存占用集合为空,选择候选工单集合取入度为0的工件投入生产;

46、s140-2,更新当前阶段g,更新当前时刻,更新当前时刻的执行工单集合和已完成工单集合;基于工件的优先级,从候选工单集合中选择一个最优先的工序进行分派,将候选工单集合更新;同时,实时计算监测更新缓存占用集合的容量;

47、s140-3,若工序有空闲资源类可以分派,则计算并设置工件的开始时间为、完工时间、将其到对应资源类上加工,并更新执行工单集合;

48、s140-4,若工序有空闲资源类可以分派,工件从上道工序所用资源类对应的缓存b取出,并同步更新缓存占用集合的工件数量;

49、s140-5,若工序没有空闲资源类可以分派,同时已完成工序所用资源类对应的缓存b有空闲,则该工件暂存至相应缓存b内;

50、s140-6,若工序没有空闲资源类可以分派,同时已完成工序所用资源类对应的缓存b没有空闲,则发生阻塞,等待所用资源类对应缓存b空闲暂存,或等待下一道工序所用资源类空闲进行投料生产;

51、s140-7,重复执行s140-2至s140-6,直到候选工单集合为空集,则该生产线调度模型完成。

52、优选的,所述s130-2具体步骤为:执行工单集合中工件对应工序最早完成时间,以其完成时间点更新当前时刻,并划定当前时段,以其完成时间点进行阶段g更新。

53、优选的,所述s130-3中候选工单集合更新包括如下步骤:从候选工单集合中寻找最优先工件,从最优先工件中寻找前置工序已完工,或者前置工单执行工序为空,即选择工单已开工但作为最优先工件的下一道工序未分派,或者仍然未开工的工单作为最优先工件的首工序,将其作为最优先工序进行分派,进而更新候选工单集合

54、优选的,所述最优先工件设定规则为:工件交付时间越早的工件优先级越高;当当任一工单和工单和的交付时间相同时,优先选择总加工时间最短的;若总加工时间仍相同,则随机选择任一工单,将其中优先级最高的工件开始进行生产投料。

55、优选的,所述s130中生产线调度模型在满足缓存约束的情况下,每次迭代仅从任一工单内的单件工件的工序集合分派一个。

56、与现有技术相比,本发明具有以下有益效果:

57、本发明提供的一种基于有限缓存约束的多目标进化生产调度方法,基于有限缓存约束的多目标进化算法,通过工件优先级的设定调度,生产调度模型可以逐步更新已完成工单集合、执行工单集合、候选工单集合、以及缓存占用集合,确保工单在满足缓存约束下被有效调度,避免出现无解的情况,使生产中的某个环节被迫暂停,进而提高生产调度过程的稳定性,保证生产系统的正常流转运行。