Discrete models and algorithms for packet scheduling in smart antennas

We investigate two combinatorial optimization problems arising when scheduling packets in a smart antenna. To select a maximum number of users to be simultaneously served in a given time slot, an arc-circular model is proposed and a polynomial algorithm, which searches for a maximum weight path in an appropriate acyclic graph, is presented. To partition the users so mimimize the number of time slots needed to transmit all the given packets, heuristics are developed.