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:
- SIPE-2's representational language allows representation
of some constraints that cannot be expressed by other techniques.
- Resources are allocated to each line with no violation of resource constraints.
- The system can be run interactively, letting a human make
crucial, high-level decisions while the system ensures that all the
details are correctly worked out.
- Because plans are produced in minutes, various ``what-if" analyses can
be run to produce and compare alternative plans.
- The system can modify its plan in seconds or minutes in response
to unexpected occurrences; thus, significantly reducing down-time of
production lines while permitting a higher level of order fulfillment.
Surprises are ubiquitous in the factory and often quickly render
useless plans produced by linear programming techniques, since such
plans cannot be modified to respond to new situations.
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