The IEEE 802.16j standard defines both transparent and non-transparent relay transmission mode. The present study formulates and optimizes the relay resource scheduling problem for the case of a non-transparent relay network. It is shown that the resource scheduling problem is NP-Complete. A method is proposed for optimizing the position of the zone boundary adaptively during the resource scheduling process in order to maximize the system throughput. In addition, a low time complexity algorithm designated as MRRS (multi-hop relay resource scheduling) is proposed to obtain an approximate solution for the NP-Complete scheduling problem. In the proposed algorithm, the zone boundary is adjusted adaptively in accordance with the user distribution and the channel state information in such a way as to improve the utilization of the available slots. The simulation results show that MRRS achieves a higher throughput than existing relay resource scheduling algorithms (GenArgMax and Eliminate-Repeat) with no significant loss in fairness. In addition, it is shown that the performance improvement provided by MRRS increases as the hop-count is increased. (C) 2014 Elsevier B.V. All rights reserved.