We present an aircraft maintenance scheduling problem, which requires suitably qualified staff to be assigned to maintenance tasks on each aircraft. The tasks on each aircraft must be completed within a given turn around window, so that the aircraft may resume revenue earning service. This paper presents an initial study based on the application of an Evolutionary Algorithm to the problem. We benchmark the algorithm on 60 generated problem instances to demonstrate the underlying representation and associated genetic operators. Future work to follow from this study will encompass applying these techniques to real-world problem instances.