# Can RL solve scheduling problems with unknown function

I have the following scheduling problem.

• There are $$n$$ tasks and $$m>n$$ machines.
• Each task $$i$$ has a requirement $$t_i$$ that should be guaranteed.
• Any task can be scheduled on at least one machine but a machine cannot schedule more that one task.
• When a task $$i$$ is scheduled on machines $$S_i\subset\{1,2,\ldots,m\}$$, the machines in $$S_i$$ should be consecutive meaning that the set $$S_i$$ is of the form $$S_i=\{j,j+1,\ldots,j+|S_i|-1\}$$, for some $$j\in\{1,2,\ldots,m\}$$.
• Given the scheduling $$S_1,\ldots,S_n$$, we can compute a satisfaction value for each task $$i$$ scheduled on machine $$j\in S_i$$ as $$f_{ij}(S_1,\ldots,S_n)>0$$, which is unknown. I only have access to a black-box to compute $$f_{ij}(\cdot)$$. So, given $$S_1,\ldots,S_n$$, I can find the satisfaction value for each task $$i$$ and each machine $$j\in S_i$$.
• We have to guarantee that each task $$i$$ has the sum of its satisfaction values of its machines is at least $$t_i$$, i.e., $$\sum_{j\in S_i}f_{ij}(S_1,\ldots,S_n)\geq t_i$$.
• The objective is to maximize the sum of all satisfaction values, i.e., $$\sum_{i=1}^n\sum_{j\in S_i}f_{ij}(S_1,\ldots,S_n)$$.

Is RL a good approach to solve this problem. What RL algorithm do you suggest and why? I was trying to model it using MAB but when I was defining the arms I figured out that the number of arms can be the possible partitions of $$m$$ into $$n$$ tasks (with permutations). So for $$m=70$$ and $$n=6$$, I have 11238513 arms. So, I don't know if it is possible to apply MAB. Even with RL, that action space will be very large and should the RL assume terminal reward game or step reward game?

• from your formulation, you have more machines than tasks Commented Dec 22, 2023 at 10:41
• Yes exactly. A task is heavy and needs more than one machine to be executed.
– Jika
Commented Dec 22, 2023 at 22:00