一种基于线程局部零堆分配回滚栈与时空网格的有限能力排产方法及系统与流程

摘要: 本发明涉及企业级高级计划与排程(aps)、多约束生产排产(iop)。具体地说是一种基于线程局部零堆分配回滚栈与时空网格的有限能力排产方法及系统。背景技术:1、在...
一种基于线程局部零堆分配回滚栈与时空网格的有限能力排产方法及系统与流程

本发明涉及企业级高级计划与排程(aps)、多约束生产排产(iop)。具体地说是一种基于线程局部零堆分配回滚栈与时空网格的有限能力排产方法及系统。

背景技术:

1、在现代离散制造业(如半导体封测、精密机械加工、高频换型装配等)中,有限能力排产与实时可承诺量(ctp)是高级计划与排程(aps)系统的核心决策大脑。当销售人员在控制塔前端录入一笔新的急单时,系统需要对全网的设备产能日历进行实时仿真演算,以确认在物料齐套和设备不超载的前提下,该订单的最早完工期(atp/ctp date),并在确认成交后对产能资源进行正式锁定。

2、为了寻找可行或最优的生产路径,求解器引擎通常在多级有向无环图(dag)构成的工艺路线与物料bom树上运行深度优先搜索(dfs)或回溯法(backtracking)。

3、然而,现有的排产引擎在处理高频 ctp 承诺与有限能力回溯排产时,面临极大的计算瓶颈:

4、1、高频堆内存申请(heap allocation)引起严重内存抖动

5、在进行dfs路径搜索时,每尝试一条工艺路线(routing)或工序(operation),引擎都需要向系统申请内存来记录当前的产能预扣减事务日志,以便在某条路径由于物料或设备瓶颈走不通(fail)回溯时进行状态还原。对于拥有数万种sku和复杂约束的网络,高频ctp计算会产生数百万次malloc/new内存申请。这会导致严重的操作系统内核锁竞争,产生内存碎片,使cpu耗费大量时间在堆内存管理和垃圾回收上,计算延迟从毫秒级退化为秒级,无法支持实时并发承诺。

6、2、串行事务互斥锁导致多线程吞吐率暴跌

7、当多位计划员在不同沙箱场景或多渠道订单并发进行 ctp 试算时,由于它们在同一物理机台(work center)的产能日历上进行预占,传统系统需要使用互斥锁(mutex/spinlock)保护天级产能数组。这导致严重的线程阻塞与上下文切换(context switch),使得多核处理器的并发性能急剧退化,系统吞吐量极低。

8、3、换型洗枪切换矩阵(setup matrix)导致搜索空间呈指数膨胀

9、在复杂流程及组装行业中,机台从生产产品a切换到产品 b 时需要进行设备清洗或换模(如半导体封测清洗、化工洗罐),其换型时间(setup time)强依赖于前后订单的生产顺序(sequence-dependent setup)。这导致排产搜索空间呈指数级爆炸,如果无法在回溯过程中以o(1)速度快速累加与撤销换型开销,整个有限能力求解器将陷入算力灾难。

10、因此,亟需一种基于线程局部零堆分配回滚栈与时空网格的有限能力排产方法及系统,以在保证排产约束100%物理精准的前提下,消除高频回溯时的内存分配开销,实现无锁高并发的有限能力排产。

技术实现思路

1、为此,本发明所要解决的技术问题在于提供一种基于线程局部零堆分配回滚栈与时空网格的有限能力排产方法及系统,解决了传统排产方法在高频回溯计算中堆内存抖动剧烈、线程锁竞争严重以及顺序相关换型计算开销巨大的技术问题,实现了零堆分配事务回滚、无锁高并发ctp寻优以及毫秒级的有限能力排配。

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

3、一种基于线程局部零堆分配回滚栈与时空网格的有限能力排产方法,包括如下步骤:

4、步骤p1、构建用于存储设备周期产能的扁平时空产能网格和用于存储产品切换耗时的扁平换型时间矩阵;

5、步骤p2、依托线程局部零堆分配回滚栈机制记录产能与换型消耗,并在推演路径冲突时快速回退产能状态,以避免产生堆内存动态申请;

6、步骤p3、通过双层时空调度规划流水线分层开展宏观产能规划与并发订单ctp仿真,对验证可行的订单固化产能占用,完成有限能力排产。

7、上述一种基于线程局部零堆分配回滚栈与时空网格的有限能力排产方法,步骤p1中,将全网所有工作中心在整个计划期内的可用产能编译为物理上完全连续的一维扁平数组,即二维扁平时空产能网格,偏移公式为:

8、;

9、其中,为一维数组的存储下标;为设备唯一标识;为整体计划周期总天数;为单台设备计划区间内的日期偏移量;

10、通过公式(1)计算得到一维数组存储偏移下标,完成二维维度数据扁平化映射。

11、上述一种基于线程局部零堆分配回滚栈与时空网格的有限能力排产方法,步骤p1中,产能数据采用dod排布方式,以使连续日期下的产能数据在硬件缓存行对齐,提升cpu缓存命中效率。

12、上述一种基于线程局部零堆分配回滚栈与时空网格的有限能力排产方法,步骤p2中,在排产线程启动初始阶段,在线程本地存储区域一次性分配固定容量的连续数组作为专属回滚日志存储容器,采用标准化结构体记录对应工作中心逻辑标识、具体计划天数偏移、名义产能数值与换型时间开销。

13、上述一种基于线程局部零堆分配回滚栈与时空网格的有限能力排产方法,步骤p2中,构建配套线程本地调度上下文,包含预分配固定容量的回滚动作数组与整型栈指针,基于栈指针自增在常数时间复杂度内完成产能消耗与换型消耗数据的无锁压栈存储。

14、上述一种基于线程局部零堆分配回滚栈与时空网格的有限能力排产方法,步骤p2中,当路径校验出现冲突时,依据栈指针逆序读取存储容器内记录数据,将对应产能数值回写至扁平时空产能网格完成状态恢复;

15、路径校验通过时执行提交操作,将栈指针直接清零而无需释放底层已分配的物理内存,100%复用已有连续内存空间承载下一轮ctp订单推演,全程无动态堆内存申请与释放,全程依托预先分配的本地数组完成全部日志记录与状态恢复操作。

16、上述一种基于线程局部零堆分配回滚栈与时空网格的有限能力排产方法,步骤p2中,执行产能推演时同步进行换型工时增量计算,具体包括如下步骤:

17、步骤p2-1、在单日设备排产推演过程中插入新订单时,获取该设备当日相邻已排订单对应的产品大类标识;

18、步骤p2-2、比对新订单与前置订单的产品大类标识,检索换型时间矩阵中对应的换模开销,将匹配得到的换型工时与工序运行时间同步扣减至扁平时空产能网格,并同步写入线程本地预分配回滚栈;

19、步骤p2-3、后续计算失败时触发回溯,进行推演路径开展状态恢复操作时,同步将已记录的换型工时与产能消耗一并回补至扁平时空产能网格。

20、上述一种基于线程局部零堆分配回滚栈与时空网格的有限能力排产方法,当新订单与前置订单的产品大类标识相同时,判定本次排产的环形开销为0;当新订单与前置订单的产品大类标识不同时,发生大类切换,将匹配得到的换型工时与工序产能消耗同步扣减至扁平时空产能网格,并同步写入线程本地预分配回滚机制。

21、上述一种基于线程局部零堆分配回滚栈与时空网格的有限能力排产方法,步骤p3中,双层时空调度规划流水线包括战术层与操作执行层;

22、其中,战术层基于共识预测执行软约束冲销与大盘多区域配额分配;

23、操作执行层依托制造工序表与工作中心日历开展硬约束订单物理派工与并发ctp试算;操作执行层输出100%可行方案后回写至战术层更新全局大盘。

24、一种基于线程局部零堆分配回滚栈与时空网格的有限能力排产系统,用于实施上述有限能力排产方法,包括:

25、网格矩阵构建模块,用于构建存储设备周期产能的扁平时空产能网格和存储产品切换耗时的扁平换型时间矩阵;

26、线程回滚推演模块,用于依托线程局部零堆分配回滚栈机制记录产能与换型消耗,并在推演路径冲突时快速回退产能状态,以避免产生堆内存动态申请;

27、双层调度仿真模块,用于通过双层时空调度规划流水线分层开展宏观产能规划与并发订单ctp仿真,对验证可行的订单固化产能占用,完成有限能力排产。

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

29、本发明采用线程局部预分配内存回滚机制,规避了传统dfs回溯排产过程中频繁的动态内存申请与释放系统调用,大幅降低内核调度开销。经实测,单订单ctp有限能力求解耗时由15ms降至0.1ms以内,单服务器可稳定支撑每秒万级并发询单响应,显著提升高频订单承诺场景的实时计算性能。

30、本发明依托线程局部独立回滚栈与多沙箱物理隔离,各线程ctp仿真推演独立运行于专属内存空间,全程无线程锁竞争开销,有效规避多线程并发死锁风险,多核并行计算加速比接近100%,大幅提升多订单并行排产的并发稳定性与算力利用率。

31、本发明将顺序依赖换型矩阵计算与零堆回滚栈机制深度耦合,使工序换型工时的占用、记录、回溯还原均实现o(1)常数级时间复杂度,有效解决了传统离散制造排产因换型组合爆炸导致的计算量大、回溯效率低的技术问题,大幅提升了复杂换型场景下的排产收敛能力。