Comparing Heuristics, Constraint Optimization, and Reinforcement Learning for an Industrial 2D Packing Problem

2021-10-27 · Stefan Böhm, Martin Neumayer, Oliver Kramer, Alexander Schiendorfer, Alois Knoll

Cutting and Packing problems are occurring in different industries with a direct impact on the revenue of businesses. Generally, the goal in Cutting and Packing is to assign a set of smaller objects to a set of larger objects. To solve Cutting and Packing problems, practitioners can resort to heuristic and exact methodologies. Lately, machine learning is increasingly used for solving such problems. This paper considers a 2D packing problem from the furniture industry, where a set of wooden workpieces must be assigned to different modules of a trolley in the most space-saving way. We present an experimental setup to compare heuristics, constraint optimization, and deep reinforcement learning for the given problem. The used methodologies and their results get collated in terms of their solution quality and runtime. In the given use case a greedy heuristic produces optimal results and outperforms the other approaches in terms of runtime. Constraint optimization also produces optimal results but requires more time to perform. The deep reinforcement learning approach did not always produce optimal or even feasible solutions. While we assume this could be remedied with more training, considering the good results with the heuristic, deep reinforcement learning seems to be a bad fit for the given use case.

📄 PDF Abstract BibTeX arXiv:2110.14535

Code (0)

등록된 구현이 없습니다.

Tasks

Deep Reinforcement Learningreinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Memory-Enhanced Neural Solvers for Efficient Adaptation in Combinatorial Optimization

2024-06-24 · Felix Chalumeau, Refiloe Shabe, Noah de Nicola, Arnu Pretorius 외

Combinatorial Optimization is crucial to numerous real-world applications, yet still presents challenges due to its (NP-)hard nature. Amongst existing approaches, heuristics often offer the best trade-off between quality…

Combinatorial Optimization Reinforcement Learning (RL)

SeaPearl: A Constraint Programming Solver guided by Reinforcement Learning

2021-02-18 · Félix Chalumeau, Ilan Coulon, Quentin Cappart, Louis-Martin Rousseau

The design of efficient and generic algorithms for solving combinatorial optimization problems has been an active field of research for many years. Standard exact solving approaches are based on a clever and complete enu…

BIG-bench Machine Learning Combinatorial Optimization reinforcement-learning Reinforcement Learning+1

Edge Generation Scheduling for DAG Tasks Using Deep Reinforcement Learning

2023-08-28 · Binqi Sun, Mirco Theile, Ziyuan Qin, Daniele Bernardini 외

Directed acyclic graph (DAG) tasks are currently adopted in the real-time domain to model complex applications from the automotive, avionics, and industrial domains that implement their functionalities through chains of …

Deep Reinforcement Learning reinforcement-learning Reinforcement Learning Scheduling

Introducing PetriRL: An Innovative Framework for JSSP Resolution Integrating Petri nets and Event-based Reinforcement Learning

2024-01-23 · Sofiene Lassoued, Andreas Schwung

Resource utilization and production process optimization are crucial for companies in today's competitive industrial landscape. Addressing the complexities of job shop scheduling problems (JSSP) is essential to improving…

Decision Making Deep Reinforcement Learning Job Shop Scheduling Scheduling

Logic-informed reinforcement learning for cross-domain optimization of large-scale cyber-physical systems

2025-11-02 · Guangxi Wan, Peng Zeng, Xiaoting Dong, Chunhe Song 외 arxiv

Cyber-physical systems (CPS) require the joint optimization of discrete cyber actions and continuous physical parameters under stringent safety logic constraints. However, existing hierarchical approaches often compromis…

Reinforcement Learning