We present a new algorithm for deadline-aware scheduling of video streams over a wireless shared channel, which only requires the computation of a single metric per user and transmission slot. By incorporating side information about the video stream structure and the future channel behavior in the scheduling algorithm, our approach outperforms existing solutions by slowing down the transmission of streams to users with favorite channel conditions until their deadline is approaching. Hence, in overload situations, the quality of the bad users is significantly increased, while good users are almost unaffected. As a consequence, this leads to a fairer distribution of the achievable video quality among all users.