The profit-oriented interval cutting problem: Model and stability analysis

A one-dimensional cutting problem recently introduced by the author is extended to the case of profit maximization. For a number of pieces of a (curtain) bale it has to be decided sequentially how they should be cut down to lengths accepted by the customers. They may cut down to single pieces and to pairs of shorter pieces, both of variable length within some boundaries. If now the profit parameters p and q for units of single pieces and of pairs differs a profit maximization model can be set up in which cutting is aimed not at minimizing the unusable rest of the pieces but at maximizing the profit from the usable pieces. This problem can be solved by the dynamic programming approach. Moreover, the stability of solutions generated by the dynamic programming method is studied for the case of profit parameters changes. Boundaries for the feasible ratio p/q will be derived, for which a found optimal solution remains valid.