Production Line Scheduling in SIPE-2

Note: The plan generation time of 4 minutes specified on the following slide was on a Symbolics 3645. The same plan is now generated on a Sun Sparcstation 20 in 28 seconds.

Objective

The objective of this project was to create software for intelligent systems that are capable of helping manufacturers to form plans and schedules to meet production goals under the operating constraints of the factory, operate equipment effectively and safely, especially in unanticipated and emergency situations, and evaluate hypothetical scenarios in determining the impact of potential decisions. Though the aim of the project was to develop generic technologies applicable to a wide range of manufacturing activities, a real-world problem was implemented to demonstrate the usefulness of the approach.

Approach

SIPE-2 was applied to the problem of producing products from raw materials on process lines under production and resource constraints. A beer packaging plant exemplifies this domain. Our application involved one of the ten largest such plants in the world, and realistically incorporates most of the necessary constraints for planning a daily schedule for multiple production lines at this plant. There are over 300 products which are assembled from the ``raw materials" of cans, bottles, beer, tops, labels, wrapping, and cartons.

Physical constraints on transporting raw materials from stores inventory to the packaging line have been adequately modeled --- this involves satisfying constraints on using beer-lines to feed several production-lines from beer-tanks, as well as ensuring that all necessary raw materials are available and meet the constraints of the packaging line being used. Resources are correctly allocated to each packaging line --- the packaging lines can contend for the use of both beer-tanks and beer-lines. The system uses consumption rates to calculate the changing levels of orders, the changing availability of raw materials, and the start-time, end-time, duration, and level of production of each run and shift.

The beer in the beer-tanks has been produced in accordance with a planned fermentation cycle computed from the order backlog as it stood two weeks previously. However, to reflect the true manufacturing environment, the planning system reacts to the current demand for products and the current status of required resources: manpower, equipment, available beer, and raw materials. There is a cost involved in switching the type of beer that flows through a beer-line. The planner generates plans that utilize all lines and manpower to fill the highest priority orders while satisfying all physical constraints and minimizing waste from flushing of lines. The system does not search for an optimal plan (no cost function is available), but various search strategies could be easily implemented to compare alternative plans.

An important problem in this factory, as in most, is that production is often interrupted by unplanned events such as the unavailability of some raw material, equipment malfunction, or resource shortages. The SIPE-2 planner has causal information relating the actions in its plans and uses this information to modify plans during execution without having to replan completely. In addition, the system can interact with the user allowing him to participate in the decision-making process. This allows a human expert to formulate plans based on his knowledge and judgement in a fraction of the time it would take without the AI planning system.

Performance

SIPE-2 generates a daily plan (master schedule) for two eight-hour shifts on each of six production lines in about 4 minutes on a Symbolics 3645. The plan schedules dozens of orders (for possibly hundreds of products) with approximately 20 separate product runs (with their corresponding needs for different raw materials). To produce one such plan with no backtracking requires the generation of 1100 action and goal nodes (at all planning levels). To modify such a plan after a certain type of material becomes unavailable takes less than two minutes if only a few runs are affected. This response time makes it reasonable to consider using the planner on the factory floor to schedule daily operations and respond to new events.

The primary advantages over conventional scheduling software are the following:

Reference

D. E. Wilkins, "Can AI planners solve practical problems?," Computational Intelligence, vol. 6, no. 4, pp. 232--246, 1990.
Abstract: While there has been recent interest in research on planning and reasoning about actions, nearly all research results have been theoretical. We know of no previous examples of a planning system that has made a significant impact on a problem of practical importance. One of the primary goals during the development of the SIPE-2 planning system has been the balancing of efficiency with expressiveness and flexibility. With a major new extension, SIPE-2 has begun to address practical problems. This paper describes this new extension and the new applications of the planner. One of these applications is the problem of producing products from raw materials on process lines under production and resource constraints. This is a problem of commercial importance and SIPE-2's application to it is described in some detail.

Acknowledgements

This application was funded by the Australian Department of Industry, Technology, and Commerce. The reasearch was performed from July to December, 1988 by the Australian Artificial Intelligence Institute and the SRI International Artificial Intelligence Center. The research team was lead by Dr. David E. Wilkins
David E. Wilkins
Last modified: Sat Apr 1 14:22:41 1995