We propose a greedy heuristic and a Tabu Search type heuristic for channel block assignment subject to co-channel, adjacent channel, co-site constraints as well as restrictions on the percentage of channels in the expanded spectrum. Computational experience are presented on two Bell Mobilité cellular networks. We also study the impact of the size of the channel blocks on the quality of the networks.