We consider a real-world problem of planning operation of locomotive maintenance depots (LMD) in operation of the Russian Railways. We are provided a 24 hours plan of locomotives arriving to the LMD. The locomotives differ in series, number of sections and maintenance duration. LMD consists of up to one buffer track and a set of access tracks, each of them ending with its own single maintenance track. Upon arrival each locomotive can be placed into the buffer for some period of time and then moved to one of the access tracks, or it can be placed directly on an access track. Each of the tracks has a limited capacity measured in locomotive sections. Each maintenance track can only service a certain set of locomotive series. The buffer track operates like a stack. The goal is to decide for each locomotive, whether it should be placed into the buffer, which access and service tracks it should be placed on, and the time intervals of its presence on each of the set racks. We consider four different objective functions to minimize: the total idle time, maximum idle time, total waiting time and makespan. We propose a dynamic programming algorithm, a constraint programming model for IBM ILOG CPLEX and a heuristic algorithm. The algorithms and the model were tested on real data for LMD configurations of the Eastern area of Russian Railways.