Efficient waste reduction algorithms based on alternative underestimates for the modied Wang method

Abstract

This paper is concerned with wastage reduction in constrained two-dimensional guillotine- cut cutting stock problems, often called trim loss problems. A number of researchers report in the literature on algorithmic approaches to nd exact solutions for the trim loss problem.
Alternative heuristic functions are investigated and applied to the modied Wang method. This involves the sharpening of underestimates used in the methods heuristic function. Two aspects of these solution approaches are considered and some empirical results are given. The rst part considers the feasibility to construct more informed heuristic functions. The second part investigates the role of more informedness on the computational cost of these search processes.

Key words: Cutting stock, trim loss, guillotine cutting.