We investigate a relay-aided multi-cell broadcasting system using random network codes, where the focus is on devising efficient scheduling algorithms between relay and base stations. Two scheduling algorithms are proposed based on different feedback strategies; namely, a one-step scheduling algorithm with instantaneous feedback for each redundancy packet; and a multi-step scheduling algorithm with feedback only after multiple redundancy packets. For the latter case, dynamic programming is applied to determine optimal scheduling. Numerical results show that the transmission efficiency of the multi-step algorithm approaches that of the one-step algorithm, but requires significantly less feedback. They both significantly outperform corresponding ARQ and random scheduling approaches.