Abstract: In this paper, a standard one-dimensional cutting stock problem(S1-CSP) considering items transportation problem(ITP) is studied. It is assumed that the manufacturer undertakes products transportation. A coordination optimization model of standard one-dimensional cutting stock problem and items transportation is formulated. The model’s objective is to minimize total costs of the stock, items inventory and transportation. Lagrangian relaxation approach is employed to relax a certain type of constraint. A hybrid heuristic method called Lagrangian-based cutting and transportation heuristic based on the methods of column generation, sequential procedure, FFD and subgradient is developed. It consists of two sub-algorithms, one is for S1D-CSP, the other is for ITP. Finally, more than 1800 randomly generated instances have been solved by using the proposed method. The calculation results demonstrate the validity of the proposed model and the corresponding solving method. Compared with two-stage heuristic based on column generation, the hybrid heuristic algorithm reduces cost by 17.57% on average, which suggests that integrated algorithm is superior to two-stage algorithm.

Key words: cutting stock, transportation, sequencing, Lagrangian relaxation, patterns