The IEEE 802.16 mesh network is a promising next-generation wireless backbone network. In such a network, setting the holdoff time for nodes is essential to achieving good performances of medium-access-control-layer scheduling. In this paper, we propose a two-phase holdoff time setting scheme to improve network utilization. Both static and dynamic approaches of this scheme are proposed, and their performances are compared against those of the original schemes. Our simulation results show that both approaches significantly increase the utilization of the control-plane bandwidth and decrease the time required to establish data schedules. In addition, both approaches provide efficient and fair scheduling for IEEE 802.16 mesh networks and generate good application performances.