International Telemetering Conference Proceedings / October 18-21, 2004 / Town & Country Resort, San Diego, California / The Broadcast Scheduling Problem (BSP) is a well known NP-complete problem that arises in the study of wireless networks. In the BSP, a finite set of stations are to be scheduled in a time division multiple access (TDMA) frame. The objective is a collision free transmission schedule with the minimum number of TDMA slots and maximal slot utilization. Such a schedule will minimize the total system delay. We present variations of a Greedy Randomized Adaptive Search Procedure (GRASP) for the BSP. Path-relinking, a post-optimization strategy is applied. Also, a reactivity method is used to balance GRASP parameters. Numerical results of our research are reported and compared with other heuristics from the literature.

In this thesis, we study the broadcast scheduling algorithms in a dynamic environment with set-typed data requests. We sketch the dimensions of broadcasting paradigms and build a family of Wp