IEEE 802.16 standard defines the broadband wireless access specification for WiMAX, but it did not specify a standard scheme for scheduling algorithms and admission control. As a result, we propose an uplink scheduling scheme called Random Early Detection based Deficit Fair Priority Queue (RED-based DFPQ) for WiMAX. RED-based DFPQ adjusts the deficit counter of rtPS based on the current queue length. Our proposed scheme improves the transmission quality of rtPS traffic in WiMAX networks. Our simulation results show that RED-based DFPQ enhances the throughput of rtPS, reduces the delay of rtPS and avoids the starvation of lower priority service classes when compared with other scheduling schemes.