An Improved Heuristic Procedure for a Nonlinear Cutting Stock Problem

Many industries acquire stocks of material in large standard sizes which are then reduced to required widths or lengths according to demand. Scheduling the cutting operations is a particularly difficult problem when a few cutting patterns must be chosen from a vast number of feasible patterns such that the total cost of the reduction process is minimised. Physical constraints and economic considerations restrict the number and type of pattern which can be used. Haessler [Haessiler, R. W. An application of heuristic programming to a nonlinear cutting-stock problem occurring in the paper industry. Unpublished doctoral dissertation, The University of Michigan, Ann Arbor, 1968, available through University Microfilms, Ann Arbor, Dissertation No. 69–12, 119; Haessiler, R. W. 1971. A heuristic programming solution to a nonlinear cutting-stock problem. Management Sci. 17 (12, August) 793–802.] has described a typical problem in the paper industry and a heuristic procedure for obtaining satisfactory schedules. An improved procedure is proposed in which the type of pattern generated and accepted into the schedule is constrained to improve the likelihood that the residual scheduling problem has a feasible and economic solution. Results obtained by the proposed procedure are compared with those obtained manually and by Haessler for a set of eleven actual problems.

• 저널Management Science · 23(1) · 78–86
• 토픽Optimization and Packing Problems · Industrial and Manufacturing Engineering
• DOI10.1287/mnsc.23.1.78
• 저자Ian Lawson Coverdale, F. Wharton