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?

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


You must log in to answer this question.

Browse other questions tagged .