Scholarlink

The cutting stock problem (CSP) has long been a cornerstone of combinatorial optimization, addressing critical manufacturing challenges by efficiently cutting standard-sized materials to meet customer demands. Despite its significance, solving CSP remains a formidable task due to its NP-hard nature. Various exact and heuristic methods have been explored, including linear programming, cutting plane algorithms, heuristics, and metaheuristic techniques. Recently, there has been a growing interest in integrating Reinforcement Learning (RL) into CSP solutions, leveraging its ability to adapt to dynamic environments and optimize cutting patterns. This study presents a novel algorithm that combines Column Generation (CG) with RL to obtain optimal integer solutions that maximize the material utilization for real-world CSP instances. Unlike traditional RL methods, which aim to obtain integer solutions directly, our approach integrates CG to derive cutting patterns and LP relaxations before employing RL for integer solutions to obtain the utilization maximization of the standard-sized materials in the cutting process. This step-by-step learning process offers a direct solution for every subproblem of the main large CSP instance regarding demand changes, enhancing efficiency and effectiveness in production planning. Case studies demonstrate the efficacy of our method in maximizing the utilization up to 92%, offering promising avenues for future research in this domain.

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Integrating Column Generation with Reinforcement Learning for Optimal Solutions in the One-Dimensional Cutting Stock Problem

  • 会议论文

  • 发表日期：

    2025年

查看全文
  • Onur Osman,
  • Tolga Kudret Karaca,
  • Bahar Yalçın Kavuş,
  • Sajjad Nematzadeh,
  • Gökalp Tulum

摘要

The cutting stock problem (CSP) has long been a cornerstone of combinatorial optimization, addressing critical manufacturing challenges by efficiently cutting standard-sized materials to meet customer demands. Despite its significance, solving CSP remains a formidable task due to its NP-hard nature. Various exact and heuristic methods have been explored, including linear programming, cutting plane algorithms, heuristics, and metaheuristic techniques. Recently, there has been a growing interest in integrating Reinforcement Learning (RL) into CSP solutions, leveraging its ability to adapt to dynamic environments and optimize cutting patterns. This study presents a novel algorithm that combines Column Generation (CG) with RL to obtain optimal integer solutions that maximize the material utilization for real-world CSP instances. Unlike traditional RL methods, which aim to obtain integer solutions directly, our approach integrates CG to derive cutting patterns and LP relaxations before employing RL for integer solutions to obtain the utilization maximization of the standard-sized materials in the cutting process. This step-by-step learning process offers a direct solution for every subproblem of the main large CSP instance regarding demand changes, enhancing efficiency and effectiveness in production planning. Case studies demonstrate the efficacy of our method in maximizing the utilization up to 92%, offering promising avenues for future research in this domain.