Solving a real-world large-scale cutting stock problem: A clustering-assignment-based model

Abstract

This study stems from a furniture factory producing products by cutting and splicing operations. We formulate the problem into an assignment-based model, which reflects the problem accurately, but is intractable, due to a large number of binary variables and severe symmetry in the solution space. To overcome these drawbacks, we reformulate the problem into a clustering-assignment-based model (and its variation), which provides lower (upper) bounds of the assignment-based model. According to the classification of the board types, we categorize the instances into three cases: Narrow Board, Wide Board, and Mixed Board. We prove that the clustering-assignment-based model can obtain the optimal schedule for the original problem in the Narrow Board case. Based on the lower and upper bounds, we develop an iterative heuristic to solve instances in the other two cases. We use industrial data to evaluate the performance of the iterative heuristic. On average, our algorithm can generate high-quality solutions within a minute. Compared with the greedy rounding heuristic, our algorithm has obvious advantages in terms of computational efficiency and stability. From the perspective of the total costs and practical metrics, our method reduces costs by 20.90% and cutting waste by 4.97%, compared with a factory’s method.

Keywords:

• Furniture production
• large-scale cutting stock
• material batch feed
• material substitutability
• iterative heuristic

Additional information

Funding

The authors are grateful for the financial support partly from the Natural Science Foundation of China under grant No. 72188101, National Key R&D Program of China under grant No. 2018AAA0101705, and Shenzhen Municipal Science and Technology Innovation Committee under grant No. WDZC20200821140447001.

Notes on contributors

Xinye Hao

Xinye Hao received his BS degree and PhD degree in Industrial Engineering from Shandong University and Tsinghua University, China, respectively. His research interests include cutting & packing problems, lot-sizing problems, and scheduling problems.

Changchun Liu

Changchun Liu is a senior research fellow in IORA at National University of Singapore. His research interests are revenue management, supply chain management and optimization. He earned his PhD degree in the Department of Industrial Engineering at Tsinghua University, China. He has published his researches in many journals, such as IISE Transactions, European Journal of Operational Research, Annals of Operations Research, Transportation Research Part E, Computers & Industrial Engineering, International Journal of Production Research, etc.

Maoqi Liu

Maoqi Liu received a PhD degree in industrial engineering from Tsinghua University, China. His research interests include product design and development management, stochastic process, and distributionally robust optimization. He earned his BS degree in the mechanical design manufacture and automation from the School of Mechanical Engineering at Shandong University.

Canrong Zhang

Canrong Zhang is an associate professor in the Graduate School at Shenzhen, Tsinghua University, China. He received his PhD degree in Industrial engineering from Tsinghua University in 2010. His research interests include logistics system (especially the container terminal) optimization, manufacturing system optimization, and supply chain management. His work has appeared in European Journal of Operational Research, Computers & Industrial Engineering, International Journal of Production Research, Asia-Pacific Journal of Operational Research, Journal of Systems Science and Systems Engineering, and so on.

Li Zheng

Li Zheng is a professor in Department of Industrial Engineering at Tsinghua University, China. His current research interests are production system, manufacturing information system and digital manufacture. He has published numerous articles in many journals, such as European Journal of Operational Research, Computers & Operations Research, International Journal of Production Research, International Journal of Production Economics, etc.