Recently, social interest in the deteriorated bridges and infrastructure has been increasing. Also, studies on performance prediction and maintenance decision making of structures are underway. In this study, it was proposed an algorithm to create an optimal maintenance scenario that takes into consideration the relationship between the members of bridge that affect each other, rather than the conventional maintenance that is focused on single members of the bridge. Since maintenance scenario creation is discrete in terms of time and cost. So in this study, it is used a genetic algorithm. Each member of bridge has a subordinate relation that takes into account member damage transitions effect and the elimination of duplication maintenance cost, which was established through the Korean bridge maintenance manual and expert opinion. In order to predict the performance change of each member, the algorithm used the condition prediction model of each member of the bridge, which was created by multiple regression analysis based on the actual bridge case. Also, it used the maintenance cost model of members for cost estimation, it has created and applied it through actual maintenance case analysis. The constraint of the algorithm is set to the minimum maintenance level of the bridge by the bridge administrator. And, it was conducted the case study about real bridge model using the optimal maintenance model, analyzed the cost-effect and made maintenance scenario.