WiMAX Cellular Networks with Multi-hop Relays(MR), standardized as IEEE 802.16j networks, have been proposed for the improvement of overall throughput by providing last mile high speed broadband service to the users. The scheduling algorithm at Base Station(BS) plays a vital role in optimal resource allocation. In Queue aware scheduling, Concurrent Transmission Scenarios(CTS) are identified based on high back pressure links, which are used as input for linear programming model that determines the transmission schedules to maximize the overall throughput with simultaneous transmissions over Independent Links(IL). As shown in the results of Queue aware scheduling algorithm, the increase in the number of Concurrent Transmission Scenarios, improves the throughput and reaches a steady state after a level because of the limited number of independent links. In this paper, the installation of Directional Antennas at Base Station(BS), Relay Stations(RS) is proposed and studied the impact of increase in independent links, so as the concurrent scenarios with Directional Antennas, and observed some improvement in throughput. Simulation results showed that the proposed Queue aware scheduling with Directional Antennas outperforms even when the Mobile Stations(MSs) are at the edge of the cell coverage.