Reinforcement Learning for Assignment Problem with Time Constraints

2021-06-05 · Sharmin Pathan, Vyom Shrivastava

We present an end-to-end framework for the Assignment Problem with multiple tasks mapped to a group of workers, using reinforcement learning while preserving many constraints. Tasks and workers have time constraints and there is a cost associated with assigning a worker to a task. Each worker can perform multiple tasks until it exhausts its allowed time units (capacity). We train a reinforcement learning agent to find near optimal solutions to the problem by minimizing total cost associated with the assignments while maintaining hard constraints. We use proximal policy optimization to optimize model parameters. The model generates a sequence of actions in real-time which correspond to task assignment to workers, without having to retrain for changes in the dynamic state of the environment. In our problem setting reward is computed as negative of the assignment cost. We also demonstrate our results on bin packing and capacitated vehicle routing problem, using the same framework. Our results outperform Google OR-Tools using MIP and CP-SAT solvers with large problem instances, in terms of solution quality and computation time.

📄 PDF Abstract BibTeX arXiv:2106.02856

Code (0)

등록된 구현이 없습니다.

Tasks

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

Multi Agent Reinforcement Learning for Sequential Satellite Assignment Problems

2024-12-20 · Joshua Holder, Natasha Jaques, Mehran Mesbahi

Assignment problems are a classic combinatorial optimization problem in which a group of agents must be assigned to a group of tasks such that maximum utility is achieved while satisfying assignment constraints. Given th…

Combinatorial Optimization Multi-agent Reinforcement Learning reinforcement-learning Reinforcement Learning+1

Optimal Task Assignment and Path Planning using Conflict-Based Search with Precedence and Temporal Constraints

2024-02-13 · Yu Quan Chong, Jiaoyang Li, Katia Sycara

The Multi-Agent Path Finding (MAPF) problem entails finding collision-free paths for a set of agents, guiding them from their start to goal locations. However, MAPF does not account for several practical task-related con…

Multi-Agent Path Finding Reinforcement Learning (RL)

Constrained Optimization of Charged Particle Tracking with Multi-Agent Reinforcement Learning

2025-01-09 · Tobias Kortus, Ralf Keidel, Nicolas R. Gauger, Jan Kieseler

Reinforcement learning demonstrated immense success in modelling complex physics-driven systems, providing end-to-end trainable solutions by interacting with a simulated or real environment, maximizing a scalar reward si…

Multi-agent Reinforcement Learning

Attention Routing: track-assignment detailed routing using attention-based reinforcement learning

2020-04-20 · Haiguang Liao, Qingyi Dong, Xuliang Dong, Wentai Zhang 외

In the physical design of integrated circuits, global and detailed routing are critical stages involving the determination of the interconnected paths of each net on a circuit while satisfying the design constraints. Exi…

reinforcement-learning Reinforcement Learning Reinforcement Learning (RL)

A Deep Reinforcement Learning Approach for Online Parcel Assignment

2021-09-08 · Hao Zeng, Qiong Wu, Kunpeng Han, Junying He 외

In this paper, we investigate the online parcel assignment (OPA) problem, in which each stochastically generated parcel needs to be assigned to a candidate route for delivery to minimize the total cost subject to certain…

Decision Making Deep Reinforcement Learning reinforcement-learning Reinforcement Learning+1