Polynomial algorithms for a two-class multiprocessor scheduling problem in mobile telecommunications systems

In Universal Mobile Telecommunications Systems radio access, information packets of different services and users are sent across the air interface organized into radio frames. A radio frame is divided into a fixed number of time slots, different packets can share the same time slot and exactly one slot must be assigned to each packet. The packets of different services have divisible sizes and the slot capacity is limited. Quality of Service requirements set time intervals within which each packet must be scheduled. In this work, we address the problem of scheduling packets related to two different services to the time slots of a radio frame. The problem is a variant of the High-Multiplicity Multiprocessor Scheduling Problem in which there are two classes of jobs with divisible sizes, and the jobs must satisfy assignment restrictions. Two polynomial–time scheduling algorithms, maximizing the number of scheduled packets, and the weighted throughput, are provided.