Overview
Project Motivation
Project Objectives
In a recent customization effort for the scheduling of the Printed Wiring Assembly area at Raytheon's Andover manufacturing facility, Micro-Boss was shown to simultaneously improve due date performance by more than 50 percent, reduce leadtimes by 55 to 60 percent, and reduce inventory by 20 to 30 percent depending on load conditions. The system is now undergoing customization for a large and highly dynamic machine shop at the same facility in the context of the IP3S project. The Micro-Boss scheduling heuristics have also been customized by Carnegie Group to solve commodity distribution planning and scheduling problems for the US Army, further demonstrating the versatility of this approach.
Researchers
Micro-opportunistic scheduling generalizes bottleneck scheduling approaches, which have been shown to produce higher quality schedules than traditional scheduling approaches by first optimizing the scheduling of bottleneck resources. Rather than assuming the presence of a single global bottleneck that spans the entire scheduling horizon, micro-opportunistic scheduling continuously monitors resource contention during the construction or revision of a schedule and constantly redirects its optimization effort towards the bottleneck that is currently the most critical. The ability of micro-opportunistic scheduling techniques to constantly redirect their optimization effort has been shown to yield significant improvements in due date, leadtime and inventory performance over traditional bottleneck scheduling approaches across a broad range of load conditions.
Manufacturing companies are faced with an increasingly fragmented and volatile market place. They are under continuous pressures to reduce inventories and leadtimes while improving on-time delivery. As a result, we are witnessing a shift from make-to-stock to assemble-to-order, make-to-order, and even engineer-to-order practices. Traditional production scheduling tools and techniques such as MRP/MRP-II systems, Kanban, or traditional finite capacity scheduling tools lack the functionalities required to support effective operation under these more demanding conditions.
Micro-Boss is a dynamic finite capacity scheduling tool developed at Carnegie Mellon University to support efficient just-in-time operation in complex manufacturing environments subject to rapidly changing conditions. Micro-Boss improves over commercially available scheduling tools in a number of key areas:
Project Status
Micro-Boss supports powerful and versatile modeling functionalities that make it possible to capture the complexities of a wide variety of manufacturing environments (e.g., operations with multiple resource requirements, overlapping operations, non-linear process routings, resources subject to different shift patterns, multiple capacity resources, complex setups). In contrast to other finite capacity scheduling tools, Micro-Boss's just-in-time model allows for jobs with different tardiness and inventory costs (both work-in-process and finished-goods inventory costs). In fact, in Micro-Boss, any operation can introduce its own marginal inventory costs.
Micro-Boss implements a new approach to building schedules called micro-opportunistic scheduling. The ability of micro-opportunistic scheduling techniques to constantly redirect their optimization effort has been shown to yield significant improvements in due date, leadtime, and inventory performance over traditional bottleneck scheduling approaches across a broad range of load conditions.
Micro-Boss is not just capable of constructing high quality schedules for complex manufacturing environments. It also supports powerful reactive techniques that enable it to quickly repair schedules in the face of contingencies such as machine breakdowns or new order arrivals.
Micro-Boss also supports a wide range of what-if analysis functionalities, enabling the user to quickly evaluate alternative scheduling decisions by saving, restoring, and comparing partial and complete scheduling solutions and interleaving manual and automatic scheduling decisions.
In the context of IP3S, a joint project with Raytheon, our team is developing a flexible blackboard-based architecture to support the integration of Micro-Boss with process planning modules. The resulting system will be initially deployed and evaluated in a large machine shop at Raytheon's Andover facility. This is a facility where about 50% of incoming orders are for parts that require the generation or revision of process plans.
Our team is also working with Raytheon to develop multi-facility scheduling functionalities that will make it possible for Micro-Boss to support tight coordination across the supply chain.
Micro-Boss has been compared against a number of other techniques, including dispatch-based techniques and various neighborhood search procedures. In a comparison against the best of a set of 39 combinations of dispatch rules and release policies (i.e., taking the best of the 39 schedules produced by each of these combinations and comparing against the schedule obtained by Micro-Boss), Micro-Boss was shown to simultaneously improve due date performance by about 20% and inventory by about 23%.
Collaborators
Relevant Publications
Please note the links to select gzipped Postscript and PDF files:
1996
Norman M. Sadeh and Mark S. Fox.
Variable and Value Ordering Heuristics for the Job Shop Scheduling Constraint Satisfaction Problem.
Artificial Intelligence, 86, 1996, pp. 1-41.
Earlier versions of this paper appeared as CMU Robotics Institute Technical
Reports CMU-RI-TR-95-39 and CMU-RI-TR-91-23.1995
Norman M. Sadeh, Katia Sycara, and Yalin Xiong.
Backtracking Techniques for the Job Shop Scheduling Constraint Satisfaction Problem.
Artificial Intelligence, 76, 1995, pp. 455-480.
Special Issue on Planning and Scheduling.
Earlier versions of this paper appeared as CMU Robotics Institute Technical
Reports CMU-RI-TR-94-31 and CMU-RI-TR-92-06.
2 pages
(158 Kbytes)
Norman M. Sadeh.
Micro-Boss: Dual-Use ARPI Scheduling Technology Helps Improve Manufacturing Performance.
IEEE Expert, February 1995.1994
Norman M. Sadeh.
Micro-Opportunistic Scheduling: The Micro-Boss Factory Scheduler.
In Intelligent Scheduling, edited by Mark S. Fox and Monte Zweben,
chapter 4, pp. 99-135.
San Francisco: Morgan Kaufmann, 1994.
Also available as CMU Robotics Institute Technical Report CMU-RI-TR-94-04.
Norman M. Sadeh.
Micro-Boss: Towards a New Generation of Manufacturing Scheduling Shells.
Proceedings, ARPA/Rome Laboratory Knowledge-based Planning and
Scheduling Initiative, Tucson AZ, February 1994, pp. 191-203.1993
Norman M. Sadeh.
Micro-Boss: A Micro-Opportunistic Factory Scheduler.
Expert Systems with Applications, 6(3), July-September 1993, pp. 377-392.
Special Issue on Scheduling Expert Systems and their Performances.
Norman M. Sadeh, Shinichi Otsuka, and Robert Schnelbach.
Predictive and Reactive Scheduling with the Micro-Boss Production Scheduling and Control System.
Proceedings, IJCAI-93 Workshop on Knowledge-based Production Planning,
Scheduling, and Control. Chambery France, August 1993.1991
Norman M. Sadeh and Mark S. Fox.
Micro vs. Macro-Opportunistic Scheduling.
In Computer Applications in Production and Engineering,
edited by G. Doumeingts, J. Browne, and M. Tomljanovich, pp. 651-658.
North Holland: Elsevier, 1991.
Norman M. Sadeh.
Look-ahead Techniques for Micro-opportunistic Job Shop Scheduling.
PhD Thesis, School of Computer Science, Carnegie Mellon University, Pittsburgh PA.
March 1991.
Available as CMU Computer Science Technical Report CMU-CS-TR-91-102.
