In this work, we consider mixed traffic with time-sensitive users; a deadline-constrained user, and an AoI-oriented user. To develop an efficient scheduling policy, we cast a novel optimization problem formulation for minimizing the average AoI while satisfying the timely throughput constraints. The optimization problem is a Constrained Markov Decision Process (CMDP). We relax the constrained problem to an unconstrained Markov Decision Process (MDP) problem by utilizing Lyapunov optimization theory. The unconstrained problem is solved for each frame by applying backward dynamic programming. Simulation results show that the timely throughput constraints are satisfied while minimizing the average AoI. Also, simulation results show the convergence of the algorithm for different values of the weighted factor and the trade-off between the AoI and the timely throughput.