The locomotive assignment problem is to provide at minimum cost sufficient motive power to pull all the trains of a time tabled schedule. Optimization methods for large scale problems are based on multi-commodity flow models with additional restrictions, solved on a rolling horizon. Branch-and-bound strategies are used to find integer solutions. When there is an insufficient number of locomotives, some companies rent additional units while others prefer to postpone train departures. In this paper, we propose a method that finds a feasible solution by delaying the departure of some trains, according to their types. The numerical results using data from the company CN North America show that with a total of about 38 hours of delay time, all the train requirements could be satisfied for a one-week planning problem involving 1988 train segments. When the train requirements are satisfied, the cost penalties associated with undercovering are significantly reduced, and consequently, the integrality gap is decreased. In our numerical experiments, this gap decreases by 2% on average.