Power systems are usually subjected to some changes in connections during operation, which leads to varied short-circuit levels in different parts of them and Directional Overcurrent Relays (DOCRs) may be subjected to miscoordination by changing short circuit levels. Therefore, all network topologies should be considered for coordination among overcurrent relays in a power system. Reduction of operating time of relays is highly important in a protection system. This paper uses the overcurrent relays with a time-current-voltage curve for coordination among overcurrent relays with respect to all the different topologies. This improves coordination results of the relays due to increasing number of variables and considering voltage of the relays. This paper uses a combination of Genetic algorithm (GA) and Linear Programming (LP) for improving operating time and setting current due to the increased number of constraints for coordinating the overcurrent relays. The proposed method was implemented for an 8-bus system. Optimization results show a considerable reduction in the operating time of overcurrent relays and number of miscoordination, compared to conventional relays and the conventional optimization methods. In addition, coordination among DOCRs is maintained by changing topology of network.