Scheduling problems are common in a wide range of real-world industries and strategies for tackling them can impact on profits significantly. The careful planning and precise timing of industrial events and processes can maximize the utilization of resources, improve efficiency and reduce costs. One important type of scheduling problem from the domain of maintenance planning is the Generator Maintenance Scheduling Problem (GMSP) in the power industry. This thesis makes three broad contributions. First, we introduce a set of 23 real-world instances of the problem of different characteristics and sizes, based on data collected from industry in Saudi Arabia. We show that the fitness landscapes of these instances are rugged and full of relatively poor local optima. Our initial experiments to optimize the instances using a simple evolutionary algorithm and some hill-climbers reveal the dominance of local search for this problem, and suggest that effort be concentrated on the development of more advanced local search algorithms. Secondly, we turn our attention to ensemble problem solving, another promising direction, and propose the use of selection methods (selectors) to evaluate and choose the constituent algorithms of algorithm portfolios. These selectors range in intricacy and the computational effort they require. We show that a selector based on "racing" methods from the metaheuristic tuning literature appears to offer the best trade-off between performance and cost of selection. Finally, we propose several operators for an Iterated Local Search (ILS) algorithm for GMSP taking close account of the problem constraints. To improve performance, we propose extensions to the basic ILS design. These include an ILS with restart strategy, an ILS with delta evaluation implementation, an ILS hybrid with a variable neighbourhood descent algorithm, and a portfolio of ILSs. Results show a superior and consistent performance of the portfolios in a smaller number of evaluations (especially when using communication between constituent components) compared to the performance of individual constituent algorithms.