一种基于遗传算法的异构并行车间排产方法

专利2025-04-29  22


本发明涉及车间排产调度优化,尤其涉及一种基于遗传算法的异构并行车间排产方法。


背景技术:

1、随着网络信息化的发展,智能工厂的模样逐渐清晰,提高制造车间生产效率,实现智能化管理车间的目标不断在实体企业中落地,使得企业生产车间中的排产调度优化问题得到了很大改善;先进的制造系统和信息系统的使用,令原本低效的人工排产方式逐渐得到优化。排产问题可以基本描述为:如何在合理的时间内把有限的资源分配给各个任务,以满足一个或多个优化目标。合理的排产可以有效地减少生产加工所需要的时间,提高生产效率,节省资源消耗从而降低生产成本。同时对于企业工厂的生产车间进行排产优化之后,根据优化后的排产方案进行生产,可以获得较好的优化结果,使得生产加工正常运行。优良的排产计划能够帮助制造企业缩短完工时间、减少成本、提升生产效率和机器使用率,因此研究生产制造业的排产问题具有十分重要的现实意义。

2、在车间调度中,并行机调度问题是指在车间内有多台可用的机器可以同时处理不同的工件,并且需要将工件分配到这些机器上,以便最大化车间的生产效率。在这种情况下,目标是为每个工件组分配一个开始时间,并指定每个工件在机器上的加工时间,以便最小化完成所有工件所需的总时间。若干个并行机组成的多个车间,存在有些车间的加工速度不同,这种加工环境称为异构并行车间。在实际生产中,车间调度问题具有复杂性、动态随机性、多目标性等特性,在计算量上属于np-hard(非确定性多项式)问题,无法精确求解,所以许多研究学者研究这一问题均采用各种智能方法来对问题进行求解。

3、遗传算法(ga)起源于对生物系统所进行的计算机模拟研究,是一种随机全局搜索优化方法,它模拟了自然选择和遗传中发生的复制、交叉和变异等现象,从任一初始种群出发,通过随机选择、交叉和变异操作,产生一群更适合环境的个体,使群体进化到搜索空间中越来越好的区域,这样一代一代不断繁衍进化,最后收敛到一群最适应环境的个体,从而求得问题的优质解。

4、传统车间生产调度模型通常以最小化最大生产时间、最小化总生产时间、最小化总延迟时间等为优化目标建立数学模型,不够切合实际车间生产。多数群体智能算法初始种群的个体是给定范围内随机生成的,具有较大的随机性和不确定性。此外智能优化算法的寻优方式不一样导致每种算法的寻优能力也不同,有些算法容易陷入局部最优或者偏离目标。

5、因此为了解决上述问题,提出一种基于遗传算法的异构并行车间排产方法。


技术实现思路

1、本发明提供一种基于遗传算法的异构并行车间排产方法,以解决现有车间生产调度模型以最小化最大生产时间、最小化总生产时间、最小化总延迟时间等为优化目标建立数学模型,不够切合实际车间生产的问题。

2、本发明提供一种基于遗传算法的异构并行车间排产方法,所述方法包括:

3、对粗排产的结果进行数据前处理,将粗排产的结果组装成优化器所需要的输入数据,所述输入数据包括加工任务和物料;

4、将优化器的参数以及输入数据输入优化器;

5、优化器根据预先定义的问题约束条件与目标函数,在所述问题约束条件下,采用遗传算法搜索目标函数的最优解作为最终输出的加工决策;

6、其中,加工工件按照合同号和订单号编号,每个合同包含若干个订单,每个订单由若干同种产品组成,订单允许按产品数量拆分成若干份生产,每个订单或者产品由不同的物料按比例生产,订单分为a、b两种类型;加工机器存在两种类型的车间,混流车间和非混流车间,实际调度以车间为单位;每个车间有若干个机器,机器之间完全一致,只是根据加工速度的不同分为a、b两种类型;

7、所述问题约束条件如下:同一合同不同订单按照先后顺序生产,且尽量安排在同一机器上生产;在订单加工时需要对物料按照消耗系数*加工单位数量进行消耗,物料不足时无法生产;机器的能力按照消耗系数*加工数量进行消耗,能力不足时无法生产;工件的合同号每发生一次切换,对当天该机器的能力进行扣减,扣减的数量为当天能力总数*能力损失百分比;车间的全部机器上,任意时刻可以同时加工n个订单,n为车间参数中设置的最大并行加工订单数;前六周最大提前生产天数10天,其余时间最大提前生产天数为14天;工件在同一台机器上需满足连续生产γ小时以上,γ为超参数;

8、所述目标函数为最小化总成本,所述目标函数的数学模型如下:

9、

10、s.t.sih+pih≤sij+g·(1-xhj),i=1,2,3,…,m,

11、h=1,2,3,…,n,j=1,2,3,…,n.                  (1.2)

12、xhj+xjh=1,h=1,2,3,…,n,j=1,2,3,…,n.             (1.3)

13、cj≥0,j=1,2,3,…,n.                     (1.4)

14、sij≥0,eij≥0,i=1,2,3,…,m,j=1,2,3,…,n.           (1.5)

15、xhj∈{0,1},h=1,2,3,…,n,j=1,2,3,…,n.            (1.6)

16、其中,参数说明:

17、j:工件集合,j={1,2,3,…,n},其中n为工件数;

18、m:机器集合,m={1,2,3,…,m},其中m为机器数;

19、pih:工件h在机器i上处理时间;

20、g:无穷大正数;

21、决策变量:

22、sij:工件j在机器i上的开始处理时间;

23、sih工件h在机器i上的开始处理时间;

24、eij:工件j在机器i上的完成时间;

25、cj:工件j的加工总成本;

26、di:机器i上的合同切换成本

27、xhj:整数决策变量,若工件h为工件j的紧前工件,则xhj=1;

28、否则,xhj=0;

29、xjh:若工件j为工件h的紧前工件,则xjh=1;

30、否则,xjh=0;

31、式(1.1)表示目标函数为最小化总生产成本;式(1.2)表示同一时间每台机器只能处理一个工件;式(1.3)表示机器上工件的顺序关系;式(1.4)(1.5)及(1.6)定义了变量的取值范围;

32、对所述加工决策进行数据后处理,组装成排产结果。

33、进一步地,所述目标函数的数学模型中,工件j的加工总成本cj包括:

34、跨类型生产成本:加工决策中,a类工件在b类机器上生产或b类工件在a类机器上生产时,产生跨类型生产成本;

35、过早开工成本:加工决策中,有加工时间小于加工任务的要求完工时间减去最大提前加工天数时,产生过早开工成本;

36、延迟成本:加工决策中,有加工时间大于加工任务的要求完工时间,产生延迟成本;

37、缺货成本:加工决策中,实际加工数量小于加工任务要求的加工数量,产生缺货成本;

38、粗排产提前偏差成本:加工决策中,加工日期小于粗排产加工时间_开始的部分,产生粗排产提前偏差成本;

39、同时,机器i的切换成本di包括:

40、跨合同切换成本:同一机器在连续时间上生产不同合同号的工件时,产生跨合同切换成本;

41、将所述跨类型生产成本、过早开工成本、延迟成本、缺货成本、粗排产提前偏差成本以及跨合同切换成本计算后汇总。

42、进一步地,优化器根据预先定义的问题约束条件与目标函数,在所述问题约束条件下,采用遗传算法搜索目标函数的最优解作为最终输出的加工决策,包括:

43、根据工件的合同号进行编码;

44、在初始化种群时进行如下操作:根据完工时间对待加工工件的合同号进行权重赋值,完工时间越晚权重越大,使其更可能在安排生产时排序靠后;w=(合同完工时刻-项目开始时刻)/(项目结束时刻-项目开始时刻);随机生成一个小数α代表生产顺序,α∈(0,1),令α=α*w,根据α的大小进行生产顺序的排序;随机生成一个整数β∈(1,m),代表工件安排几台机器生产,m为此时刻机器总数;初始种群中精英个体的α=w,其它不变;

45、将所述目标函数作为适应度函数,计算种群中每个个体的适应度,得到所述目标函数的可行解;

46、对所述可行解依次进行选择操作、交叉以及变异,得到新生成的子代个体;

47、将所述新生成的子代个体加入原种群中,形成新一代种群;

48、对新一代种群重复进行适应度计算、选择、交叉和变异操作,直到满足预先设置的收敛条件,输出最优化个体结果作为最终输出的加工决策。

49、进一步地,对所述可行解依次进行选择操作、交叉以及变异,得到新生成的子代个体,包括:

50、按照个体的适应度进行选择操作,从当前种群中选择出适应度较高的个体作为父代;

51、对被选中的两个父代个体进行交叉,产生新的个体;

52、随机生成一定的新个体,加入到种群中;其中,复制、交叉和变异比例为2:7:1;交叉时父染色体选择采用锦标赛法,锦标赛比例为15%,随机从父代种群挑选出上述比例个体,挑选表现最好的两条作为父代个体;交叉操作采用两点交叉方法。

53、进一步地,将所述目标函数作为适应度函数,计算种群中每个个体的适应度,得到所述目标函数的可行解,需要所述方法进行安排生产的操作:

54、步骤1,记录当前时刻各个车间n的约束、各个机器的最早可用时间、各个机器最后加工订单的加工时间;

55、步骤2,检查所有订单是否安排完毕,若安排完毕则结束求解;若未安排完毕,获取当前待安排订单,计算各个机器的能力衰减,更新当前时刻各个机器的最早可用时间,按照以下准则得到机器的优先级序列,并更新n的值;所述准则包括:选择机器时,相同合同的工件优先,其次参考机器可用时间;机器可用时间相差1时视为相同;对n=1的同车间机器进行统一调度;

56、步骤3,按照优先级序列得到优先加工机器的编号;

57、步骤4,根据物料的存量计算当天可加工的产品数量,对订单进行加工,尽量保证各个订单加工的结束时间一致;

58、步骤5,判断当前订单是否加工完毕;若加工完毕,更新当前时刻各个机器的最早可用时间、各个机器最后加工订单的加工时间,回到步骤2;若未安排完毕,继续下一步骤;

59、步骤6,判断是否达到下一个机器的可加工时间,若达到时间,回到步骤3;若未达到时间,令当前时刻为下一天的开始加工时间,回到步骤4。

60、本发明具有以下有益效果:本发明的基于遗传算法的异构并行车间排产方法,对粗排产的结果进行数据前处理,将粗排产的结果组装成优化器所需要的输入数据,输入数据包括加工任务和物料;将优化器的参数以及输入数据输入优化器;优化器根据预先定义的问题约束条件与目标函数,在问题约束条件下,采用遗传算法搜索目标函数的最优解作为最终输出的加工决策;对加工决策进行数据后处理,组装成排产结果;通过遗传算法全局优化后的生产计划主要的改进点是对产品加工顺序的重排,更合理地安排较多的机器投入生产,重新组织生产序列来减少整体完工时间,以及替换机器类型获得更合理的加工路线。生产者可以根据整体的排产计划,设计出一个更为合理的加工路线,从而提高生产效率,缩短生产周期。


技术特征:

1.一种基于遗传算法的异构并行车间排产方法,其特征在于,所述方法包括:

2.如权利要求1所述的一种基于遗传算法的异构并行车间排产方法,其特征在于,所述目标函数的数学模型中,工件j的加工总成本cj包括:

3.如权利要求1所述的一种基于遗传算法的异构并行车间排产方法,其特征在于,优化器根据预先定义的问题约束条件与目标函数,在所述问题约束条件下,采用遗传算法搜索目标函数的最优解作为最终输出的加工决策,包括:

4.如权利要求3所述的一种基于遗传算法的异构并行车间排产方法,其特征在于,对所述可行解依次进行选择操作、交叉以及变异,得到新生成的子代个体,包括:

5.如权利要求3所述的一种基于遗传算法的异构并行车间排产方法,其特征在于,将所述目标函数作为适应度函数,计算种群中每个个体的适应度,得到所述目标函数的可行解,需要所述方法进行安排生产的操作:


技术总结
本发明公开一种基于遗传算法的异构并行车间排产方法,该方法包括:对粗排产的结果进行数据前处理,将粗排产的结果组装成优化器所需要的输入数据,将优化器的参数以及输入数据输入优化器;优化器根据预先定义的问题约束条件与目标函数,在问题约束条件下,采用遗传算法搜索目标函数的最优解作为最终输出的加工决策;对加工决策进行数据后处理,组装成排产结果。本发明通过遗传算法全局优化后的生产计划主要的改进点是对产品加工顺序的重排,更合理地安排较多的机器投入生产,重新组织生产序列来减少整体完工时间,以及替换机器类型获得更合理的加工路线。

技术研发人员:温玉玺,陈鑫,卢浩,孙延森
受保护的技术使用者:辽宁工业大学
技术研发日:
技术公布日:2024/6/26
转载请注明原文地址:https://doc.8miu.com/index.php/read-1819328.html

最新回复(0)