CHIP Application at Dassault Aviation
This paper is aimed at showing how Constraint Logic Programming can be effectively used to implement advanced decision support systems for planning and scheduling. Three such systems are presented by Dassault Aviation, the French aircraft manufacturer. Two of these systems are installed and being tested on-site and the third is a feasibility prototype.
Production rate and assembly lines:
Aircraft sections are produced on assembly lines, each consisting of a sequence of production steps. A production step is composed of one jig (work station), or several jigs in parallel, on which sets of operations are performed. Assembly lines have to respect the production rate, i.e. the number of air-craft to be produced per month. Sections have to be moved from a production step to the next at a pace determined by the production rate. This has critical implications on the organization of the assembly line and on the production planning process. The assembly lines are designed and built for a nominal production rate, and have to be adapted for significant rate changes. This was so far done manually. For production planners, this restricts the possible production rate transitions and induces a cost for each production rate change. The planning process itself being manual, the completion of a full long-term production plan took several days.
A need for specific tools:
Constraint Logic Programming (CLP)
Dassault Aviation concluded that there are no generic tools able to handle the specific constraints occuring in its assembly lines. This finding motivated the in house development of Decision Support Systems (DSS) for production planning (PLANE), and subsequently for assembly line design and organization (COCA).
CLP was chosen since this technology is aimed at solving complex problems which are likely to evolve, due to its unique combination of declarative programming and powerful constraint handling. This technology was also used to develop a scheduler in a feasibility study in primary-part production, another critical manufacturing phase (MADE).
The CLP language chosen is COSYTEC's CHIP V4 which features very powerful constraints suitable for complex resource allocation problems. In addition, its object layer and integrated graphical tools made it very suitable for handling evolving situations and building highly interactive systems.
Planning and Scheduling Aircraft Manufacture at Dassault Aviation
PLANE : PLANification Evolutive
PLANE is an aircraft production planning DSS, which schedules production for the next few months or years. Typical figures are: hundreds of aircraft, about 20 manufacturing sections, up to 30 assembly lines.
PLANE uses permanent production parameters for the various aircraft types (cycle durations, assembly lines of sections, precedence constraints between sections) and the assembly lines (production rate constraints), as well as planning data : aircraft orders, work in progress, assembly line's current rates. The objective is to find schedules that respect aircraft due-dates, and balances fuselage storage against the number and magnitude of the production rate changes.
The users are planning experts. Interactivity has been a requirement, since a fully automatic system cannot allow for all aspects. The basic resolution mechanism consists in modifying (or not) the production rate at certain aircraft ranks, determined by an intensive precomputation based on the due date profile.
PLANE has been in use at the Argenteuil factory since mid '94. Its robustness and interactivity are being improved. Developed over about three man-years, the system should be fully operational by mid '95 and its extension to the company level is being considered.
COCA : Conception et Organisation de Chaines d'Assemblage
COCA is a assembly line design and organization DSS. The project was launched in 1993, based on data from the Argenteuil factory and current focus is on design. The aim is to define the successive production steps and assign operations to them in such a way that a satisfactory compromise is reached between the overall cycle duration and resource requirement and occupation. The problem constraints are related to precedence between operations, accessibility of fuselage areas, production rate feasibility, the maximum number of simultaneous operations and resource limitations (e.g. jigs, labour).
Capacity and area availability constraints are handled by the cumulative constraint of CHIP V4. Several dynamic heuristics are used, based on the tasks' start-date domains and on the precedence matrix. They produce satisfactory solutions in a few minutes.
Manually, only coarse grain operations can be handled and adaptation to rate changes was done empirically on the shop-floor. COCA V.1, used by assembly line designers since mid-94, handles small grain tasks. It is operated in an iterative way and allows feed-back to operation definition. Developed over about 18 man-months, COCA will to be fully operational in 1995.
MADE : Module d'Aide à la Décision pour l'Engagement
MADE is a work order release-orientated, designed for a flanging workshop in Argenteuil, weekly producing thousands items of several hundred types, in small batches.The manufacturing process consists of milling, cleaning, annealing, flanging, quenching and finishing, but the particular sequence of operations varies greatly with the part types. The milling and flanging work stations feature complex part grouping constraints.
A first scheduler prototype was completed in 1992, but was considered as too detailed and too stringent for human operators. The current feasibility demonstrator is based on a simpler workshop model and a FIFO flow rule. It computes the part groupings for the milling machine to ensure the right workloads on the work stations. The main user is the workshop manager. The system has three main functions: static analysis of the current situation, mid-term analysis based on work flow simulation, and work order release computation (the constraint-solving core), which includes a part layout module.
The problem is modelled as a bin-packing problem, one bin per work station: to each day is associated a bin whose height corresponds to the station's daily capacity. The objective is to pack the tasks as densely as possible in the bins, while respecting due dates. This is implemented by CHIP V4's cumulative constraint. Strategies derived from classical bin-packing methods are used and compact solutions are obtained. When the problem is overconstrained, specific constraints to be relaxed are proposed to the user. If these are not feasible, the system switches to simulation. In that case, the main benefit resides in being able to estimate the overall delay and to report to higher levels of decision. Each demonstrator took about a man-year to specify and develop.
Further development is currently under discussion.
DASSAULT concludes that CHIP is highly adequate for handling complex planning and scheduling problems, where prototyping is necessary to build the right systems, where end-user interaction is standard practice and where contexts typically evolve over time.
Development efforts are found to be relatively small, typically of the order of two-three manyears, including significant prototyping and (re-) specification phases.
Constraint Logic Programming Decision Support Systems for Planning and Scheduling Aircraft Manufacturing at Dassault Aviation, by J.Bellone, A.Chamard, A.Fischler, in the Third International Conference on the Practical Applications of Prolog, Paris, April 1995.
Authors: J. Bellone, A. Chamard and A. Fischler Département Intelligence Artificielle & Informatique Avancée, DASSAULT AVIATION, 78, quai Marcel Dassault, 92214 Saint-Cloud, FRANCE.
Acknowledgments: Work on MADE is partly supported by ESPRIT Project 5291 CHIC. PLANE is by EP 6708 APPLAUSE.