V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
ahaxzh
V2EX  ›  算法

想咨询一个生产排产算法问题

  •  
  •   ahaxzh · 2021-05-27 11:36:03 +08:00 · 645 次点击
    这是一个创建于 1037 天前的主题,其中的信息可能已经有所发展或是发生改变。

    1 、有一卷无限长的布匹,布宽约 5.55 米(我们且称为原始布 X )。

    2 、根据客人的订单,需要将这 5.55 米宽的布匹分成宽度各异的小的布匹卷( y1 、y2 、y3.....,相加小于等于 5.55 米)。

    3 、每个小卷的宽度( Yi )是订单中给定的,每个小卷的长度是固定的 150 米。

    4 、切割布匹需要使用多把机械剪刀,比如根据订单

    可以将 5.55 米的原始布 X 分成 1.2 米、1.2 米、1.5 米、1.55 米、0.1 米(损耗),
    
    这样会同时布置四把机械剪刀,但更换剪刀间距(或者增加、取下)需要一定的成本δ,所以尽可能在少换刀的情况下对 原始布 X 进行剪裁。
    

    5 、如果订单的小布匹卷相加起来宽度小于 5.55 米,可以搭配切一些比较好卖的小布匹卷 Ui (如 1.5 米宽、1.2 米宽等)。

    6 、在此基础上如何最节约不浪费的剪裁布料。

    输入: X(原始布的宽度)

    Yi*n (订单中小布卷的宽度 以及 每种宽度需求数量 n )

    Ui (搭配裁剪的小布卷)

    输出就是裁剪的方案组别。

    值得注意的事情,“5.55 米的原始布 X 分成 1.2 米、1.2 米、1.5 米、1.55 米、0.1 米(损耗)”,这里是需要 4 把机械剪刀的!而不是三把~

    最初我拿到这个之后第一反应是能做,使用多重动态规划就行了,可是我发现根本没有那么简单,真实案例中还涉及到布匹的厚度,原始布的总长度等奇形怪状的因素。

    如果实在不行可以先忽略换刀的情况。

    2 条回复    2021-05-29 13:11:45 +08:00
    sillydaddy
        1
    sillydaddy  
       2021-05-28 12:46:10 +08:00
    > Ui (搭配裁剪的小布卷)

    Ui 的含义不明确,下标 i 代表什么?每个 Yi 对应一个 Ui ?按我的理解

    输入
    X (原始布的宽度)
    Yi*Ni,i∈[0, m] (订单中小布卷的宽度种类共有 m 中,宽度为 Yi,该宽度需求数量为 Ni )
    Uj,j∈[1, n](搭配裁剪的小布卷的宽度种类有 n 种,Uj 为小布卷宽度)

    是这样理解吗?

    有个问题,用于搭配的小布卷,如果种类多于一个,需要怎样搭配呢?比如最后一段 150 米长的布匹,剩余布料宽为 4 米,那可以制作搭配的小布卷:2 个 1.5 米的,或者 3 个 1.2 米的,怎么选择呢?选布料浪费最少的吗?
    ahaxzh
        2
    ahaxzh  
    OP
       2021-05-29 13:11:45 +08:00
    @sillydaddy 是的,可以这么理解。
    关于 Ui,是给定的一组比较好卖的布的宽度,如你所说 1.2 、1.5 这种。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2749 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 12:48 · PVG 20:48 · LAX 05:48 · JFK 08:48
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.