A scheduler is adapted to schedule packets or other data blocks for transmission from a plurality of transmission elements in timeslots of a frame in a communication system. In scheduling for a given frame, the scheduler initially designates each of the transmission elements as eligible to transmit one or more data blocks in the given frame, and selects from among those of the transmission elements designated as eligible at least one of the transmission elements for scheduling in a next available timeslot of the given frame. The scheduler then adjusts the eligibility status of the selected transmission element(s), and repeats the selecting and adjusting operations for one or more remaining timeslots of the given frame. The scheduler in an illustrative embodiment may be implemented in a network processor integrated circuit or other processing device of the communication system.