Optimization of operating time of relay in an interconnected network is essential to reduce damage by reducing fault clearing time and at the same time enhance selectivity of the relay by employing directional feature. The relays connected in network function properly during normal as well as abnormal condition. The prime feature of this paper is to obtain minimum Time Dial Setting (TDS) for the relays in considered network using Firefly Algorithm. The said algorithm result is compared with Linear Programming technique and the implementation on the network is simulated in MATLAB. The unprecedented feature of this paper is application of nature inspired algorithm to one of the most important problem of optimization in the field of power system protection.