In methods and devices for scheduling uplink transmission in a cellular radio system for a number of user equipments transmitting data over an air-interface each user equipment is associated with an individual uplink load factor. Further a cost function is formed based on the load factor for each user equipment that is to be scheduled for uplink transmission, wherein the cost function is approximated by a quadratic function. The throughput of all scheduled user equipments is maximized using a convex optimization of the sum of the individual cost functions, and the grant for uplink transmission is scheduled in accordance with the optimized cost functions.