一种基于物料依赖LLC拓扑分级的大规模MRP并行消纳调度方法及系统与流程

摘要: 本发明涉及物料需求计划(mrp)及高级计划与排程(aps)。具体地说是一种基于物料依赖llc拓扑分级的大规模mrp并行消纳调度方法及系统。背景技术:1、在离散制...
一种基于物料依赖LLC拓扑分级的大规模MRP并行消纳调度方法及系统与流程

本发明涉及物料需求计划(mrp)及高级计划与排程(aps)。具体地说是一种基于物料依赖llc拓扑分级的大规模mrp并行消纳调度方法及系统。

背景技术:

1、在离散制造行业(如电子组装、汽车制造、重型装备等)中,物料需求计划(mrp) 是供应链运营的核心发动机。它的基本职能是根据客户订单及预测需求,沿着物料清单(bom,bill of materials)结构,自上而下逐层扣减在库库存、在途供应,并在物料缺口处生成建议的采购计划或生产计划(planned orders)。

2、在大规模离散制造工厂中,mrp 计算面临极高的计算压力与时效痛点:

3、1、物料结构依赖深度(bom级联)带来的“计算串行化”瓶颈。

4、物料之间存在强烈的父子级联依赖关系(如成品fg消耗半成品sub,半成品sub消耗原材料raw)。计算父项的建议补货量后,产生的需求会自动传递为子项的毛需求。这导致mrp 必须严格按照物料结构由上至下计算,无法进行盲目的全局并行。传统 mrp 系统只能采用单线程顺序遍历数十万种sku节点,导致大批量计划计算耗时长达数小时,无法融入what-if沙箱秒级决策中。

5、2、多层级bom环路死锁(circular dependency)导致计算挂起。

6、在企业工程变更(ecn)频繁或主数据维护混乱时,极易产生物料间的环路依赖(例如a的子件包含b,b的子件包含c,c的子件又指回a)。如果排程引擎在没有静态环路检测的情况下盲目多线程计算,计算会陷入无穷递归(栈溢出)或线程间互等死锁(deadlock),导致计算引擎彻底崩溃挂起。在复杂的网络图结构中,动态环路检测开销极大,传统系统只能在计算中抛错或限制计算层级。

7、3、多线程并发锁竞争与缓存未命中(cache miss)。

8、若传统系统试图使用简单的面向对象(oop)多线程技术,即为每个物料节点分配一个独立计算线程,由于父子节点间频繁的需求传递和状态更新,线程之间必须对共享的物料库存和分配账本进行高频加锁。高额的线程锁争用(lock contention)以及复杂的指针跳转导致cpu的l1/l2缓存频繁失效,多核处理器的计算效能反而会退化甚至低于单线程。

9、因此,亟需一种基于物料依赖llc拓扑分级的大规模mrp并行消纳调度方法及系统,以解决传统mrp在大规模计算中串行耗时极长、bom 环路死锁崩溃以及多线程并发锁争用剧烈的技术问题,实现秒级静态拓扑防环、层内绝对并行零冲突以及接近cpu物理极限的极速计划计算。

技术实现思路

1、为此,本发明所要解决的技术问题在于提供一种基于物料依赖llc拓扑分级的大规模mrp并行消纳调度方法及系统,解决了传统mrp在大规模计算中串行耗时极长、bom环路死锁崩溃以及多线程并发锁争用剧烈的技术问题,实现秒级静态拓扑防环、层内绝对并行零冲突以及接近cpu物理极限的极速计划计算。

2、为解决上述技术问题,本发明提供如下技术方案:

3、一种基于物料依赖llc拓扑分级的大规模mrp并行消纳调度方法,包括如下步骤:

4、步骤p1、载入物料及bom基础数据,通过带环路识别的深度优先拓扑遍历,生成各物料对应的低层码;

5、步骤p2、将产品结构bom拓扑编译为在物理内存中连续排布的扁平数组;

6、步骤p3、拓扑编译完成后,依据低层码划分多层并行计算网格并在网格内多线程并发完成物料供需测算,通过无锁跨层需求传递与层级同步机制完成mrp并行消纳调度。

7、上述一种基于物料依赖llc拓扑分级的大规模mrp并行消纳调度方法,步骤p1中,带环路识别的深度优先拓扑遍历的具体过程包括:

8、步骤p1-1、以成品物料为起点遍历物料有向超图,采用三色状态标记方式区分各物料节点的遍历状态;

9、步骤p1-2、遍历过程中统计每个物料所有依赖路径的最大深度,生成对应低层码;

10、步骤p1-3、遍历过程中若识别出循环依赖关系,则触发静态环路检测拦截器。

11、上述一种基于物料依赖llc拓扑分级的大规模mrp并行消纳调度方法,步骤p1-1中,三色状态标记方式为:白色标记表示未访问、灰色标记表示正在访问、黑色标记表示访问完毕。

12、上述一种基于物料依赖llc拓扑分级的大规模mrp并行消纳调度方法,步骤p1-2中,成品低层码为0,底层原材料的低层码最大。

13、上述一种基于物料依赖llc拓扑分级的大规模mrp并行消纳调度方法,步骤p1-3中,识别出循环依赖关系表现为:在搜索过程中碰到了灰色标记节点;

14、静态环路检测拦截器执行:

15、a、中止拓扑计算;

16、b、通过递归调用栈逆向提取成环物料依赖链路,将包含成环节点与路径的异常信息持久存入审计数据库。

17、上述一种基于物料依赖llc拓扑分级的大规模mrp并行消纳调度方法,步骤p2的具体过程包括:

18、步骤p2-1、构建物料编码映射词典,将字符串格式的物料编码统一转换为固定长度数字标识;

19、步骤p2-2、将树形bom依赖关系拆解为标准化扁平关联记录,并统一存储为数组结构;

20、步骤p2-3、对全部扁平关联记录按照父物料标识排序,使同一父物料对应的全部子物料记录在物理内存中连续存储,并构建首尾偏移索引向量,实现常数时间内存定位与cpu缓存预取。

21、上述一种基于物料依赖llc拓扑分级的大规模mrp并行消纳调度方法,步骤p3中,依据低层码划分多层并行计算网格并在网格内多线程并发完成物料供需测算的具体过程包括如下步骤:

22、步骤p3-1、依据各物料对应的最大低层码对全部物料分组,形成多层并行计算网格;

23、步骤p3-2、设置外层时序循环,按照低层码由小至大的顺序逐层开展计算,在单层网格内部通过openmp线程池分发多核并发计算,并在每层计算完成后执行层级屏障同步,再进入下一层网格计算;

24、步骤p3-3、基于同低层码物料无相互依赖的特性,对单层网格内全部物料采用多线程并发执行供需扣减计算。

25、上述一种基于物料依赖llc拓扑分级的大规模mrp并行消纳调度方法,步骤p3中,物料供需测算产生缺口时生成计划订单,结合单件消耗系数计算向下游子物料传导的拉动量。

26、上述一种基于物料依赖llc拓扑分级的大规模mrp并行消纳调度方法,步骤p3中,利用子物料低层码高于父物料的层级隔离特性,采用硬件级原子指令进行物理内存直接累加,将拉动量叠加至对应子物料的需求数据中,消除线程互斥锁开销并确保累加操作的绝对正确性。

27、一种基于物料依赖llc拓扑分级的大规模mrp并行消纳调度系统,用于实施上述大规模mrp并行消纳调度方法,包括:

28、低层码生成模块,用于载入物料及bom基础数据,通过带环路识别的深度优先拓扑遍历,生成各物料对应的低层码;

29、拓扑编译模块,用于将产品结构bom拓扑编译为在物理内存中连续排布的扁平数组;

30、供需测算模块,用于在拓扑编译完成后,依据低层码划分多层并行计算网格并通过openmp线程池在网格内多线程并发完成供需扣减,并基于硬件级原子指令实现无锁跨层需求传递与层级屏障同步,完成mrp并行消纳调度。

31、本发明的技术方案取得了如下有益的技术效果:

32、本发明基于低层码同级物料无依赖特性实现层级内无锁并发求解,消除多线程数据竞争带来的锁等待开销,进而消除了父子依赖在同级计算中的冲突,计算效率随着cpu核心数呈线性增长。针对包含5万种物料、300万笔订单的大规模mrp级联展开场景,现有串行方案耗时通常达数小时,采用本方法可将整体求解耗时压缩至800毫秒以内,大规模供需测算效率实现跨越式提升。

33、本发明在mrp正式求解启动前,通过三色标记深度优先遍历(dfs)完成全量物料依赖图环路检测,提前识别并拦截bom循环依赖异常,同步留存完整异常链路审计记录。从根源规避求解过程中递归栈溢出、多线程死锁等程序崩溃问题,实现物料拓扑异常100%预拦截,大幅降低系统运行故障概率。

34、本发明采用面向数据dod的扁平化连续内存存储架构,搭配分层动态分批调度机制(dynamic chunking),重构传统面向对象离散存储带来的内存碎片化问题,提升cpu缓存行(cache line)命中率至95%以上,大幅减少缓存失效次数,彻底规避了传统oop结构带来的频繁cache miss,实现无锁并发、无冗余内存拷贝的高速数据读取,进一步降低算力损耗。