Optimal selection of safety measures (SMs) is a challenging task for safety managers due to its importance, complexity, and incapability of traditional approaches in considering all the aspects of SMs optimal selection. Sophisticated mathematical models can be used to overcome the limitations of traditional approaches. However, setting the objective functions while considering their priorities as well as possible synergistic effects of the SMs on the hazards are still among the main concerns in the development and application of mathematical models. The present study is aimed at developing a methodology to optimize the SMs selection while addressing the aforementioned challenges and considering both the budget and the risks. To do so, first the Pareto set of the solutions is obtained by NSGA-II technique - a multi-objective genetic algorithm technique - where a lexicographic model is used to select the optimal solution from the Pareto set based on the priority of the objective functions. A pessimistic strategy is used to account for the synergistic effects and the overlaps between the selected SMs. Two mathematical models are developed to represent different policies in optimal SMs selection in a gas wellhead and surface facility. The results show a notable difference between the two policies, indicating the importance of setting proper objective functions in multi-objective optimization problems. The results also show that the methodology is able to effectively satisfy different safety management policies and constraints with no need for much extra information except the cost and impact of SMs on the hazards' risk. (C) 2019 Institution of Chemical Engineers. Published by Elsevier B.V. All rights reserved.