@ 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.
(defun Alt
-1D
-CSP
(lenLst demLst stockLen
) (Alt-FFD-BinPack lenLst demLst stockLen)
(1D-CSP lenLst demLst stockLen okLossFact allPatP)
)
'(0.000 0.000 0.005 0.010 0.015 0.020 0.025 0.030 0.035 0.040 0.045 0.050)
'(nil T T T T T T T T T T T )
)
)
'
(lambda (a b
) (< (car a
) (car b
))) ; Sort using loss factor. )
)
)
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:
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.