Offering throughput guarantees for cellular wireless networks, carrying real-time traffic, is of interest to both the network operators and the customers. In this article, we formulate an optimization problem which aims at maximizing the throughput that can be guaranteed to the mobile users. By building on results obtained by Borst and Whiting and by assuming that the distributions of the users' carrier-to-noise ratios are known, we find the solution to this problem for users with different channel quality distributions, for both the scenario where all the users have the same throughput guarantees, and the scenario where all the users have different throughput guarantees. Based on these solutions, we also propose two simple and low complexity adaptive scheduling algorithms that perform significantly better than other well-known scheduling algorithms. We further develop an expression for the approximate throughput guarantee violation probability for users in time-slotted networks with the given cumulants of the distribution of bit-rate in a time-slot, and a given distribution for the number of time-slots allocated within a time-window.