zbMATH — the first resource for mathematics

Performance testing of rectangular parts-nesting heuristics. (English) Zbl 0571.90029
We compare the performance of a set of rectangular layout heuristics on the basis of their packing densities and time performance, with a view to increase their applicability in manufacturing situations. Among the techniques is a class of heuristics introduced by the authors in an earlier work [J. Manufact. Systems 1, 169-186 (1982)]. The experimental comparison is made over two attributes defined for the bill of materials; the area and the aspect ratio distributions of the pieces. In addition, some of the heuristics considered permit limited human intervention. Our study shows that the two attributes play a significant part in determining the performance of a heuristic. Length-sorted heuristics are found to perform differently as a class from height-sorted heuristics. The study shows that human intervention, even in limited amounts, usually improves the quality of a solution substantially. The heuristics’ worst case time complexities are presented. For certain specific regions of the attributes, the best heuristic has been identified.

90B30 Production models
65K05 Numerical mathematical programming methods
90C90 Applications of mathematical programming
Full Text: DOI
[1] ORSINI R., Journal 23 pp 338– (1979)
[2] BENGTSSON B., The Computer Journal 25 pp 353– (1982) · doi:10.1093/comjnl/25.3.353
[3] BENTLEY J. L., C M U Working Paper (1980)
[4] BENTLEY J. L., C M U Working Paper (1980)
[5] Box , G. E. P. , HUNTER , W. G. and HUNTER , J. S. , 1978 . Statistics for experimenters ( New York John Wiley ), pp. 208 – 244 . · Zbl 0394.62003
[6] COFFMAN E. G., SIAM.Journal of Computing 9 pp 808– (1980) · Zbl 0447.68079 · doi:10.1137/0209062
[7] GAREY , M. R. , and JOHNSON , D. S. , 1980 , Approximation algorithms for bin packing problems A survey . Bell Laboratories Working Paper .
[8] GAREY , M. R. , and JOHNSON , D. S. , 1979 , Computers and intractibility A guide to the theory of NP-completeness ( San Francisco Freeman ), pp. 124 – 127 .
[9] HINXMAN A. I., A survey. European Journal of Operational Research 5 (8) (1980) · Zbl 0441.90042
[10] HODGSON T. J., IIE Transactions 14 pp 175– (1982) · doi:10.1080/05695558208974601
[11] ISRANI S., Journal of Manufacturing Systems 3 pp 81– (1984) · doi:10.1016/0278-6125(84)90024-4
[12] ISRANI S., Journal of Manufacturing Systems 1 pp 169– (1982) · doi:10.1016/S0278-6125(82)80027-7
[13] ISRANI S., Computers and Industrial Engineering (1983)
[14] SNEDECOR , G. W. , and COCHRAN , W. G.Statistical methods( Ames , Iowa Iowa State University ), pp. 233 – 237 .
[15] WANG P. Y., University of Maryland Mathematics Research (1981)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.