The network capacity has to be maximized to support the ever-increasing data traffic demand. One of thepotential outcomes to enhance the network capacity is to enhance the spectral efficiency per unit area by expandingthe serving node densities. This is unreasonable on account of present Macro evolved node B (eNB) for which siteacquisition is expensive. The idea of heterogeneous network (HetNet) and multi-hop relay (MHR) are extremely prominentin long-term evolution (LTE) standard, where small cells are deployed along with Macro cell. Small cells aremore suitable solution for the coverage and traffic issues experienced by Macro cell users. Unfortunately, HetNetdeployment is not specified in any of the standards. The network operators have been managing tremendous investmentsfor cellular infrastructures. Because of the high cost and lack of radio resources, a precise and productive HetNetdeployment seems uttermost important. In this work, a flexible four-stage fuzzy logic-based HetNet deployment schemeis proposed, which deploys mix of Macro-eNB, Micro-eNB and relay station (RS) by considering capacity, coverage andcost factors. The proposed scheme identifies the required number of eNBs, their types and deployment locations tooffer the expected coverage in a cost-effective way. The simulation results demonstrate that our proposed scheme is moreflexible and offers improved performance in terms of system cost and power ratio than the conventional HetNet deploymentschemes. © 2016, King Fahd University of Petroleum & Minerals.