Highway infrastructure elements, such as signs, guardrails, structures, and pavements, deteriorate over time because of weather, accidents, daily wear and tear, and other factors. To keep them functional and operational, the elements require periodic maintenance. In the absence of an optimization model that can optimally allocate the annual maintenance budget for needed maintenance, it is often difficult to secure adequate funding for such activities. A mathematical model is developed; it evaluates the condition of elements, considers a budget constraint, and suggests the optimal maintenance schedule over a specified period of time. A genetic algorithm has been used to solve the model. The model considers a parabolic function over time to represent deterioration of the elements as well as rehabilitation expenses. The extent of rehabilitation at a given time is considered as dependent on the present condition and amount of deterioration. Also, threshold values for level of deterioration are considered as a check for the minimum condition before rehabilitation is warranted. With inputs such as deterioration levels, rehabilitation costs, threshold deterioration levels, and annual budget, the model can give the optimum maintenance schedule of the elements over a specified time period as an output. The approach is illustrated through a numerical example.