ABSTRACT
KARIMI, SAHAR Algorithms for Solving the Crosscutting Problem in a Wood Processing
Mill. (Under the direction of Professor Yahya Fathi).
In this thesis, an exact and an inexact method are proposed for solving the crosscutting
problem in a wood cutting mill. In a wood cutting mill, boards are first cut along their
length (rip) into strips; then the obtained strips are cut along their width (crosscut) into
cut-pieces with specific length and demand. Removing the defected areas of wood from the
strips gives us clear pieces which must be cut into cut-pieces. The crosscutting problem is
the problem of finding cutting patterns for all clear pieces such that demand of all cut-pieces
is satisfied with minimum amount of incoming strips.
A Mixed Integer Programming (MIP) model is developed for solving the
crosscutting problem optimally; solving the MIP model is, however, very time-consuming.
As a result, we added some valid inequalities (VI's) to the model with the purpose of
increasing the efficiency of the model. The VI's are useful, but the model still couldn't
solve large instances in reasonable time.
To overcome the difficulty of solving time for large instances a heuristic method (inexact
method) is proposed for solving the problem. We evaluated the quality of the solution
obtained by the heuristic method, and its solving time. The heuristic method is fast enough
to solve very large instances; the value of the solution obtained via this heuristic, however,
is a few percent above optimal in the instances that we performed the experiment on.
