Reinforcement Learning for Assignment Problem with Time Constraints
This work addresses dynamic task-worker assignment problems with constraints, offering a real-time solution that is incremental in applying reinforcement learning to optimization domains.
The paper tackles the assignment problem with time constraints by developing a reinforcement learning framework that minimizes total assignment cost while adhering to hard constraints, outperforming Google OR-Tools solvers in solution quality and computation time for large instances.
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.