Small Unmanned Aerial Vehicles (UAVs) are finding a rapidly increasing number of applications in delivery, passenger transport, surveillance of assets, traffic monitoring and other industries. Apart from regulatory hurdles, low payload and range, a fundamental limitation for their large-scale implementation relate to airspace management. UAV operations are expected to occur in shared airspace with static and dynamic obstacles, including low altitude manned flight and areas of prohibitive weather. Given the large UAV fleet sizes envisioned, it becomes imperative to create airspace management heuristics that provide optimal and non-conflicting flight paths under short runtime. To this effect, we develop a dynamic airspace sectorisation algorithm that discretises the airspace into sectors. The optimal arrangement and size of airspace sectors are determined by the fleet position and direction, and change during the operation time window. A trajectory heuristic is integrated into the sectorisation algorithm that determines non-conflicting optimal paths for every vehicle, conforming to the Performance Based Navigation requirements and considering payload and range variations. The proposed methodology is applied to a UAV relief delivery operation in the aftermath of the Chi-Chi earthquake, in Taiwan. The model is compared with a single sector case and a static airspace case, where sectors are pre-determined based on the warehouse locations. Results show a substantial acceleration in runtime with minimal increase in flight-time and mission time.