In air traffic management, a fundamental decision with large cost implications is the planning of future capacity provision. Here, capacity refers to the available man-hours of air traffic controllers to monitor traffic. Airspace can be partitioned in various ways into a collection of sectors, and each sector has a fixed maximum number of flights that may enter within a given time period. Each sector also requires a fixed number of man-hours to be operated; we refer to them as sector-hours. Capacity planning usually takes place a long time ahead of the day of operation to ensure that sufficiently many air traffic controllers are available to manage the flow of aircrafts. However, at the time of planning, there is considerable uncertainty regarding the number and spatiotemporal distribution of nonscheduled flights and capacity provision, the former mainly due to business aviation, and the latter usually stemming from the impact of weather, military use of airspaces, etc. Once the capacity decision has been made (in terms of committing to a budget of sector-hours per airspace to represent long-term staff scheduling), on the day of operation, we can influence traffic by enforcing rerouting and tactical delays. Furthermore, we can modify which sectors to open at a given time (the so-called sector-opening scheme) subject to the fixed capacity budgets in each airspace. The fundamental trade-off is between reducing the capacity provision cost at the expense of potentially increasing displacement cost arising from rerouting or delays. To tackle this, we propose a scalable decomposition approach that exploits the structure of the problem and can take traffic and capacity provision uncertainty into account by working with a large number of traffic scenarios. We propose several decision policies based on the resulting pool of solutions and test them numerically using real-world data.