We present a test suite of 23 instances of a preventive maintenance scheduling problem from the power industry, which we also make available online. The formulation of the problem and the suite are derived from real-world data collected recently. A first study of the landscape characteristics of these problem instances based on three different types of adaptive walk reveals a generally rugged landscape, with little global fitness-distance correlation. Initial results from a simple evolutionary algorithm shows indifferent performance compared to adaptive walks, suggesting that intensive local search may be an important component of a successful optimizer for this problem. © 2012 IEEE.