Reinforcement Learning to Grouped Scheduling Optimisation Problem

Question

I am not sure the name of this kind of problem, but anyway, the situation is as below.

Assign teachers into Groups and consider on each of their workload, availability etc. There are some other soft/hard constraint (equality/inequality) like

• Each group should have at least 2 teachers
• Everyone in the group have similar workload
• Total workload in the group is below a certain value
• All are in different expertise

and more...

I am trying to build a sub-optimal solution to solve this problem. Linear/non-linear programming seems not working for grouping problems. I am thinking of genetic algorithm or reinforcement learning.

Can this problem solve by using RL or DRL? I am trying to define the groups as state, and actions include "assignToGroup" and "removeFromGroup". And any kind of idea or suggestion of how to solve this problem?

Many thanks

Answer 1

It is often possible, by describing certain parts of a problem as state, others as actions, and some measurement you want to optimise as a reward, to frame a problem as a reinforcement learning task. However, this is not always helpful.

I suspect your problem is in the "RL is not that helpful" category. You could give it a try, and maybe expect to find working solutions but take an unreasonable amount of time to find optimal solutions.

What you appear to have here is a problem in combinatorial optimisation. There are many applicable algorithms, a good selection are described in the free book Clever Algorithms: Nature-Inspired Programming Recipes - which is best will be determined by the specific details of your constraints and the size of the problem.

If many constraints are soft and can be assigned a cost, you may be able to use genetic algorithms (with genome being group assignments in order) or simulated annealing for example.