摘要:排产引擎背景与挑战 对于任何一家制造业公司来说,生产计划的合理安排都是核心中的核心。尤其对于华为这样产业涉及面广,销售地区覆盖全球的公司来说,如何合理利用手中的资源进行生产以实现利润最大化更是急需解决的难题。 华为公司于03年以来采购了I2的APS
排产引擎背景与挑战对于任何一家制造业公司来说,生产计划的合理安排都是核心中的核心。尤其对于华为这样产业涉及面广,销售地区覆盖全球的公司来说,如何合理利用手中的资源进行生产以实现利润最大化更是急需解决的难题。 华为公司于03年以来采购了I2的APS软件包作为工厂的排产引擎,支撑公司每日的生产计划决策。但随着近年来公司业务的体量与形态不断扩展,原软件包的功能已远远无法支撑日益复杂的业务场景。更有甚者,今年公司受到美国限制令不断施压,对生产计划优化与自研排产引擎的需求更加迫切。 从技术分类上说,排产问题有计划和调度两种类型,通常计划问题是指决定工厂每日生产量,即粗粒度的定量决策;调度问题是指每日工厂内生产流程的优化,即细粒度上的定序问题(如常见的Job-shop、Flow-shop、Open-shop等类型问题),其对比如表1所示。通常计划问题虽然是更复杂的定量的问题,但对象粒度大、额外约束少;调度问题虽然涉及更细粒度和更复杂的制造约束限制,但只需决策加工对象在不同机器之间的顺序。或许由于计划问题的形式简单,学界主要研究热点集中在调度问题上,对计划问题的探究很少。 表1 生产计划与调度问题对比
华为的排产问题是需要定量的生产计划问题,但由于涉及数十万元器件在上百家工厂在未来3个月以上每日的生产量、转运与制造方案等决策,并且包含了大量制造工艺约束要求,其规模和复杂度远超一般的生产计划问题,相当于大规模生产调度问题的定量求解。进一步统计发现,该问题包含了上亿规模的原始决策变量,搜索空间更是接近天文数字(大于10的10,000,000次方),并且其中大量业务约束由业务性语言构成,难以转化为数学语言。一言以蔽之,其问题规模和复杂度远远超过所有可见的排产问题。
排产引擎算法设计华为诺亚方舟实验室攻关小组深入一线了解业务需求,经过长达一年的预研、试错与迭代,最终设计并开发出一套符合业务要求的模型、算法,并最终构建成新的排产引擎。 如果将全部需求转化成数学模型,这将是一个非线性的MIP问题,显然在华为公司的问题规模体量上,此问题不可能解得动。对此,我们设计了一种“时空分层迭代”的fix-and-optimize类型算法,对该问题进行高效的“几乎最优解”逼近: 首先,我们将原问题简化成LP问题并基于问题结构进行了定制化的约束松弛,从而得到一个可以较快求解的松弛LP问题;继而求解这个松弛LP问题可以得到对原问题最优解的形态判断,据此对原问题模型进行修正,其中包括但不限于在目标中添加将决策变量向整数牵引的部分、以及对决策空间的进一步化简,从而得到一个优化后的LP模型。整个过程如上图1中Stage1所示。 继而优化后的模型将通过LP求解器进行求解,进而得到一个对原问题而言近似可行的最优解;该解通过定制的启发式算法进行局部修正,得到一个在原问题局部可行的近似最优解;此时我们同样得到了对原问题最优解形态的进一步判断,可以基于其中信息,固定部分核心变量的取值并进行模型的修正化简;重新使用LP求解器求解这个修正后的模型并循环迭代上述过程,直至全部核心决策变量符合原问题的约束要求;最后通过固定核心决策变量求解原问题,得到原问题的一个几乎最优的可行解。上述过程如上图1中Stage2所示。 根据这类计划问题特有的结构,并经过反复调试与超参优化,大约50轮LP求解与修正的迭代后,可以在3h内得到兼顾求解速度和解的质量的“几乎最优解”。后续我们还增加了各种辅助业务理解与操作的可解释性模块,包括但不限于:①每日排产情况仿真模块——方便业务了解基于我们建议结果的未来生产、转运、交付与库存情况;②供需匹配详情模块——可以支持业务追溯每一条任务令的开工原因以及每一笔原材料的具体用途;③延期原因分析模块——用于输出需求被延期交付的原因,并分析具体的产能、物料等瓶颈以支撑业务快速反应决策。
排产引擎效果对比经过多轮生产数据验证,对比竞品算法方案(同样使用Gurobi求解器上线),我们不仅严格保证了最难的整数批量需求,并且在求解速度上有显著的优势(如下图3所示,Riemann为基于自研算法的排产引擎),同时我们自研引擎的各项设计指标均达到业务需求,最终在20年初作为首选的正式引擎在全产品上线使用。20年自研引擎实际使用率99%(1%为备份的竞品引擎),不仅有效支撑了业务每日工作正常开展,提升效率30%,更通过提高需求满足率、提高库存周转等效果,实现财经核算年收益1亿 RMB。 图3 排产引擎批量约束与求解速度对比
排产引擎延伸--------- END ----------
|
- 上一篇:PPT讲透供应链管理中生产计划与库存管理
- 下一篇:没有了
谈谈您对该文章的看