I have searched for and not found an analytic upper bound $f$
$P(Q(t) \geq a) \leq f(t,a)$
where $Q(t) = \max_{s \leq t} q(s)$, $q(s)$ is the queue length at time $s$, and $t,a$ are finite. This is for a simple M/D/1 queue with arrival rate $ \lambda$, fixed service rate $\mu$. I am not looking for asymptotic bounds when $t$ or $a$ tend to infinity. Any help or pointers to literature would be appreciated.
This is not a full answer, but it is far too detailed for a comment.
Let $N(t)$ be the number of customers in the system at time $t$, with $N(0)=N_0$, and let $\lambda$ be the arrival rate with $1/\mu$ the service time. Baek et al show that the probability that there are zero customers in the system at time $t$ given that $N_0=j$ is $$ \mathbb P(N(t)=0\mid N_0=j) := Q_0^{(j)} = \sum_{r=0}^{\lfloor \mu t\rfloor}\frac{(\lambda t)^r e^{-\lambda t}}{r!}\cdot\left(1-\frac r{\mu t}\right) $$ and more generally \begin{align} Q_n^{(j)}(t) = \frac{(\lambda t)^{n+\lfloor \mu t\rfloor - j}e^{-\lambda t}}{(n+\lfloor \mu t\rfloor - j)!} + &\sum_{r=0}^{\lfloor \mu t\rfloor - j-1}\sum_{m=0}^{\lfloor \mu t\rfloor-j-r-1}\frac{\left[\lambda\left(t-\frac{r+1}{\mu}\right) \right]^m e^{-\lambda\left(t - \frac{r+1}{\mu}\right)}}{m!}\\ &\ \times \left(1-\frac m{\mu t-r-1}\right)\left[1-\frac{\lambda(r+1)}{\mu(n+r+1)}\right]\cdot\frac{\left[\frac{\lambda(r+1)}{\mu}e^{-\frac{\lambda(r+1)}{\mu}} \right]^{n+r}}{(n+r)!}. \end{align} If we assume that $N_0=0$, we have \begin{align} Q_n^{(0)}(t) = \frac{(\lambda t)^{n+\lfloor \mu t\rfloor}e^{-\lambda t}}{(n+\lfloor \mu t\rfloor)!} + &\sum_{r=0}^{\lfloor \mu t\rfloor-1}\sum_{m=0}^{\lfloor \mu t\rfloor-r-1}\frac{\left[\lambda\left(t-\frac{r+1}{\mu}\right) \right]^m e^{-\lambda\left(t - \frac{r+1}{\mu}\right)}}{m!}\\ &\ \times \left(1-\frac m{\mu t-r-1}\right)\left[1-\frac{\lambda(r+1)}{\mu(n+r+1)}\right]\cdot\frac{\left[\frac{\lambda(r+1)}{\mu}e^{-\frac{\lambda(r+1)}{\mu}} \right]^{n+r}}{(n+r)!}, \end{align} and from here we can seek to bound $$ Q(t) := \sup\left\{Q_n^{(0)}(s): 0\leqslant s\leqslant t\right\}. $$