一维下料

mahuan1279

单一原材料长为L，要获得各种零件长度/数量为l1/n1,l2/n2,……li/ni,至少要多少根原材料？如何下料？ 算法如下 1、按如下组成初始lst    l1/min(n1,L/l1)    l2/min(n2,L/l2)    ……    li/min(ni,L/li)；   nlst=(n1,n2,n3……ni)   vlst=nil 2、随机排列lst，然后(H_L  lst   L)，即随机选取一组接近L的组合,vlst=(cons  (list (H_L  lst   L))  vlst) ； 3、更新nlst; 4、转到1; 5、nlst都为0，结束。vlst 即为裁料方式。（lenth  vlst）即为需要原材料的根数。

mahuan1279

_$ (defun rnd ()
  (*(rem (getvar "cputicks") 1e4) 1e-4)
)
(defun rnd_n (n)
  (fix (* n (rnd)))
)
(defun pick (lst i j)
   (setq count (length lst) nc 0 picklst nil)
   (while (<= nc j)
       (if (<= i nc)
           (setq picklst (cons (nth nc lst) picklst))
       )
      (setq nc (+ nc 1))
   )   
   (reverse picklst)
)
(defun xipai (n)
  (setq i 1 j 0 klst nil)
  (while (<= i n)
      (setq klst (cons i klst))
      (setq i (+ 1 i))
   )
   (while (<= j 20)
         (setq i_pot (rnd_n n))
         (setq j_pot (rnd_n n))
         (setq nmin (min i_pot j_pot))
         (setq nmax (max i_pot j_pot))
         (setq klst (append (pick klst  (+ 1 nmax) (- n 1)) (pick klst (+ 1 nmin) nmax) (pick klst 0 nmin)))
         (setq j (+ j 1))
   )
   klst
)
(defun H_L (lst L)
  (setq lst1 (mapcar '(lambda (x y)   
                         (progn
                            (list (if (> (+ x y) L) x (+ x y))
                                  y   
                                 (if  (> (+ x y) L)
                                                                          (list x)
                                                                          (list  x y)
                                  )
                            )
                         )        
                      )
                      (reverse (cdr (reverse lst)))
                      (cdr lst)
               )
   )
  (while (cdr lst1)
       (setq lst1 (mapcar '(lambda (x y)   
                              (if (> (+ (car x) (cadr y)) L)
                                                              (if (>= (car x)  (car y))
                                                                       (list
                                                                                (car x)
                                                                                (cadr y)
                                                                                (last x)
                                                                           )
                                                                                                                                                   y
                                                                  )
                                                                  (if (> (+ (car x) (cadr y)) (car y))
                                                                       (list
                                                                                (+ (car x) (cadr y))
                                                                                (cadr y)
                                                                                (cons (cadr y) (last x))
                                                                           )
                                                                           y
                                                                  )
                                                            )
                            )        
                           (reverse (cdr (reverse lst1)))
                           (cdr lst1)
                      )
            )
   )
  (cons (car (car lst1))(list (last (car lst1))))
)
(setq lst '(5.12 5.12 4.73 4.73 3.92 3.92 3.92 3.62 3.62 3.62 3.52 3.52 3.52 3.32 3.32 3.32 3.12 3.12 3.12 2.92 2.92 2.92 2.92 2.64 2.64 2.64 2.64 2.54 2.54 2.54 2.54 2.38 2.38 2.38 2.38 2.38 1.75 1.75 1.75 1.75 1.75 1.75 1.585 1.585 1.585 1.585 1.585 1.585 1.585))
(H_L (mapcar '(lambda (eb) (nth (- eb 1) lst)) (xipai (length lst))) 12)
RND
RND_N
PICK
XIPAI
H_L
(5.12 5.12 4.73 4.73 3.92 3.92 3.92 3.62 3.62 3.62 3.52 3.52 3.52 3.32 3.32 3.32 3.12 3.12 3.12 2.92 2.92 2.92 2.92 2.64 2.64 2.64 2.64 2.54 2.54 2.54 2.54 2.38 2.38 2.38 2.38 2.38 1.75 1.75 1.75 1.75 1.75 1.75 1.585 1.585 1.585 1.585 1.585 1.585 1.585)
(11.97 (4.73 3.62 3.62))
_$ (H_L (mapcar '(lambda (eb) (nth (- eb 1) lst)) (xipai (length lst))) 12)
(11.99 (2.38 1.585 1.585 3.12 3.32))
_$ (H_L (mapcar '(lambda (eb) (nth (- eb 1) lst)) (xipai (length lst))) 12)
(11.97 (3.92 3.92 1.75 2.38))
_$  (H_L (mapcar '(lambda (eb) (nth (- eb 1) lst)) (xipai (length lst))) 12)
(11.985 (2.64 2.64 1.585 5.12))
_$ (H_L (mapcar '(lambda (eb) (nth (- eb 1) lst)) (xipai (length lst))) 12)
(11.99 (3.12 3.62 1.75 1.75 1.75))
_$ (H_L (mapcar '(lambda (eb) (nth (- eb 1) lst)) (xipai (length lst))) 12)
(11.925 (1.585 3.32 1.75 3.52 1.75))
_$ (H_L (mapcar '(lambda (eb) (nth (- eb 1) lst)) (xipai (length lst))) 12)
(11.94 (2.92 2.38 3.12 3.52))
_$ (H_L (mapcar '(lambda (eb) (nth (- eb 1) lst)) (xipai (length lst))) 12)
(11.95 (1.75 2.38 2.64 2.54 2.64))
_$ (H_L (mapcar '(lambda (eb) (nth (- eb 1) lst)) (xipai (length lst))) 12)
(11.95 (1.585 2.54 1.585 3.12 3.12))
_$ (H_L (mapcar '(lambda (eb) (nth (- eb 1) lst)) (xipai (length lst))) 12)
(11.99 (1.75 5.12 5.12))
_$ (H_L (mapcar '(lambda (eb) (nth (- eb 1) lst)) (xipai (length lst))) 12)
(11.96 (1.75 1.585 3.92 1.585 3.12))
_$ (H_L (mapcar '(lambda (eb) (nth (- eb 1) lst)) (xipai (length lst))) 12)
(11.985 (1.75 4.73 1.585 3.92))
_$ (H_L (mapcar '(lambda (eb) (nth (- eb 1) lst)) (xipai (length lst))) 12)
(11.97 (4.73 3.62 3.62))
_$ (H_L (mapcar '(lambda (eb) (nth (- eb 1) lst)) (xipai (length lst))) 12)
(12.0 (2.54 3.62 2.92 2.92))
_$ (H_L (mapcar '(lambda (eb) (nth (- eb 1) lst)) (xipai (length lst))) 12)
(11.965 (1.585 3.92 2.54 3.92))
_$ (H_L (mapcar '(lambda (eb) (nth (- eb 1) lst)) (xipai (length lst))) 12)
(11.985 (4.73 3.92 1.585 1.75))
_$ (H_L (mapcar '(lambda (eb) (nth (- eb 1) lst)) (xipai (length lst))) 12)
(11.985 (2.64 2.64 1.585 5.12))
_$

masterlong

网上搜了下
一维下料算法的文章一大堆
光看标题就头疼
更别说点进去阅读了


一维下料问题的自适应广义粒子群优化求解
一维下料问题的AB分类法
基于蜂群遗传算法的一维优化下料问题
一维下料问题的启发式方法
等等等等

mahuan1279

masterlong 发表于 2019-11-11 21:30
网上搜了下
一维下料算法的文章一大堆
光看标题就头疼

条条大路通罗马。

mahuan1279

动态规划方程。
F（L，（l1,n1）,（l2,n2）,（l3,n3）……（lk,nk））=0,(if  0=l1*n1+l2*n2+……lk*nk)
F（L，（l1,n1）,（l2,n2）,（l3,n3）……（lk,nk））=1,(if  0<l1*n1+l2*n2+……lk*nk<=L)
F（L，（l1,n1）,（l2,n2）,（l3,n3）……（lk,nk））=1+min{F（L，（l1,n1-i1）,（l2,n2-i2）,（l3,n3-i3）……（lk,nk-ik））},( l1*i1+l2*i2+……lk*ik<=L)
i1、i2、i3、……ik>=0

pengfei2010

大哥，你有点专注啊，之前看你的帖子都是坚持不懈，值得学习

mikewolf2k

以前在管道行业也讨论过这个问题，理论上看起来似乎不错，但实际上无法实施，或者说无法大规模实施，主要原因的这个就需要一个非常庞大的库管系统，对于每一段料都能及时入库储存和定位出库，如果材料太多，数以千计、万计、十万计，大大提高了库管的要求，这个不大现实。只有在很小范围内才能实施。
当然对软件上来说，还是不错。

mahuan1279

mikewolf2k 发表于 2019-11-12 09:28
以前在管道行业也讨论过这个问题，理论上看起来似乎不错，但实际上无法实施，或者说无法大规模实施，主要原 ...

只是想找出组合比较接近L的那些“较好的”组合，不用全排列所有组合方式。
随机运行N次（比如100次），大部分较好的组合情况都可能出现。剩下就是怎么挑选的问题了。

cable2004

会不会影响速度

mahuan1279

cable2004 发表于 2019-11-13 11:20
会不会影响速度

一语中的。一组一组的取，效率太低了，可以先找出10组较好组合（含重复的情况。运气不好的话，可能10种为同一组合），挑选出一些组合，再分配一些系数，使得长度长的尽快先减少且减少的数量较多，更新li/ni……似乎可以加快些运算。