;; 1d-csp by ymg ;
;; ;
;; Cutting Stock Problem as per approach described in: ;
;; ;
;; A GENERALIZED APPROACH TO THE SOLUTION ;
;; OF ONE-DIMENSIONAL STOCK-CUTTING ;
;; PROBLEM FOR SMALL SHIPYARDS. ;
;; by Ahmet Cemil Dikili and Baris Barlas ;
;; ;
;; Link: http://jmst.ntou.edu.tw/marine/19-4/368-376.pdf ;
;; ;
;; Argument: l List, Demanded Lengths in Decreasing order. ;
;; d List, Number of Corresponding Demanded Length. ;
;; ls Real, Length of Standard Stock. ;
;; ;
;; Returns: A List of Cutting Patterns, where each member is composed ;
;; of 3 items as follow: Item 1, Nb of times to apply Pattern. ;
;; Item 2, List of integers where each ;
;; element correspond to the nb of ;
;; times to use a demanded length. ;
;; Item 3, Total Waste for this Pattern. ;
;; ;
(defun 1D
-CSP
(l d ls
/ a ch cp idx maxint p tl sm pu v
)
(setq v
(genpat l d ls
nil) p
nil) )
)
; Here we Sort the Set of Patterns on Min tl, Max sm and Min pu ;
; The Chosen Pattern will bubble up to top of the list. ;
)
)
)
)
)
; Building the Cutting Plan, then Adjusting the Demand List. ;
)
)
;; genpat by ymg ;
;; ;
;; Procedure for Generating the Efficient Feasible Cutting Patterns ;
;; http://www.cs.bham.ac.uk/~wbl/biblio/gecco2006/docs/p1675.pdf ;
;; Appendix 1 ;
;; Part of "Cutting Stock Waste Reduction Using Genetic Algorithms" ;
;; by Y. Khalifa, O. Salem and A. Shahin ;
;; ;
;; Argument: l List, Demanded Lengths in Descending Order. ;
;; d List, Number of Corresponding Demanded Length. ;
;; ls Real, Length of Standard Bar. ;
;; all Boolean, if true, Generate all Feasible Patterns. ;
;; if false, Generates only the Set of Patterns ;
;; for the First Demand > 0 ;
;; ;
(defun genpat
(l d ls all
/ a i j p s
) )
)
)
)
)
)
)
;; Ceiling function, Returns the smallest integer not less than x. ;
;; Floor function, Returns the largest integer not greater than x. ;
(defun c:test
(/ l1 l2 d1 d2 ls1 ls2
) (setq prob '
(("Problem 1 by Dikili & Barlas \n" (60.0 50.0 30.0 25.0 20.0 10.0)
(6 7 15 20 9 16)
100.0
)
("Problem 2 by Dikili & Barlas \n"
(40.0 30.0 20.0 10.0 5.0)
(7 10 6 4 2)
100.0
)
("Problem 3 by CAB \n"
(9.71 7.65 5.30 4.00 3.67 2.66)
(44 23 10 54 120 67)
12.01
)
("Problem 4 by Jeff H. \n"
(15.3 14.4 12.34)
(4 30 2)
60.0
)
("Problem 5 by ElpanovEvgenyi \n"
(62 20 17 12 9 8 6)
(1 1 1 1 1 2 1 1)
80
)
("Problem 6 by Khalifa, Salem & Shahin \n"
(19.0 15.5 15 12 10 8.5)
(4 4 4 4 4 4 4)
40.00
)
("Problem 7 by Khalifa, Salem & Shahin \n"
(12.146 11.896 11.729 9.396 9.0625 7.229 4.177 3.0)
(2 2 32 6 4 4 28 6)
40.00
)
("Problem 8 by sergiu \n"
(4.500 3.600 3.100 1.400 0.750)
(97 610 395 211 300)
12.000
)
)
)
(solve pr)
)
)
;; solve by ymg ;
;; ;
;; A temporary, somewhat crude Output for testing purposes. ;
;; Could be replaced by an Acad table or an Output to Excel ;
;; ;
;; Argument: ;
;; pr, List of 4 items (title l d ls) ;
;; Where title, is a String ;
;; l, List of Demanded Lengths in Decreasing Order ;
;; d, List of Associated Demand ;
;; ls, Length of a Standard Bar. ;
;; ;
;; The routine calls "1D-CSP" ;
;; ;
(defun solve
(pr
/ p tit l d ls i
) p (1d-csp l d ls)
)
)
;; ReadCSV - Lee Mac ;
;; Parses a CSV file into a list of lists, ;
;; each sublist is a row of CSV cell values. ;
;; ;
(defun ReadCSV
( filename
/ _csv
->lst file line lst
)
(defun _csv
->lst
( str
/ pos
) )
)
)
)
)
)
;; massoc by Gile Chanteau ;
;; ;
;; Returns a list of all items associated with the specified key ;
;; in an association list. ;
;; ;
;; Arguments: ;
;; k, The value to search for in the list. ;
;; l, List of Associations ;
;; ;
)
)
;; distinct by Gile Chanteau ;
;; Deletes all duplicates in a list. ;
;; ;
;; Argument ;
;; l List ;
;; ;
)
)
(defun c:sergiu
(/ a d data fn l ld ls size title
) (setq ls
12000) ; Length of Standard Bar ; (prompt "Select CSV File Containing Your Data :")
(setq data
(cdr (ReadCSV fn
)) ; cdr is to discard the line of titles ; size
(distinct
(mapcar '
cadr data
)) ; size is the list of distinct diameters; )
;; Data is now an association list and length and demand are in Integers. ;
(setq title
(strcat "Cutting Patterns for Diam. " diam
) )
(solve
(list title l d ls
)) )
)
