International Journal of Industrial Engineering & Production Management

 Abstract: Packing rectangular shapes into a rectangular space is one of the most important discussions on Cutting & Packing problems (C&P) such as: cutting problem, bin-packing problem and distributor's pallet loading problem, etc. Assume a set of rectangular pieces with specific lengths, widths and utility values. Also assume a rectangular packing space with specific width and length. The objective function is to pack the pieces into the space in order to get the maximum sum of utility value of the packed pieces. To generate the related packing pattern, this paper proposes a new formulation method based on the column generation approach. In this method, on each cycle of the algorithm, a one-dimensional pattern is generated based on the shadow prices of the Simplex method. The set of generated one-dimensional patterns are used to construct the two-dimensional packing pattern. Also, the proposed model and the present models in the state-of-the art have been compared.