Abstract: Recently, researchers have presented several deterministic small-world networks (DSWNs) which can be generated in a special iteration process without randomness. However, to the best of our knowledge, no one has studied the synchronizability of DSWNs up to now. In this study, we focus on the synchronizability of the edge iteration based deterministic small world network (EIB-DSWN) that was presented in 2006. Our testing results show that the EIB-DSWN has very poor synchronizability. To improve the synchronizability, we propose using the Modified Simulated Annealing (MSA) algorithm to optimize the EIB-DSWN. After MSA-based optimization, to check if the optimized network is still a kind of small-world network, we calculate its three main characteristics. It turns out that the MSA algorithm can significantly optimize the synchronizability of the EIB-DSWN under the premise of ensuring small world characteristics.