This paper presents a new method for coordination of directional overcurrent relays to reduce the discrimination time of the primary and backup relays, by using nondominated sorting genetic algorithm-II (NSGA-II). In order to achieve a reliable protective system, it is necessary to find a solution to avoid having large discrimination times, in addition to coordination time interval (CTI). The novelty of the paper is to reduce the discrimination time of the primary and backup relays and simultaneously reduce the operating time of primary and backup relays, by introducing a new method. In contrast to the conventional intelligent methods, the proposed method does not require weighting factors for conversion of multi-objective function into an equivalent single objective function. The effects of both near and far-end faults are considered to solve the proposed problem formulation. Also, various overcurrent relays characteristics are considered within the program to select the best of them for each relay by optimization algorithm. The proposed method is implemented in three different test cases, i.e. three, eight and IEEE 30-bus network. The results are compared with previously proposed methods.