明经CAD社区

 找回密码
 注册

扫一扫,访问微社区

QQ登录

只需一步,快速开始

查看: 455|回复: 9

[讨论] 一维下料

[复制链接]
发表于 2019-11-11 17:00 | 显示全部楼层 |阅读模式
本帖最后由 mahuan1279 于 2019-11-11 19:21 编辑



单一原材料长为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)即为需要原材料的根数。

评分

参与人数 1明经币 +1 收起 理由
USER2128 + 1 赞一个!

查看全部评分

 楼主| 发表于 2019-11-11 17:01 | 显示全部楼层
_$ (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))
_$

评分

参与人数 1明经币 +1 收起 理由
USER2128 + 1 很给力!

查看全部评分

发表于 2019-11-11 21:30 | 显示全部楼层
网上搜了下
一维下料算法的文章一大堆
光看标题就头疼
更别说点进去阅读了


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


 楼主| 发表于 2019-11-11 22:15 | 显示全部楼层
masterlong 发表于 2019-11-11 21:30
网上搜了下
一维下料算法的文章一大堆
光看标题就头疼

条条大路通罗马。
 楼主| 发表于 2019-11-11 22:31 | 显示全部楼层
动态规划方程。
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
发表于 2019-11-12 08:18 | 显示全部楼层
大哥,你有点专注啊,之前看你的帖子都是坚持不懈,值得学习
发表于 2019-11-12 09:28 | 显示全部楼层
以前在管道行业也讨论过这个问题,理论上看起来似乎不错,但实际上无法实施,或者说无法大规模实施,主要原因的这个就需要一个非常庞大的库管系统,对于每一段料都能及时入库储存和定位出库,如果材料太多,数以千计、万计、十万计,大大提高了库管的要求,这个不大现实。只有在很小范围内才能实施。
当然对软件上来说,还是不错。
 楼主| 发表于 2019-11-12 20:05 | 显示全部楼层
本帖最后由 mahuan1279 于 2019-11-12 20:06 编辑
mikewolf2k 发表于 2019-11-12 09:28
以前在管道行业也讨论过这个问题,理论上看起来似乎不错,但实际上无法实施,或者说无法大规模实施,主要原 ...

只是想找出组合比较接近L的那些“较好的”组合,不用全排列所有组合方式。
随机运行N次(比如100次),大部分较好的组合情况都可能出现。剩下就是怎么挑选的问题了。
发表于 2019-11-13 11:20 | 显示全部楼层
会不会影响速度
 楼主| 发表于 2019-11-13 11:30 | 显示全部楼层
本帖最后由 mahuan1279 于 2019-11-13 11:47 编辑

一语中的。一组一组的取,效率太低了,可以先找出10组较好组合(含重复的情况。运气不好的话,可能10种为同一组合),挑选出一些组合,再分配一些系数,使得长度长的尽快先减少且减少的数量较多,更新li/ni……似乎可以加快些运算。
您需要登录后才可以回帖 登录 | 注册

本版积分规则

小黑屋|手机版|CAD论坛|CAD教程|CAD下载|联系我们|关于明经|明经通道 ( 粤ICP备05003914号  
©2000-2020 明经通道 版权所有 本站代码,在未取得本站及作者授权的情况下,不得用于商业用途

GMT+8, 2020-4-5 13:55 , Processed in 0.934937 second(s), 32 queries , Gzip On.

Powered by Discuz! X3.3

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表