We consider a joint scheduling-and-power-allocation problem of a downlink cellular system. The system consists of two groups of users: real-time (RT) and non-real-time (NRT) users. Given an average power constraint on the base station, the problem is to find an algorithm that satisfies the RT hard deadline constraint and NRT queue stability constraint. We propose two sum-rate-maximizing algorithms that satisfy these constraints as well as achieving the system's capacity region. In both algorithms, the power allocation policy has a closed-form expression for the two groups of users. However, interestingly, the power policy of the RT users differ in structure from that of the NRT users. The first algorithm is optimal for the on-off channel model with a polynomial-time scheduling complexity in the number of RT users. The second, on the other hand, works for any channel fading model which is shown, through simulations, to have an average complexity that is close-to-linear. We also show the superiority of the proposed algorithms over existing approaches using extensive simulations.