In 4G and beyond 4G cellular communication systems, multi-hop relay network (MHR) plays a vital role. Improper deployment of relay station (RS) in MHR network creates some severe issues. The conventional studies on RS deployment have not considered the practical issue of link overloading. In this paper, a two-phase, fuzzy based selection and deployment scheme for RSs is proposed by considering link overloading issue. The study also analyses the trade-off between deployment budget, network throughput and overall service coverage. Simulation results show that the proposed scheme performs better than the conventional scheme. © 2016 IEEE.