We investigate the problem of scheduling in OFDM-based multihop relay networks with special emphasis on IEEE 802.16j based WiMAX networks. In such networks, scheduling is the problem of determining the user to be serviced at a given instant of time on a given sub-channel, while possibly exploiting multiuser and frequency diversities opportunistically in optimizing the desired objectives. In [1], the authors propose a heuristic opportunistic scheduling algorithm, GenArgMax, for such networks. In this paper, we study the drawbacks in algorithm GenArgMax. We present new opportunistic MAC scheduling algorithms that remedy these drawbacks. We compare performance of the proposed algorithms using detailed discrete event simulation based studies. Results show that the proposed algorithms improve the system throughput by over 40%, for 40-user 3-hop networks. ©2009 IEEE.