Aircraft structural maintenance is one of the critical operational activities to guarantee continued airworthiness. A proper maintenance strategy developed in design phase can save significant operational cost. Currently, the MSG-3 document and deterministic methodologies are widely applied as guidance to make scheduled maintenance tasks but face challenges with composite structures and structural health monitoring (SHM) technologies. The research objective is to determine flexible and cost-effective maintenance tasks for aircraft structures while maintaining an acceptable safety level. Two key parameters in scheduled maintenance, i.e. the inspection interval and the repair/replace threshold are addressed. Composite airframes are particularly investigated and damage characteristics are obtained. Non-deterministic methodologies are proposed to optimize maintenance tasks considering uncertainty. The integration of SHM into scheduled maintenance and its influence on scheduled maintenance is further studied.