The Hunter Valley Coal Chain (HVCC) consists of mining companies, rail operators, rail track owners and terminal operators, together forming the world's largest coal exporting facility. In 2008, the throughput of HVCC was about 92 million tonnes, or more than ten per cent of the world's total trade in coal for that year. The coal export operation generates around $15 billion in annual export income for Australia. As demand has increased significantly in recent years, and is expected to increase further in the future, efficient supply chain management is crucial. The Hunter Valley Coal Chain Coordinator Limited (HVCCC) was founded to enable integrated planning and coordination of the interests of all parties, thus improving the efficiency of the system as a whole. One of the many planning challenges faced by the HVCCC is that of annual maintenance planning. Different supply chain elements, such as trains, railway track, terminal equipment and load points, must undergo regular preventive and corrective maintenance, leading to significant reductions in system capacity (up to 15 per cent). However good alignment of the maintenance tasks can reduce their impact, and the HVCCC undertakes an annual process to ensure the impact of maintenance on the supply chain capacity is as small as possible. This is achieved in an iterative negotiation process between HVCCC and individual service providers. In the past, maintenance schedule optimisation was largely manual, which for the more than 1000 tasks involved is quite labour-intensive.In this paper the authors describe an approach developed at the University of Newcastle in partnership with the HVCCC to automate this schedule optimisation process. We will discuss our experience in applying exact (mixed integer programming) and heuristic techniques from mathematics and computer science to address the problem. This work is anticipated to lead to new decision-support tools for the HVCCC's capacity planning team.