Most scheduling tools are intended for operational use, to control the sequence of production in a factory on a day-to-day basis. The MOSES application described before is a good example of such an operational tool. The PLANE system described in this post is quite different, it was introduced as a strategic planning tool to estimate the resource requirements of multiple factories at Dassault Aviation over a five year horizon. Dassault is a French aircraft manufacturer, which mainly produce military fighter/strike aircraft both for the Armée de l’Air, the French air force, and for export to many countries around the world. The application was developed for the manufacture of the Mirage 2000, a cutaway illustration of which is shown below.
The aircraft is manufactured in sections (cockpit, fore fuselage, aft fuselage, wings, …) on a number of assembly lines, which, when combined, produce the finished aircraft.
It has long been known (Wright 1936) that the time required to build an aircraft decreases rapidly with the number of planes built. The improvement is attributed to the “learning curve” shown below.
Initially, the production requires a lot of manpower, as workers must become familiar with the design and the tooling. As production continues, more streamlined processes are introduced to speed up production, and the work force becomes more used to the tasks required.
For the Mirage 2000 understanding the learning curve becomes more complicated as the aircraft is produced in multiple variants. Five of the variants (B, C, D, N, 5F) are displayed in the profile below. Today’s production numbers are low enough (601 Mirage 2000 of all types have been built) that much of the production run is affected by steep changes in the learning curve.
Whenever a new type is introduced, the learning curve resets to a higher level for airframes of this type. Due to the delivery dates required, the production sequence must mix different types on the assembly lines, although the manufacturing times may vary significantly.
Ideally, one would wish to produce each aircraft just in time for the promised due date, so that inventory cost are kept to a minimum. It is especially expensive to store unfinished parts of the aircraft, as this uses up expensive jigs and requires extra storage tasks. An ideal production start date for each aircraft can be easily computed, using the estimated duration for each task based on its place in the production sequence for the type.
Unfortunately, using these ideal production start dates would require far too many resources. Much of the assembly work is controlled by skilled craftsmen, which have to be carefully trained for each new aircraft type. In addition, each airframe requires special tools and jigs, which are quite expensive, and thus only available in limited number. From the resource perspective, the ideal schedule would produce a constant number of airframes each month, over the total production run of the aircraft. But then the storage costs would be very high, and new orders could be included only at the end of the current order book.
In the actual factory, a compromise of these two cost factors is sought. Changes in the production rate (the time between starting two airframes) are possible, but must be tightly controlled. Each increase of the rate requires training new personnel with the required skills, and each decrease means that we have to find work for the work force made redundant in other parts of the company. Both increases and decreases also affect the learning curve (and thus task durations), as new people have to learn their tasks, or the remaining workforce has to cover the tasks before performed by personnel no longer available. The constraints on the manufacturing rate express how often one can change the rate, by how much, and how long we have to wait after a change before another change is possible. The cost model considers the overall resource use and the number and size of all changes over time.
The PLANE application was developed in CHIP to find the best time points when to change production rates, i.e. when to increase or decrease the workforce. A second use case was to consider the “ability to promise”, finding out the effect of adding a new potential order with given due dates to the order book.
The screen dump above shows an early version of the PLANE prototype. Each line in the Gantt chart is one aircraft, consisting of six sections. The different type variants are color-coded, and show different task durations due to different places on the learning curve for each type. At the bottom, the production rates for the different assembly lines are shown, the changes allow to match the due dates for aircraft delivery more closely. The system could find the optimal solution only for small problem instances, but good solutions were considered sufficient for planning purposes, as many details of the schedule are only approximately known.
In the full sized application, the planning task considered 250 aircraft orders on eight assembly lines. A full schedule could be generated in minutes, while the manual planning process used before took days to complete. The last Mirage 2000 was delivered on 23 November 2007 to the Hellenic Air Force.
To learn more
The initial PLANE prototype was decribed in the 1992 paper “J. Bellone, A. Chamard, C. Pradelles. PLANE – An Evolutive Planning System for Aircraft Production. In Proceedings of the First International Conference on the Practical Application of Prolog. 1-3 April 1992, London”. I was consulting for this application on some user interface and solver aspects, but the majority of the development and the complete rollout was performed by the AI programming group at Dassault. Periodic updates at the CHIP Users’ Club conferences described improvements and the status of the rollout of the tool to a number of factories.
Some work on a parallel version of the solver in ECLiPSe was presented in “Patrick Albers, Jacques Bellone: PSAP – A Planning System for Aircraft Production (Extended Abstract). CP 1996: 525-526”.
The initial paper on the learning curve in aircraft manufacturing is “T.P. Wright, Factors Affecting the Cost of Airplanes, Journal of Aeronautical Sciences, 3(4) (1936): 122-128.” A more modern study also considering effects increasing the manpower required is “C. Lanier Benkard, Learning and Forgetting: The Dynamics of Aircraft Production, The American Economic Review, Vol. 90, No. 4 (Sep., 2000), pp. 1034-1054″