We consider a weekly locomotive scheduling problem encountered at Swedish State Railways. The objective is to find cyclic locomotive schedules, which minimize operational costs while respecting maintenance and availability constraints. We present a mathematical model of the above problem. Considering the size and difficulty of this real world problem we have to settle with heuristic solution methods. We consider two alternative approaches utilizing specific problem characteristics. We comment on our computational experience with a problem with more than 2000 locomotive requests.