Topic: Smart list for cutting order.

[Amsterdammed]

Lets say i have a list of pipes to cut with certain lengths (in metric but that doesn't mather)
And i have lengths of pipes (like 20ft each, lets say).

What i want is to cut my pipes as efficient as possible.

I know it is "only Math" (At least i hope). But since i don't want to invent the wheel again I wonder if somebody else already did.

Thanks in Advance,

Bernd

[t-bear]

What you're looking for is a nesting routine that will take all the cut lengths from a dwg. and sort them into 20 ft. sets, right?  Sounds interesting, and no, I don't have anything.  Would be handy though..........  CADaver does a lot of piping..........you got anything like this Randy?

[David Hall]

seems like to me, you would want to sort the 'length's by longest to shortest, then starting with the largest, check against a list of pipes. that way you could get maximum usage out of each piece.  Does that make sense?

[Amsterdammed]

I have de cutting lengths from a BOM  I already made. Some of them are multiple.

It is not as easy ad starting with the longest and add the shortest one  to max it.

 The problem in my opinion is (and than I lost my English, I guess the math term is ??  ) that it is like a the math Q at School, you have 5 kids , so how many different ways are there to arrange their chairs?

That was 5!, or 5*4*3*2 = 120 (Really no Idea what this is called in English). So; since I have easily a few hundred pipes in a dwg this could be some processing time, but, there is night time and computer never sleep, so what?

Bernd

[David Hall]

1 - I think its called factorial

2  - I think it could be sorted very quickly by a computer, then computed by length.  I will see if I can make a test program

[Amsterdammed]

Thanks,

In my mother thong it is called "Facturelle", so i believe your explanation is right.  Looking forward to your testprogram.

Bernd :

[t-bear]

Me too.....don't have THAT many cuts but the train drivers would sure like it.  (like I should make life easy for THEM!)  LOL 

Bernd...not meant as a put-down but the spelling in English is: mother "tongue".  I speak and write it all the time (sort of) and that word just never looks right to me......
It wouldn't have helped to use the spell checker either...thong is a type of sandal or shoe...also a very skimpy style of underwear..........  Hope this is helpful, no offense intended, my friend.

[Amsterdammed]

Bear,

 don't worry, as an Austrian(German language),  living in The Netherlands (Dutch), dealing with English still for my crazy Floridian girlfriend and the swamp, every help in spelling is more than welcome.  BTW, I knew the word, but at this time here;  11pm; and my evening wine already drowned, i relied on the spell check.

Thanks Bernd

[T.Willey]

See if this works for you.

Code: [Select]

(defun CutPipes (PipeLng LngList / tmpList LeftOver cnt tmpLng EndList NumList tmpNum)

(setq tmpList (vl-sort LngList '>))
(setq LeftOver PipeLng)
(setq cnt 1)
(while (setq tmpLng (car tmpList))
 (setq tmpNum nil)
 (setq tmpList (cdr tmpList))
 (setq LeftOver (- LeftOver tmpLng))
 (if (< LeftOver 0.0)
  (progn
   (setq LeftOver (- PipeLng tmpLng))
   (setq EndList (cons (cons  cnt (list NumList)) EndList))
   (setq NumList (list tmpLng))
   (setq cnt (1+ cnt))
  )
  (setq NumList (cons tmpLng NumList))
 )
 (if (vl-position LeftOver tmpList)
  (progn
   (setq tmpList (RemoveItem LeftOver tmpList))
   (setq NumList (cons LeftOver NumList))
  )
  (while (> (setq tmpNum (if tmpNum (1- tmpNum) (1- LeftOver))) 0.0)
   (if (vl-position tmpNum tmpList)
    (progn
     (setq tmpList (RemoveItem tmpNum tmpList))
     (setq NumList (cons tmpNum NumList))
    )
   )
  )
 )
)
(cons (cons cnt (list NumList)) EndList)
)
;---------------------------------------------------------------
(defun RemoveItem (Item Lst)

(append
 (ListUntil Item Lst)
 (cdr (member Item Lst))
)
)
;---------------------------------------------------------------
(defun ListUntil (Item Lst / tmpList)
; Return the list from beginning to Item list.
; ie. (ListUntil 1 '(0 2 1 5 6 3)) = (0 2)

(vl-catch-all-error-p
 (vl-catch-all-apply
  '(lambda ()
   (foreach i Lst
    (if
     (
      (if (= (type Item) 'STR)
       =
       equal
      )
      i
      Item
     )
     (exit)
     (setq tmpList (cons i tmpList))
    )
   )
  )
 )
)
(reverse tmpList)
)


Code: [Select]

Command: (cutpipes 10 '(1 5 6 8 3 2))
((3 (5)) (2 (1 3 6)) (1 (2 8)))


[David Bethel]

Nesting routine can be very very intense

Are the pipes exactly 240" long
Do you need to take ito consideration the cutting blade thickness
Do you want the drops to be the best average or longest and shortist possible.

Or is it okay if the total number of lengths are met and drops don't matter.


Here's a very crued hack at it:

Code: [Select]


;;;SORT BY STEVE JOHNSON
(defun qsort (LST FUN / sort subnth)
  (defun sort (L R / i j x loop)
    (setq i L
          j R
          x (nth (/ (+ L R) 2) LST)
          loop T)
    (while loop
      (while (apply FUN (list (nth i LST) x))
             (setq i (1+ i)))
      (while (apply FUN (list x (nth j LST)))
             (setq j (1- j)))
      (if (<= i j)
          (setq LST (subnth (nth i LST) j (subnth (nth j LST) i LST))
                  i (1+ i)
                  j (1- j)))
      (setq loop (<= i j)))
    (if (< L j) (sort L j))
    (if (< i R) (sort i R)))

  (defun subnth (ITEM N LST / # tlst)
    (setq # 0)
    (while (and LST (/= # N))
      (setq tlst (cons (car LST) tlst)
             LST (cdr LST)
               # (1+ #)))
    (append (reverse tlst) (list ITEM) (cdr LST)))

  (sort 0 (1- (length LST)))
   LST)


(defun c:nestp (/ pl in il tl pq pc sl c tmp cl)

;  (*-debug-* 9 "c:nestp")

   (initget 6)
   (setq pl (getdist "\n Pipe Length <240>:   "))
   (if (not pl)
       (setq pl 240))

;|
   (while (setq in (getdist "\n Enter Each Length To Cut:   "))
          (setq il (cons in il)))
|;
   (setq il '(144 35 23 86 99 12 230 12 12 14 132 189 6 3 99))

   (setq tl (apply '+ il))
   (setq pq (/ (float tl) pl))
   (setq pc (if (zerop (rem pq 1)) pq (1+ (fix pq))))
   (setq c 1)

   (setq sl (qsort il '>))
   (while sl
     (setq cl (list (car sl))
           tmp (car sl)
           sl (cdr sl))
     (while (and sl
                 (<= (last sl) (- pl tmp)))
            (setq tmp (+ (last sl) tmp)
                   cl (cons (last sl) cl)
                   sl (reverse (cdr (reverse sl)))))
     (set (read (strcat "CL" (itoa c))) cl)
     (setq cl nil c (1+ c)))

; (*break*)

  (textpage)
  (princ (strcat "\n Lengths Used = " (itoa (1- c))
                 "\n Total Cut Length = " (rtos tl 2 2)
                 "\n Total Pipe Length = " (rtos (* (1- c) pl) 2 2)
                 "\n Efficency = " (rtos (/ (* pc pl) (* (1- c) pl)) 2 4)
                 "\n Minimum Lengths " (itoa pc)
                 "\n Cut Lists:\n"))

  (setq c 1)
  (while (boundp (read (strcat "CL" (itoa c))))
         (princ "\n")
         (prin1 (eval (read (strcat "CL" (itoa c)))))
         (princ " - Drop ")
         (princ (rtos (- pl (apply '+ (eval (read (strcat "CL" (itoa c)))))) 2 2))
         (setq c (1+ c)))

; (*-debug-* 0 "c:nestp")

  (prin1))


-David

[Amsterdammed]

Thanks T., Thanks David.

Tomorrow I'll  try it in the office (it is +6 ET here)

David, i was thinking of adding the cutting loss to the pipe length and go for the minimum pipe length of the supplier's books. Since they are copper pipes,  they are pretty exactly  3600 or 6000 mm, depends

Thanks a lot,
Bernd

[Amsterdammed]

David,


It works, but I doubt that the cutting order is the best solution Because it gathers all the short pieces first, there are large drops on the end. But it is a certain way to go on with. I will try do modify it. But I have to do some other stuff first.

Thanks

Bernd

[David Bethel]

Bernd,

The main primism for a routine like this is that if the drop from longest piece needed  is smaller than the shortest length needed, you have yo use an entire length of pipe no matter what.

So a next step could be to make maximum number of cuts from each drop based on the shortest. Which is what I did.

Another would be to use the longest length that could come out of the drop and then delete that atom from the list.

A true maximizing routine would compare all of the possible scenarios against each other.  But it needs some very detailed rules to follow.

Recursion routines like this can be very CPU intensive.  And also very hard to code.

Anyway, mine was a kludge but it worked.  -David

[CAB]

Here is my attempt.
<Caution: Very little testing>

Code: [Select]

;;  CAB 03-10-06
(defun get_cutlist (lst maxlen / cutlst itm lst ptr tl x finallst remove-at)
  (defun remove-at (lst pos / head) ; Tony Tanzillo
    (repeat pos
      (setq head (cons (car lst) head)
            lst  (cdr lst)
      )
    )
    (append (reverse head) (cdr lst))
  )

  (setq lst (mapcar '(lambda (x) (nth x lst)) (vl-sort-i lst '>)))
  ;;  step through lst
  (while lst
    (setq cutlst (list (car lst)) ; start new cutlist w/ first item
          lst    (cdr lst) ; remove first item
          ptr    (1- (length lst)) ; point to end of list
          tl     (apply '+ cutlst) ; total length so far
    )

    ;; build the cutlst
    (while (and lst cutlst)
      ;; find largest next cut
      ;; exit conditions ptr < 0 or itm length exceeds max
      (while (and (< (+ tl (setq itm (nth ptr lst))) maxlen)
                  (> ptr 0))
        (setq ptr (1- ptr))
      )

      (if (> ptr -1)
        (if (= ptr (1- (length lst)))
          ;;  no more cuts fit, go to next
          (setq finallst (cons cutlst finallst)
                cutlst   nil
          )
          (setq cutlst (cons (nth (1+ ptr) lst) cutlst)
                lst    (remove-at lst (1+ ptr))
                tl     (apply '+ cutlst) ; new total

          )
        )
        ;; else exausted pointer
        (setq finallst (cons cutlst finallst)
              cutlst   nil
        )
      ) ; endif
    ) ; while
  ) ; while
  (if cutlst
    (cons cutlst finallst)
    finallst
  )
)

Code: [Select]

(defun c:test(/ lst maxlen)
  (setq lst '(144 35 23 86 99 12 230 12 12 14 132 189 6 3 99))
  (setq maxlen 240.0)
  (get_cutlist lst maxlen)
 )

Code: [Select]

Command: test
((99) (99 132) (86 144) (12 12 12 14 23 35 189) (3 6 230))

[hornet 103]

hello
just putting in half penny worth
I have a excel spreadsheet which cuts flat timber panels, this sorts out the different sizes you can cut from an 8x4 sheet (24cm x 12cm)
from a type in list.
If you are interested i will dig it out

hornet 103

[Amsterdammed]

David,

I'm totally with you in this point. Your routine works and is for sure better than leaving the case over to the guy on the saw to decide what to cut first.

What I was thinking is for sure very CPU challenging but as I said, Computers never sleep, so what. But I agree that the scenario with comparing all the different ways to sort the list makes my head spin, so I have no Idea how to get it in a code.

Bernd

[CAB]

Anyway, mine was a kludge but it worked.  -David

If that's a kludge it's a very nice kludge.
Ignoring your lisp to come up with my solution, mine ended up similar but took more code to get there.