This paper presents two hyper-heuristic approaches for solving a facility location problem called reliable p-median problem with at facility service (RpMF). In RpMF, service is provided to customers at the facility locations and it is closely related to the p-median problem. p-median problem is concerned with locating p-facilities while minimizing the total distance traveled by the customers to the corresponding nearest facilities and it is an -hard problem. But according to the p-median problem, it doesn’t consider the possibility of facility failures. On the other hand, RpMF assumes that facilities can fail and the customers assigned to that facility do not know about the facility failure till they reach the facility for service. So, the customers have to travel from failed facilities to other functioning facilities to receive service. RpMF deals with locating p facilities to minimize the cost of serving the customers while considering facility failures. We have proposed two multi-start hyper-heuristic based approaches that are based on greedy and random selection mechanisms to solve the RpMF. The solutions obtained through hyper-heuristics are improved further via a local search. The two proposed hyper-heuristic approaches are evaluated on 405 RpMF benchmark instances from the literature. Experimental results prove the effectiveness of the proposed approaches in comparison to the state-of-the-art approaches available in literature for the RpMF