Cutting Stock Problem: A Heuristic Solution Based on Human Intuitive Strategies

Abstract

The goal of the cutting stock operation is to maximize the material utilization by laying out maximum number of parts on a sheet. Historically, laying of parts on a sheet has been performed by humans. As the manual process is very time consuming, a number of heuristic and mathematical algorithms have been developed in recent years. However, these algorithms do not guarantee higher utilizations than those achieved by human operators. This study investigated the feasibility of extracting and generalizing the involved human strategies in laying out parts. The results indicated that it is possible to extract and form generalized strategies leading to higher utilization. A group, trained with these strategies, achieved higher utilization than the untrained group. The trained group also achieved higher utilization than the most promising mathematical algorithm. This implies that these strategies can be used to train new operators. Using these strategies and automation aids such as a graphics software, the layout process will be much faster and produce high material utilization.

Get full access to this article

View all access options for this article.

References

Adamowicz

Albano

(1976). A solution of the rectangular cutting-stock problem. IEEE Transactions on Systems, Man and Cybernatics, (SMC-6(4)), 302–310.

Albano

(1977). A method to improve two-dimensional layout. Computer Aided Design, 9, 48–52.

Albano

Sapuppo

(1980). Optimal allocation of two-dimensional irregular shapes using heuristic search methods. IEEE Transactions on System, Man and Cybernetics, (SMC-10), 242–248.

Amaral

Bernardo

Jorge

(1990). Marker-marking using automatic placement of irregular shapes for the garment industry. Computer and Graphics, 14 (1), 41–46.

Dagli

C. H.

Tatoglu

Y.M.

(1987). An approach to two-dimensional cutting stock problems. International Journal of Production Research, 25, 175–190.

Dori

Ben-Bassat

(1984). Efficient nesting of congruent convex figures. Communications of the ACM, 27 (3),228–235.

Dyckhoff

(1981). A new linear programming approach to the cutting stock problem. Operations Research, 29, 1092–1104.

Eisemann

(1957). The trip loss problem. Management Science, 3, 279–284.

Freeman

Shapira

(1975). Determining the minimum-area encasing rectangle for an arbitrary closed curve. Communications of the ACM, 18 (7), 409–413.

10.

Gilmore

P.C.

Gomory

R.E.

(1963). A linear programming approach to the cutting stock problem Part II. Operations Research, 11, 863–888.

11.

Haessler

R.W.

Sweeney

P.E.

(1991). Cutting stock problems and solution procedures. European Journal of Operational Research, 54, 141–150.

12.

Ismail

H.S.

Hon

K.K.B.

(1992). New approaches for the nesting of two dimensional shapes for press tool design. International Journal of Production Research, 30 (4), 825–837.

13.

Israni

Sanders

J.L.

(1982). Two-dimensional cutting stock problem research: A review and a new rectangular layout algorithm. Journal of Manufacturing Systems, 1, 169–182.

14.

Israni

Sanders

(1985). Performance testing of rectangular parts-nesting heuristic. International Journal of Production Research, 23, 437–456.

15.

Kershner

R.B.

(1968). On paving the plane. American Mathematical Monthly, 75, 839–844.

16.

Koroupi

Loftus

(1991). Accommodating diverse shapes within hexagonal pavers. International Journal of Production Research, 29 (8), 1507–1519.

17.

Paull

A.E.

(1956). Linear programming: A key to optimum newsprint production. Pulp and Paper Magazine of Canada, 57, 145–150.

18.

Poshyanonda

Dagli

C.H.

(1993). Genetic neuro-nester for irregular patterns. Intelligent Engineering Systems through Artificial Neural Networks, 3, 825–830.

19.

Sanders

J.L.

(1987). A nesting algorithm for irregular parts and factors affecting trim losses. ernational Journal of Production Research, 381–397.

20.

Sanders

J.L.

(1989). Sequence selection of stock sheets in the two-dimensional layout. International Journal of Production Research, 27, 1553–1571.

21.

Roberts

S.A.

(1984) Application of heuristic techniques to the cutting-stock problem for worktops. Journal of Operations Research Society, 35(5), 369–377.

22.

Sweeney

P.E.

Taternoster

E.R.

(1992) Cutting and Packing Problems: A categorized, Application-Oriented Research Bibliography. OR: Journal of the Operations Research Society, 43 (7), 691–706.