Applying Markov Decision Processes to an arrival forecasting problem

Question

I have the following problem and I'd like to know if it's something that was already studied in the literature or not. I'm not sure about the naming conventions either.

I have a system $S$ that can accept at most $N$ users. For the sake of simplicity let's assume that it is a discrete-time system $t = t_0,t_1,\ldots,t_n$.

Now, users are divided into $M$ classes $ m = 1,\ldots,M$. Each user pays $m$ in order to be in the system for a time slot. Users arrive to the system according to a geometric distribution that depends on the class. So, interarrival times between two users belonging to the same class has $p = i_m \forall m \in 0,\ldots,M$.

Users have associated a duration time that also follows a geometric distribution: $p = d_m \forall m \in 0,\ldots,M$

So, for example, the next user of class $m$ arrives at a time $i$ geometrically distributed with parameter $p = i_m$, will have a duration $d$ geometrically distributed with $p = d_m$ and will pay $m*d$ dollars.

The system has to take a decision every time a user arrives: accept it or not. The goal is to maximize the revenues. For example, if $N=1$ and a $t=0$ a user of class 1 arrives with $d = 10$, accepting it means to exclude all the users of higher classes from the system for the next 10 slots.

I have to define a strategy for problem. My idea is to follow a Viterbi-alike algorithm, simulating the system over the next time window $W$ and choosing the best first-decision that leads to the path satisfies the criteria on the occupation, the likelihood and the revenue.

Is there literature on similar problems? Any alternative strategies? Can it be solved by using the Markovian Decision Process theory?

Answer 1

This problem certainly seems like something that can be studied using the theory of Markov decision processes.

You could try looking into the literature on the optimal admission control of queueing systems. The book Stochastic Dynamic Programming and the Control of Queueing Systems by Sennott might be helpful.

Also, this recent paper considers a similar problem, and might contain some useful references.