crichmon@digi.lonestar.org (Charles Richmond) (10/02/90)
Given a large number of rectangular pieces of sheet metal (all of the same size), it is desired to cut out smaller rectangular pieces of given number and dimensions. The goals are to minimize the number of large pieces used for cutting, and to have the largest pieces of scrap left over with usable dimensions (i.e. width very nearly equal to height, such as 5 x 6 instead of 30 x 1). For example: If the larger rectangular sheets are 20 x 30 units and it is desired to cut five pieces of 7 x 8 and three pieces of 10 x 12, the the following MIGHT be a solution: <--------- 20 ----------> <--------- 20 ----------> ------------------------- ------------------------- | | | ^ | | | | | | | | | 7 x 8 | 7 x 8 | | | 10 x 12 | 10 x 12 | | | | | | | | | | | | | | | | | | |________|________| | |___________|___________| | | | scrap | | | | | | | 7 x 8 | | | | 7 x 8 | | 30 | | | | 10 x 12 | | | | | | scrap | | | | | | |________| | | |________| | | | | |___________| | | | | | | | 7 x 8 | | | | scrap | | | | | | | | | scrap | | | | | scrap | | |________| | v | | ------------------------- -------------------------- Another constraint is that the smaller pieces must be placed to allow for "clear cuts," i.e. all cuts must pass completely across the larger sheet of metal. Thus a configuration like the following would NOT be allowed: ---------------------------------- | | | | | | | | | | |----------------------| | | | | | | | | | | | | | | | | | | | | |----------------------| | | | | | | | | | | ---------------------------------- For a computer solution, it seems to be a problem for backtracking techniques. A solution that is "close" to the optimal placement for the pieces will be sufficient. If you do not know how to approach this problem (hey, we don't either), maybe you can give some references to books or journal articles that will be of help. If this is not the right group to post this article, please tell me where I can post it to find some information. Thanks in advance for any help you can render! Charles Richmond crichmon@digi.lonestar.org
GNewsam@itd.dsto.oz (G.N. Newsam) (10/06/90)
References: <1048@digi.lonestar.org> Organization: Defence Science & Technology, Australia In article <1048@digi.lonestar.org> crichmon@digi.lonestar.org (Charles Richmond) writes: > Given a large number of rectangular pieces of sheet metal (all of > the same size), it is desired to cut out smaller rectangular pieces > of given number and dimensions. The goals are to minimize the > number of large pieces used for cutting, and to have the largest > pieces of scrap left over with usable dimensions .... This problem can probably be tackled using some variant of linear programming. However before attempting a solution the proposer might first consider what happened to a previous solver. I think the following story is apocryphal, but I would be interested to know if it is indeed true. During the 1930's while Stalin's purges were in full swing, Kolmogorov was asked by a Russian factory to help them with the same basic problem of minimizing wastage in cutting various shapes from basic steel sections. He tackled the problem using linear program and reduced wastage by 60% or more. The factory was duly grateful and Kolmogorov no doubt had the satisfaction of a job well done, if nothing more. However shortly after this work he was arrested in the middle of the night, charged with sabotaging the economy and smartly sentenced to death; the story goes that he was only reprieved at the last minute after pleas and intervention at quite a high level. Kolmogorov's crime was that he had been too successful in reducing wastage. Apparently the wastage from the first factory had been a vital input to a second factory; when this factory found its inputs cut by 60% it complained loudly. In the atmosphere of the times this quickly became a witch hunt and the fingers all quickly ended up pointing at the interfering mathematician. In present times what with pressure on scientitsts to be commercial and the state of the Soviet economy, this story would seem to hold a number of morals for mathematicians and others. G.N. Newsam Anzus: The last line of defence for penguins. (Opinions expressed above are those of the penguins only and do not necessarily coincide with those of DSTO as a whale.)