In recent years the electricity sector has undergone a number of changes that all point in the direction of liberalization and decentralization of control. However, a number of technological challenges have to be addressed before the desired degree of decentralization is obtained. Currently, most of the decisions about the operation of a power system are still made in control centers in a centralized fashion. We present in this paper a distributed optimization method that allows several power plant operators to schedule preventive maintenance on their generation units in a distributed fashion. This method does not require the centralization of private data of the power plant operators (like available capacities, internal maintenance schedules, maintenance and operation costs, etc). Furthermore, the method guarantees globally optimal schedules while observing the power generation demand at all times. The problem is modeled as a constraint satisfaction/optimization problem, which is a powerful paradigm for solving numerous tasks in distributed AI, like planning, scheduling, resource allocation. The algorithm that we use is a complete method for distributed constraint optimization, based on dynamic programming. It requires a linear number of messages, whose maximal size depends on a parameter of the constraint graph, called induced width. This makes our algorithm well suited for large but loose problems. We conjecture that this method has applications in power systems well beyond this scheduling scenario.