Author Topic: The Cutting Stock Problem (Optimizing Cutting of Rebar or Other Material)  (Read 17435 times)

0 Members and 1 Guest are viewing this topic.

roy_043

  • Water Moccasin
  • Posts: 1895
  • BricsCAD 18
Re: The Cutting Stock Problem (Optimizing Cutting of Rebar or Other Material)
« Reply #30 on: September 18, 2015, 10:35:31 AM »
@ Ymg:

As you have already explained the algorithm of your 1D-CSP function has some issues.

Because the processing occurs in sequence, the largest lengths are handled first, and is geared towards minimizing waste, an early pattern can use up lengths that make later, potentially more frequently used, patterns less efficient. Leading to a final result that is not always optimal.

I have looked at ways to improve the performance of 1D-CSP by changing the way the temporary list is sorted and ultimately have come up with the idea of introducing an 'Allowable Loss Factor' argument. This argument, in conjunction with the 'all' option of your GenPat, can be used to identify patterns with a high 'pattern count' that have a reasonable waste percentage. The processing still occurs step by step, but there no longer is a too strong emphasis on the largest demanded lengths.

The main function Alt-1D-CSP tries out several 'Allowable Loss Factors' and also tries the 'old behavior' of 1D-CSP and an FFD-BinPack solution. The best solution of 13 is returned.

Code - Auto/Visual Lisp: [Select]
  1. (defun Alt-1D-CSP (lenLst demLst stockLen)
  2.   (car
  3.     (vl-sort
  4.       (cons
  5.         (Alt-FFD-BinPack lenLst demLst stockLen)
  6.         (mapcar
  7.           '(lambda (okLossFact allPatP)
  8.             (1D-CSP lenLst demLst stockLen okLossFact allPatP)
  9.           )
  10.           '(0.000 0.000 0.005 0.010 0.015 0.020 0.025 0.030 0.035 0.040 0.045 0.050)
  11.           '(nil   T     T     T     T     T     T     T     T     T     T     T    )
  12.         )
  13.       )
  14.       '(lambda (a b) (< (car a) (car b))) ; Sort using loss factor.
  15.     )
  16.   )
  17. )

The results of Alt-1D-CSP appear to be quite good.

For example the efficiency percentages found for Problems 1a to 5a (EP-Cut.LSP) are identical to those found by your EP-CUT, and those for Problems 6a to 10a are higher. And EP-CUT usually suggests far more different patterns than Alt-1D-CSP.

Another example:
Quote
Problem 2 in post #7:
 Length list: (4.5 3.6 3.1 1.4 0.75)
 Demand list: (97 610 395 211 300)
Stock length: 12.000


Solution from a Commercial Program:
(2 (3.6 1.4 1.4 1.4 1.4 1.4 1.4) 0.0)
(1 (3.1 1.4 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75) 0.0)
(1 (0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75) 0.0)
(197 (3.6 3.1 3.1 1.4 0.75) 0.05)
(97 (4.5 3.6 3.6) 0.3)
(72 (3.6 3.6 3.6 0.75) 0.45)
(1 (3.6 1.4 0.75 0.75 0.75 0.75 0.75) 3.25)

Nb of Stock Used    : 371
Nb of Parts Cut     : 1613
Total Length Wasted : 74.60
Percent Efficiency  : 98.3243 %


Solution from Alt-1D-CSP:
(211 (3.6 3.6 3.1 1.4) 0.3)
(97 (4.5 3.6 3.1 0.75) 0.05)
(45 (3.6 3.6 3.1 0.75 0.75) 0.2)
(14 (3.1 3.1 3.1 0.75 0.75 0.75) 0.45)
(4 (0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75) 0.0)
(1 (3.6 0.75 0.75 0.75 0.75 0.75 0.75 0.75) 3.15)

Nb of Stock Used    : 372
Nb of Parts Cut     : 1613
Total Length Wasted : 86.600
Percent Efficiency  : 98.0600 %

I am attaching the Lisp code. As you will see I have renamed all variables as I find it hard to read code with many very short variable names. I hope you don't mind.

ymg

  • Guest
Re: The Cutting Stock Problem (Optimizing Cutting of Rebar or Other Material)
« Reply #31 on: September 18, 2015, 04:52:42 PM »
roy,

Look good to me, but will try to test it some more.

It sounds like an idea that I never followed which was
simply mixing the order of the pattern once an initial
solution was found.

Quote
As you will see I have renamed all variables as I find it hard to read code with many very short variable names.

I must be (I am  :-D)  old school as in my case me long name for variable mix me up.

On a side note Problems 1a to 4a are somewhat trivial.  Problems 5a to 10a are much
more challenging.

A lower number of patterns is a desirable feature.

Another feature which I have not adressed is the number of currently open lenght.
That is how many different pile of cut rods needs to be accumulated on the shop floor.

ymg

« Last Edit: September 18, 2015, 05:03:32 PM by ymg »

ymg

  • Guest
Re: The Cutting Stock Problem (Optimizing Cutting of Rebar or Other Material)
« Reply #32 on: September 22, 2015, 07:34:21 AM »
Roy,

I've done some testing.  Results are actually quite good,
better than anyhing I had up to now.

Problem 7 however waste 10 meter too much as opposed
to thiese solutions:

Quote
Real Cut 1D
(4   (3.6 1.4 1.4 1.4 1.4 1.4 1.4) 0.0)
(181 (3.6 3.1 3.1 1.4 0.75) 0.05)
(31  (3.6 3.6 3.1 0.75 0.75) 0.2)
(55  (3.6 3.6 3.6 0.75) 0.45)
(97  (4.5 3.6 3.6) 0.3)
(1   (3.1 3.1 0.75 0.75) 4.3)
(2   (3.6 3.6 1.4 1.4 1.4) 0.6)

Nb of Stock used   : 371
Nb of Parts Cut    : 1613
Total Length Wasted: 74.60
Percent Efficiency : 98.3243 %


CutLogic 1D
(2   (3.6 1.4 1.4 1.4 1.4 1.4 1.4) 0.0)
(1   (3.1 1.4 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75) 0.0)
(1   (0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75) 0.0)
(197 (3.6 3.1 3.1 1.4 0.75) 0.05)
(97  (4.5 3.6 3.6) 0.3)
(72  (3.6 3.6 3.6 0.75) 0.45)
(1   (3.6 1.4 0.75 0.75 0.75 0.75 0.75) 3.25)

Nb of Stock used:    371
Nb of Parts Cut    : 1613
Total Length Wasted: 74.60
Percent Efficiency : 98.3243 %

Probably due to the constraint on acceptable waste.

ymg

roy_043

  • Water Moccasin
  • Posts: 1895
  • BricsCAD 18
Re: The Cutting Stock Problem (Optimizing Cutting of Rebar or Other Material)
« Reply #33 on: September 22, 2015, 02:30:51 PM »
Relatively speaking the difference is small: only 0.26%. But there is definitely room for improvement. Where did you get this example and do you perhaps have other tough cases?

ymg

  • Guest
Re: The Cutting Stock Problem (Optimizing Cutting of Rebar or Other Material)
« Reply #34 on: September 22, 2015, 04:06:10 PM »
Roy,

Don't remember where I took this particular example.

Probably read too many papers.

But as a general rule, when all the demanded length are shorter
than 50% of the stock lenght, the problem tend to be difficult.

Another goal is to try to concentrate most of the loss in a single
pattern.  A case can be made that this can be reused in another
order.

ymg

roy_043

  • Water Moccasin
  • Posts: 1895
  • BricsCAD 18
Re: The Cutting Stock Problem (Optimizing Cutting of Rebar or Other Material)
« Reply #35 on: September 29, 2015, 03:04:09 PM »
I am still toying with this... :-)

I have discovered a problem with the genpat function. Fixed code below.

Test with old code:
Code: [Select]
(GenPat '(4.50 3.60 3.10 1.40 0.75) '(0 2 0 2 0) 12.0 nil)
=> ((0 2 0 2 0) (0 2 0 1 0) (0 2 0 0 0) (0 1 0 2 0) (0 1 0 1 0) (0 1 0 0 0))
(GenPat '(4.50 3.60 3.10 1.40 0.75) '(0 2 0 0 2) 12.0 nil)
=> ((0 2 0 0 2) (0 1 0 0 2))
(GenPat '(4.50 3.60 3.10 1.40 0.75) '(0 2 0 2 0) 12.0 T)
=> ((0 2 0 2 0) (0 2 0 1 0) (0 2 0 0 0) (0 1 0 2 0) (0 1 0 1 0) (0 1 0 0 0) (0 0 0 2 0) (0 0 0 1 0) (0 0 0 0 0))
(GenPat '(4.50 3.60 3.10 1.40 0.75) '(0 2 0 0 2) 12.0 T)
=> ((0 2 0 0 2) (0 1 0 0 2) (0 0 0 0 2))

Test with new code:
Code: [Select]
(GenPat '(4.50 3.60 3.10 1.40 0.75) '(0 2 0 2 0) 12.0 nil)
=> ((0 2 0 2 0) (0 2 0 1 0) (0 2 0 0 0) (0 1 0 2 0) (0 1 0 1 0) (0 1 0 0 0))
(GenPat '(4.50 3.60 3.10 1.40 0.75) '(0 2 0 0 2) 12.0 nil)
=> ((0 2 0 0 2) (0 2 0 0 1) (0 2 0 0 0) (0 1 0 0 2) (0 1 0 0 1) (0 1 0 0 0))
(GenPat '(4.50 3.60 3.10 1.40 0.75) '(0 2 0 2 0) 12.0 T)
=> ((0 2 0 2 0) (0 2 0 1 0) (0 2 0 0 0) (0 1 0 2 0) (0 1 0 1 0) (0 1 0 0 0) (0 0 0 2 0) (0 0 0 1 0))
(GenPat '(4.50 3.60 3.10 1.40 0.75) '(0 2 0 0 2) 12.0 T)
=> ((0 2 0 0 2) (0 2 0 0 1) (0 2 0 0 0) (0 1 0 0 2) (0 1 0 0 1) (0 1 0 0 0) (0 0 0 0 2) (0 0 0 0 1))

Code - Auto/Visual Lisp: [Select]
  1. ;; 20150929: Fixed by Roy.
  2. ;; 20150918: Very minor changes by Roy.
  3. ;; GenPat                    (By Ymg)                                         ;
  4. ;;                                                                            ;
  5. ;; http://www.theswamp.org/index.php?topic=48889.0                            ;
  6. ;;                                                                            ;
  7. ;; Procedure for Generating the Efficient Feasible Cutting Patterns           ;
  8. ;; http://www.cs.bham.ac.uk/~wbl/biblio/gecco2006/docs/p1675.pdf              ;
  9. ;; Appendix 1                                                                 ;
  10. ;; Part of "Cutting Stock Waste Reduction Using Genetic Algorithms"           ;
  11. ;;              by Y. Khalifa, O. Salem and A. Shahin                         ;
  12. ;;                                                                            ;
  13. ;; Argument: lenLst     List, Demanded Lengths in Descending Order.           ;
  14. ;;           demLst     List, Number of Corresponding Demanded Length.        ;
  15. ;;           stockLen   Real, Length of Standard Stock.                       ;
  16. ;;           allPatP    Boolean, if true,  Generate all Feasible Patterns.    ;
  17. ;;                               if false, Generate only the Set of Patterns  ;
  18. ;;                                         for the First Demand > 0.          ;
  19. (defun GenPat (lenLst demLst stockLen allPatP / i j cntLst maxIdx patLst usedLen)
  20.   (setq maxIdx (length lenLst))
  21.   (setq i 0)
  22.   (while (zerop (nth i demLst)) (setq i (1+ i)))
  23.   (while
  24.     (or
  25.       (not cntLst)
  26.       (if allPatP
  27.         (> (apply '+ cntLst) 0)
  28.         (> (nth i (reverse cntLst)) 0)
  29.       )
  30.     )
  31.     (cond
  32.       (cntLst
  33.         (while (zerop (car cntLst)) (setq cntLst (cdr cntLst))) ; Last item in cntLst is for the first item (= longest) in lenLst.
  34.         (setq cntLst (cons (1- (car cntLst)) (cdr cntLst)))
  35.         (setq j (length cntLst))
  36.         (setq usedLen
  37.           (apply
  38.             '+
  39.             (mapcar
  40.               '(lambda (cnt len) (* cnt len))
  41.               (reverse cntLst)
  42.               lenLst
  43.             )
  44.           )
  45.         )
  46.       )
  47.       (T
  48.         (setq j 0)
  49.         (setq usedLen 0.0)
  50.       )
  51.     )
  52.     (while (< j maxIdx)
  53.       (setq cntLst
  54.         (cons
  55.           (min
  56.             (fix (/ (- stockLen usedLen) (nth j lenLst)))
  57.             (nth j demLst)
  58.           )
  59.           cntLst
  60.         )
  61.       )
  62.       (setq usedLen (+ usedLen (* (car cntLst) (nth j lenLst))))
  63.       (setq j (1+ j))
  64.     )
  65.     (setq patLst (cons (reverse cntLst) patLst))
  66.   )
  67.   (reverse (cdr patLst)) ; Remove 'zero pattern'.
  68. )