We consider Downlink (DL) scheduling for a multi-user cooperative cellular system with fixed relays. The conventional scheduling trend is to avoid interference by allocating orthogonal radio resources to each user, although simultaneous allocation of users on the same resource has been proven to be superior in, e.g., the broadcast channel. Therefore, we design a scheduler where in each frame, two selected relayed users are supported simultaneously through the Superposition Coding (SC) based scheme proposed in this paper. In this scheme, the messages destined to the two users are superposed in the modulation domain into three SC layers, allowing them to benefit from their high quality relayed links, thereby increasing the sum-rate. We derive the optimal power allocation over these three layers that maximizes the sum-rate under an equal rates' constraint. By integrating this scheme into the proposed scheduler, the simulation results show that our proposed SC scheduler provides high throughput and rate outage probability performance, indicating a significant fairness improvement. This validates the approach of simultaneous allocation versus orthogonal allocation in the cooperative cellular system. Copyright © 2011 The Institute of Electronics, Information and Communication Engineers.