前一阵有个微信朋友发了一个需求,是关于卷膜分切组合的,感觉挺有意思,就进行了算法设计与实现。结果不错。
感觉这是一类问题,就拿出来介绍一下。
有类似需求欢迎联系,深入讨论。
1、问题背景需求
客户订制化一批卷膜,具体内容如示例中客户需求,车间配备设备为生产宽度为2280mm-2500mm、4150-4300mm。
本问题的核心在于根据客户定制化订单计算最优的组合方案,分切后的小卷数量与宽幅需和客户要求相匹配。同时,需要尽量能够利用生产宽度。
场景1:12种尺寸卷膜,共计71卷(客户要求),面向2280mm-2500mm(事先定好)。
尺寸
|
卷数
|
尺寸
|
卷数
|
尺寸
|
卷数
|
490
|
9
|
610
|
27
|
750
|
18
|
510
|
9
|
630
|
27
|
770
|
18
|
530
|
9
|
650
|
9
|
830
|
9
|
550
|
27
|
670
|
27
|
990
|
9
|
570
|
9
|
710
|
18
|
||
590
|
27
|
730
|
9
|
2、求解
假如不考虑优化目标即组合方案数越少越优的情况下,组合方案多达上千万种,从时间复杂度上考量该问题无法直接建立数学模型求解,因而使用智能算法开发了一整套系统能够在计算机求解能力下进行智能自适应搜索,求得最优方案。
首先系统能够以Excel的形式集成导入卷膜尺寸及数量数据,而后根据加工时间的紧迫程度自适应定义搜索的范围,搜索范围越大,耗费时间越长,而后一键点击便可自动生成最优(或者可选的N种最优方案,以供选择)。
场景一:
针对给出的第一种应用场景(2280-2500mm)案例,运行结果如下,黄色填充区域为自动生成的方案,生成时间为3-4秒,白色无填充区域为文档给定的原有方案,总搜索规模为1500次:
方案一
|
|
[550, 550, 590, 590, 610, 630, 750]
|
13
|
[670, 670, 670, 710, 710, 770]
|
9
|
[610, 610, 630, 630, 770, 490, 510]
|
7
|
[530, 570, 650, 730, 830, 990]
|
9
|
[750, 750, 750, 750, 750, 490]
|
1
|
[770, 770, 490, 510, 510, 550, 590]
|
1
|
6种
|
|
用时10min
|
3、结论与后续扩展
本文只是对组合分切这种场景的优化进行了实践。但是对于组合分切车间的排产,其实不仅仅是指定机台下的某个场景进行组合优化,还涉及到整个滚动任务下的多机台的优化乃至动态的分配。对于车间来说,这其实是一种双层APS。机台分配APS比较成熟,我这边都有现成的,但在这个过程中需要融合确定场景下的组合优化,才能真正的落实机台分配。这方面的整合已经在进行中,可以快速定制形成一套针对这一类组合分切车间的APS。