4
$\begingroup$

Suppose you have $K$ servers numbered $\{1,2,...,K\}$. Playing server $i$ provides a value of $v_i > 0$. However, once you play server $i$, you are not allowed to play it for the next $n_i$ time-slots. Assuming you have a time-horizon of $T \gg K$ time-slots, what is the optimal scheduling strategy to play the servers in terms of collecting the maximum total value.

There is a chance that this problem is well-studied but I cannot find any references, nor can I solve it trivially. Any help would be appreciated. I know that the greedy strategy of playing the available server with the highest value is not optimal.

$\endgroup$
  • $\begingroup$ This is what I was thinking.....but it may be wrong. Given that T is so large, the scheduling strategy is going to be periodic for most of the time slots. If we can get a bound on the period, then it boils down to finding the best order in that period, the complexity of which need not scale with T. However, this may be an additive constant away from the actual optimum value that can be achieved. $\endgroup$ – rajatsen91 Feb 22 at 20:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.