Unlike centralized versions, a distributed self-healing system (SHS) for electrical distributed systems is less vulnerable to single-point failures (or attacks), requires less information from the agents, and is more scalable. However, optimality is challenging to achieve because binary variables are used in the modelling of the distributed service restoration problem. To deal with this challenge, this paper proposes an enhanced alternating direction method of multipliers (ADMM)based algorithm used to developed a fully distributed SHS in electrical distribution networks. Hereby, three ADMM-based heuristics are executed in parallel to improve the chances of obtaining a feasible solution. However, if none of the heuristics converge within given reasonable time, the proposed distributed SHS uses a basic restoration plan that is feasible in terms of topology and operational constraints. Results using the IEEE 123node system show that the proposed distributed SHS is reliable and it always provides a feasible solution.