未分類
4 4 月 2020

关于工业生产中的一个算法问题

关于工业生产中的一个算法问题

資深大佬 : catshen 15

51 假期回老家，发现家纺行业切割材料的问题，我看了下本质是一个算法问题：

  • 有一个大矩形区域，矩形区域的尺寸规格为：2*N
  • 有若干矩形，尺寸规格不等，注：这些小矩形尺寸规格 a*b，a 和 b 中的有一个值必定在 2 以内
  • 现在将这些小矩形填充到大矩形区域，使得耗用的大矩形区域的面积最少

求解图形化规划方案 即输入若干尺寸小矩形规格，输出规划图形，工人可以根据规划图形划料

目前都是人工排版划料，效率有提升空间～

如能解决，现金感谢～

大佬有話說 (8)

  • 資深大佬 : wtof

    二维装箱问题？记得是个 NP 问题来着，量不大 DLX 搞一下应该也可以吧

  • 資深大佬 : murmur

    这得看你什么样的布了，如果是单色或者是重复花纹还好，如果是复杂印花，有的部分必须浪费因为要显示整个一套图案

  • 主 資深大佬 : catshen

    @murmur 纯色的，所以好弄一些

  • 主 資深大佬 : catshen

    @wtof https://blog.csdn.net/code_long/article/details/81182516 应该就是这个吧

  • 資深大佬 : ccpp132

    虽然 2 维，这个问题的限制倒是比较好搞。把 1xn 的先挑出来。剩下 2xn 的只有一种放法，1xn 的就分两行，尽量相等，相当于一个装一半总大小的 1 维装箱。唯一一个例外是可能多一个 1×2 的旋转一下更好

  • 資深大佬 : CrazyMoon

    造船行业里已经有现成的解决方案了，偶们厂里把这个叫套料，一般是软件自动生成图形，人工辅助。具体算法不清楚。

  • 資深大佬 : CrazyMoon

    主可以查查论文试试

  • 主 資深大佬 : catshen

    @CrazyMoon 谢谢，看来要废不少脑子了