One of the most important things to consider before constructing a railway is the train operating program. However, the analysis of the operating program based train schedule in the railway planning stage is carried out mainly on the basis of the intuitive experiences of the planner, and the optimization of the train schedule under various conditions is not properly considered. This study analyzes the optimization of heterogeneous train scheduling structures with minimizing the weighted scheduled waiting time and with the decision of Subsidiary Main Track (SMT) for overtaking of high-speed trains on the railway line. As a way for analyzing the Optimal Train Schedule (OTS) under constraint conditions, the genetic algorithm is used. The genetic algorithm is widely applied to various optimization and decision-making problems in engineering, natural sciences, business administration, and social sciences. The proposed method can examine train schedules for more scenarios, apply quantitative evaluation criteria, and review concrete infrastructures in comparison to the existing empirical method used in South Korea.