AD-A282 968 MICRO-OPPORTUNISTIC SCHEDULING: THE MICRO-BOSS FACTORY SCHEDULER Norman Sadeh CMU-RI-TR-94-04 '-kf94-24169 The Robotics institute Carnegie Mellon University Pittsburgh, Pennsylvania 15213 To appeari n "IntelligentS cheduling" book edited by M. Zweben and M. Fox, Morgan Kaufmann, 1994 DTIC ~ ELECTEI Copyright © 1994 Sadeh - D'flS QtJAI~f I~l8P2CTED5 b* This research was supported, in part, by the Defense Advanced Research Projects Agency under contract #F30602-9I-F-0016 and in part by grants from McDonnell Aircraft Company and Digital Equipment Corporation. 94 7 29 090 SShe akeOn.. m PWujr* Pewh(cid:127) IS2L%4Mg 22 July 1994 Defense Technical Information Center Cameron Station Alexandria, VA 22314 RE: Report No. CMU-RI-TR-94-04 Permission is granted to the Defense Technical Information Center and the National Technical Information Service to reproduce and sell the following report, which contains information general in nature: Norman Sadeh Micro-OpportunisticS cheduling: The Micro-Boss Factory Scheduler Yours truly, Marcella L. Zaragoza Graduate Program Coordinator enc.: 12 copies of report Table of Contents 1. Introduction I 1.1. The Production Schedulg Problem 1 1.2. A Micro-Opportunistic Approach to Production Schedulng 3 13. Paper Outle 5 2. A Micro-opportunistic Search Procedure 6 2.1. A Deterministic Scheduling Model 6 "L2.2 Overview of the Search Procedure 9 2.3. Look-Ahead Analysis in Mkro-Bou 12 2.3.1. Optimizing Critical Conflicts First 12 2.3.2. Step 1: Reservation Optimization within a Job 13 23.3. Step 2: Building Demand Profiles to Identify Critical Resourceinme Intervals 13 2.4. Operation Selection 16 2.5. Reservation Selection 19 3. A Small Eample 20 4. Reactive and Interactive Scheduling in Micro-Boss 24 4.1. Reactive Scheduling and Control Issues 24 4.2. Interactive Scheduling with Micro-Baer 25 5. Performance Evaluation 28 5.1. Comparison Against Combinations of Priority Dispatch Rules and Release Policies. 29 5.2 Comparison Against Coarser Opportunistic Scheduling Procedures 31 5.3. Evaluating the Impact of Using Biased Demand Profiles 32 6. Concluding Remarks 34 Acknowledgement 37 References 39 AooessioU For IITIS GRA&IL DTIC TAB [ ust f ioatin Unannoncoed Ditrib ti ,,o mE,. AvailabilitY Oodes vail and/or Dist Spec ial II V !11 List of Figures Figure 1: A simple job shop problem with four jobs. Each node is labeled by the operation that It 8 represents, its duration, and the resource that it requires. Figure 2: An example of an unscheduled operation that absolutely needs a resource/time interval. 12 2 2 Figure 3: Start time distribution a2 (r) for operation O2 In the Initial search state for the problem 14 defined In Figure 1. Figure 4: Building R 's aggregate demand profile In the initial search state. 15 2 Figure 5: Aggregate demands in the Initial search state for each of the five resources. 17 Figure 6: Operation selection In the Initial search state. 18 Figure 7: An edited trace 21 Figure 8: Gantt chart of the final schedule produced by Micro-Boss. 23 Figure 9: The Micro-Boss user Interface allows for Interactive manipulation of schedules. By 27 Interleaving both manual and automatic scheduling decisions, saving and comparing alternative schedules, the user can easily assess different trade-offs and locally Impose ad hoc constraints or preferences that are not easily amenable to representation in the computer model. Figure 10: Comparison of Micro-Boss and the best of 39 combinations of priority dispatch rules 29 and release policies under 8 different scheduling conditions (10 problems were generated under each condition). Figure 11: Comparison of Micro-Boss and two coarser opportunistic schedulers. 31 Figure 12: Comparison of the cost of the schedules produced by Micro-Boss and a variation of the 32 system that used unbiased demand profiles. IV v List of Tables Table 1: Earledt acceptable release dates, due dates, latest acceptable completion dates and 9 m-ria cost Table 2: Characteristics of the eight problem sets. 28 Abstract A major challenge for research in production management is to develop new finite-capacity scheduling techniques and tools that (1) can account more precisely for actual production management constraints and objectives, (2) are better suited for handling production contingencies, and (3) allow the user to interactively manipulate the production schedule to reflect idiosyncratic constraints and preferences not easily amenable to representation in the computer model. This paper describes Micro-Boss, a decision-support system for factory scheduling currently under development at Carnegie Mellon University. Micro-Boss aims at generating and maintaining high-quality realistic production schedules by combining powerful predictive, reactive, and interactive scheduling capabilities. Specifically, the system relies on new micro-opportunistic search heuristics that enable it to constantly revise its scheduling strategy during the construction or repair of a schedule. These search heuristics are shown to be more effective than less flexible scheduling techniques proposed in the Operations Research and Artificial Intelligence literature. 1. Introduction In a global market economy, the need for cost-efficient production management techniques is becoming more critical every day. In contrast with this need, current production management practice is too often characterized by low levels of due date satisfaction, high levels of inventory and, more generally, a state of chaos in which the computer systems that are used to provide managerial guidance do not accurately reflect the current state of affairs, because they rely on oversimplified and rigid models of the production environment. A major challenge for research in this area is to develop new production management techniques and tools that (1) can account more precisely for actual production management constraints and objectives, (2) are better suited for handling production contingencies, and (3) allow the user to interactively manipulate the production schedule to reflect idiosyncratic constraints and preferences not easily amenable to representation in the computer model. This paper describes Micro-Boss, a decision-support system for factory scheduling currently under development at Carnegie Mellon University. Micro-Boss aims at generating and maintaining high-quality realistic production schedules by combining powerful predictive, reactive, and interactive scheduling capabilities. Specifically, the system relies on new micro-opportunistics earch heuristics that enable it to constantly revise its scheduling strategy during the construction or repair of a schedule. These search heuristics are shown to be more effective than less flexible scheduling techniques proposed in the Operations Research and Artificial Intelligence literature. 1.1. The Production Scheduling Problem Production scheduling requires allocating resources (e.g., machines, tools, human operators) over time to a set of jobs while attending to a variety of constraints and objectives. Typical constraints include e functional constraints limiting the types of operations that a specific resource can perform * capacity constraints restricting the number of jobs a resource can process at any given time " availability constraints specifying when each resource is available (e.g., number of shifts available on a group of machines) " precedence constraintse xisting between operations in a job, as specified in the job's process routing *processing time constraints specifying how long it usually takes to perform each operation * setup constraints requiring that each machine be in the proper configuration before 2 performing a particular task (e.g., proper sets of fixtures and tools) time-bound constraints specifying for each job an earliest acceptable release date before which the job cannot start (e.g., because its raw materials cannot arrive earlier) and a due date by which ideally it should be delivered to a customer Some of these constraints must be satisfied for a schedule to be valid (so-called non-relaxable or hard constraints). For instance, milling operations can only be performed on milling machines. Other groups of constraints are not always satisfiable and might need to be relaxed (so-called relaxable or soft constraints). For instance, due date constraints often need to be relaxed for a couple of jobs because of the limited capacity of the production facility. Availability constraints are another example of constraints that can be relaxed, by either working overtime or adding extra shifts. A good schedule is one that satisfies all hard constraints while selectively relaxing soft constraints to maximize performance along one or several metrics. Two factors that critically influence the quality of a schedule are due date satisfaction and inventory levels. Missing a customer due date can result in tardiness penalties, loss of customer orders, delayed revenue receipts, etc. Inventory costs include interests on the costs of raw materials, direct inventory holding costs, interests on processing costs, etc. One often distinguishes between in-process inventory costs (also referred to as work-in-process inventory costs) and finished-goods inventory costs. Work-In-Process (WIP) inventory costs account for inventory costs resulting from orders that have not yet been completed, and finished-goods inventory costs result from completed orders that have not yet been shipped to customers. Manufacturing contingencies such as machine breakdowns, late arrivals of raw materials, and variations in operation durations and yields further complicate production scheduling. In the face of contingencies, schedules need to be updated to reflect the new state of affairs. The sheer size of most factory scheduling problems precludes the generation of new schedules from scratch each time an unanticipated event occurs. In fact, most contingencies do not warrant such extreme actions and are best handled by repairing a portion of the existing schedule [3]. As schedules are optimized at a more detailed level, they can also become more sensitive to disruptions and require more frequent repairs. In general, there is a limit to the amount and detail of information that one can reasonably expect to represent in a computer model. For instance, a worker's preference for performing more demanding tasks in the morning might not be worth storing in the computer model and, instead, might be best accounted for by allowing the end-user to interactively manipulate the schedule. Even under idealized conditions such as simplified objectives (e.g., minimizing total tardiness or maximizing throughput) and deterministic assumptions, scheduling has been shown to be an NP-hard problem [12, 14, 11]. Uncertainty further adds to the difficulty of the problem, and makes it even more impractical to look for optimal solutions. Instead, practical approaches to production scheduling are heuristic in nature. The next subsection briefly reviews earlier