SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Artificial Intelligence Techniques <s> Abstract Uncertainties in the production environment and modelling limitations inevitably result in operational deviations from schedules generated using predictive models. A production control mechanism monitors the environment for exceptions, and takes corrective actions, with the objective of adhering closely to planned objectives. This paper proposes a knowledge based (KB) methodology to perform such control in FMS environments. Use of KB techniques is motivated by the observation that control knowledge has a high heuristic content. A PROLOG implementation of this methodology, that generates automatic response to machine failures, dynamic introduction of new jobs, and dynamic increase in job priority, is presented. Experimental results appear to show that simple and generic design strategies for the KB can provide the basis for effective and robust control behavior. Handled by the Department of Computer and Information Sciences. <s> BIB001 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Artificial Intelligence Techniques <s> SUMMARY In this paper we develop an interactive, real time, knowledge-based approach for dynamic scheduling. Blackboard concept has been utilized to organize and maintain the dynamic data base. The major knowledge representation schemes used in the system include frame structures, relational tables, and production rules. The system design is highly modular in nature thereby providing the ease for further development and enhancement. Based on this system, a design philosophy of an AI/OR integrated approach is also presented. <s> BIB002 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Artificial Intelligence Techniques <s> Abstract Scheduling can be divided into two classes, viz. predictive and reactive scheduling. Predictive scheduling addresses problems with deterministic process times and machine availability and generates a solution valid for the entire time span specified. Reactive scheduling, on the other hand, deals with the problem of maintaining schedules in a dynamic environment such as processing delays, machine breakdown, etc. In this paper a review of the research on scheduling in a dynamic environment is presented. Scheduling approaches have been classified into three categories, viz. conventional, knowledge-based and distributed problem solving. <s> BIB003 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Artificial Intelligence Techniques <s> Abstract Reactive scheduling has emerged as a new concept in production planning and control over the past few years. It is attracting the increased interest of both academic and industrial researchers in developing available knowledge-based techniques in real-time shop floor control applications and providing advanced tools for subsequent industrial applications. In this paper, we provide an overview of research results in the domain of knowledge-based reactive scheduling and some related industrial applications. Since reactive scheduling is a new and not well-defined paradigm, we start by examining some definitions of the problem given by different practitioners in the field. We then examine alternative knowledge-representation technologies and reasoning approaches which, because of t heir flexibility and reactive capability, are often applied in real-time decision-making environments. This is followed by a review of some reported industrial applications, and a summary on major areas for further researc... <s> BIB004 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Artificial Intelligence Techniques <s> In most practical environments, scheduling is an ongoing reactive process where evolving and changing circumstances continually force reconsideration and revision of pre-established plans. Scheduling research has traditionally ignored this “process view” of the problem, focusing instead on optimization of performance under idealized assumptions of environmental stability and solution executability. In this paper, we present work aimed at the development of reactive scheduling systems, which approach scheduling as a problem of maintaining a prescriptive solution over time, and emphasize objectives (e.g., solution continuity, system responsiveness) which relate directly to effective development and use of schedules in dynamic environments. We describe OPIS, a scheduling system designed to incrementally revise schedules in response to changes to solution constraints. OPIS implements a constraint-directed approach to reactive scheduling. Constraint analysis is used to prioritize outstanding problems in the current schedule, identify important modification goals, and estimate the possibilities for efficient and non-disruptive schedule modification. This information, in turn, provides a basis for selecting among a set of alternative modification actions, which differ in conflict resolution and schedule improvement capabilities, computational requirements and expected disruptive effects. <s> BIB005 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Artificial Intelligence Techniques <s> Practical scheduling problems generally require allocation of resources in the presence of a large, diverse and typically conflicting set of constraints and optimization criteria. The ill-structuredness of both the solution space and the desired objectives make scheduling problems difficult to formalize. This paper describes a case-based learning method for acquiring context-dependent user optimization preferences and tradeoffs and using them to incrementally improve schedule quality in predictive scheduling and reactive schedule management in response to unexpected execution events. The approach, implemented in the CABINS system, uses acquired user preferences to dynamically modify search control to guide schedule improvement. During iterative repair, cases are exploited for: (1) repair action selection, (2) evaluation of intermediate repair results and (3) recovery from revision failures. The method allows the system to dynamically switch between repair heuristic actions, each of which operates with respect to a particular local view of the problem and offers selective repair advantages. Application of a repair action tunes the search procedure to the characteristics of the local repair problem. This is achieved by dynamic modification of the search control bias. There is no a priori characterization of the amount of modification that may be required by repair actions. However, initial experimental results show that the approach is able to (a) capture and effectively utilize user scheduling preferences that were not present in the scheduling model, (b) produce schedules with high quality, without unduly sacrificing efficiency in predictive schedule generation and reactive response to unpredictable execution events along a variety of criteria that have been recognized as important in real operating environments. <s> BIB006 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Artificial Intelligence Techniques <s> Scheduling jobs effectively under the consideration of actual loads on machines is one of the most complicated tasks in production control. The conventional scheduling methods fail because of the complexity of the tasks. To deal with the complexity, knowledge-based approaches to job shop scheduling have been attempted. This paper presents an interactive scheduling expert system, IOSS (Intelligent Operations Scheduling System), which performs both predictive and reactive scheduling. IOSS combines the knowledge-based scheduling method with the interactive scheduling method to generate a feasible schedule and to revise the existing schedule. It is based on opportunistic and interactive repair based problem solving within a blackboard architecture. To handle conflicting events, heuristics are applied from the order point of view. Flexible reaction management is possible while keeping the changes in the generated schedule to a minimum by adjusting the schedule for tardy operations or changes in job shop status. The effectiveness of the proposed concept is demonstrated by applying the developed system to an example case. <s> BIB007 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Artificial Intelligence Techniques <s> Abstract Knowledge-based systems can help to enlarge the application range for simulation. Acting as intelligent front-ends they communicate with the user and provide statistical knowledge. As an example, the paper presents SIMULEX, a prototype decision support system for short-term rescheduling in manufacturing. SIMULEX couples expert systems and simulation to assist the production manager in handling production disturbances. Its core is a job shop simulator that models the plant and evaluates the results of various rescheduling measures. One intelligent front-end (the access system) gathers information about the disturbance and configures the simulation experiments. Another (the run time control) supervises the simulation runs. A third one (the termination/interpretation system) analyzes the data, derives conclusions and suggests the most promising measures. The paper focuses on the system's decision model that allows multi-attribute decisions under uncertainty. <s> BIB008 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Artificial Intelligence Techniques <s> Abstract Real-world scheduling problems are intrinsically complex because of the dynamic nature of industrial environments, conflicting organizational goals, the existence of operational constraints and preferences that are difficult to represent in a computational model. In addition, plant capacity and bottleneck stages are generally not known ahead of time since they depend upon the product mixture. Therefore, rigid scheduling procedures, designed to provide optimal or near-optimal solutions under particular circumstances, will not always be satisfactory. Moreover, purely automatic scheduling is not realistic because it neglects the important role of the human expert, who has the ultimate responsibility for all decisions and wants to be engaged in the solution process. To overcome these difficulties, many authors have adopted knowledge-based approaches. This contribution presents a knowledge-based framework, based on the object oriented technology, for building scheduling systems aimed at solving real-world problems. The paper points out the most relevant aspects of the proposed framework architecture that supports both predictive and reactive scheduling. It has been designed to enhance the problem solving capabilities of human schedulers and has been abstracted after the successful implementation of three different scheduling systems, two of which have entered into everyday industrial use. The most important lessons that were learned during the design of these systems are outlined in the paper. <s> BIB009 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Artificial Intelligence Techniques <s> Global competition and rapidly changing customer requirements are demanding increasing changes in manufacturing environments. Enterprises are required to constantly redesign their products and continuously reconfigure their manufacturing systems. Traditional approaches to manufacturing systems do not fully satisfy this new situation. Many authors have proposed that artificial intelligence (AI) will bring the flexibility and efficiency needed by manufacturing systems. This paper is a review of AI techniques used in manufacturing systems. The paper first defines the components of a simplified intelligent manufacturing systems (IMS), the different AI techniques to be considered and then shows how these AI techniques are used for the components of IMS. <s> BIB010 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Artificial Intelligence Techniques <s> Abstract The job shop rescheduling problem is considered as a particularly hard combinatorial optimization problem. This problem deals with uncertainty caused by the exterior business environment and interior production conditions. Production rescheduling is a common practice in Chinese manufacturing firms. Four sources of production disturbances have been identified: (1) incorrect work; (2) machine breakdowns; (3) rework due to quality problem; and (4) rush orders. These disturbances are fuzzy and random. In order to solve this ill-structured production problem, a production rescheduling expert simulation system is proposed in this paper. The production rescheduling expert simulation system integrates many techniques and methods, including simulation technique, artificial neural network, expert knowledge and dispatching rules. <s> BIB011 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Artificial Intelligence Techniques <s> Abstract In this work, a simple strategy for the development and implementation of a fault diagnosis system (FDS) that interacts with a schedule optimiser in batch chemical plants is presented. The proposed FDS consists of an artificial neural network (ANN) structure supplemented with a knowledge-based expert system (KBES) in a block-oriented configuration. The system combines the adaptive learning diagnostic procedure of the ANN and the transparent deep knowledge representation of the KBES. The information needed to implement the FDS includes a historical database of past batches, a Hazard and Operability (HAZOP) analysis and a model of the plant. Two motivating case studies are presented to show the results of the proposed methodology. The first corresponds to a fed-batch reactor. In this example, the FDS performance is demonstrated through the simulation of different process faults. The second case study corresponds to a multipurpose batch plant. In this case, the results of reactive scheduling are shown by simulating different abnormal situations. A performance comparison is made against the traditional scheduling approach without the support of the proposed FDS. <s> BIB012 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Artificial Intelligence Techniques <s> Abstract In this paper, a new fuzzy logic based decision support system for parallel machine scheduling/rescheduling in the presence of uncertain disruptions is presented. It is applied to a real-life problem identified in a pottery company. The uncertain disruption considered is glaze shortage, defined by two parameters: number of glaze shortage occurrences and glaze shortage duration. Both parameters are specified imprecisely. They are modelled and combined using standard fuzzy sets and level 2 fuzzy sets, respectively. In order to deal with the glaze shortage disruption, a predictive–reactive scheduling approach is proposed and implemented. It is defined as a two-step procedure. In the first step, a predictive schedule is generated in such a way as to being capable of absorbing the impact of the glaze shortage disruption. In the second step, rescheduling is applied when the impact of the glaze shortage disruption is too high. Two sets of Sugeno type rules are proposed to support rescheduling decision making. One set of the fuzzy rules determines when to reschedule, whilst the other one determines which rescheduling method to use. Various tests are carried out that show that (1) the predictive schedules have good performance in the presence of uncertain disruptions and (2) the fuzzy inference generates appropriate rescheduling decisions. <s> BIB013
A number of dynamic scheduling problems have adopted artificial intelligence techniques such as knowledge-based-systems, neural networks, case-based reasoning, fuzzy logic, Petri nets, etc. which are discussed below. The basic motivation of knowledge-based approaches is that there is a wide variety of technical expertise on the corrective actions to undertake in the presence of real-time events. Knowledge-based systems focus on capturing the expertise or the experience of the expert in a specific domain and an inference mechanism is used to derive conclusions or recommendations regarding the corrective action to undertake. ISIS  BIB005 developed at Carnegie Mellon in 1982, was the first attempt to use knowledge-based systems in production job shop scheduling. ISIS performs a constrained-direct search to derive a schedule. The dynamic situations are handled by rescheduling the affected jobs by selectively relaxing some of the constraints. OPIS  ) is a successor of ISIS. OPIS is a knowledge-based system developed originally for manufacturing production scheduling which uses an opportunistic problem solving process to incrementally generate and revise schedules in response to changes. OPIS implemented a blackboard architecture wherein a set of distinct heuristics, referred to as knowledge sources, are selectively employed to generate and revise the overall schedule. The schedule repair heuristics defined in OPIS are: job scheduler, resource scheduler, right-shifter, left-shifter, and demand swapper. IOSS BIB007 is another interactive scheduling knowledge-based scheduling system based on opportunistic and interactive repair-based problem solving within blackboard architecture. SONIA (Le  ) is a knowledge-based job-shop predictive-reactive scheduling system. Various schedule repair heuristics were defined such as relaxing due dates, extending work shifts, operation postponed until the next shift and reduction of idle times of resources by permuting operations. Some researchers combined knowledge-based systems and simulation to pursue a richer modelling capacity of scheduling to decide on the best corrective actions to handle the realtime events BIB008 . Some knowledge-based systems were developed to assist the user to 12 react interactively to real-time events BIB001 BIB002 BIB009  . Other artificial intelligence techniques that have been used to solve the problem of dynamic scheduling are the following: case-based reasoning, neural networks, petri nets, and fuzzy logic. Extensive discussions of these techniques can be found in BIB003 BIB004   BIB010 . To derive better dynamic scheduling systems, some researchers developed hybrid systems which combine various artificial intelligence techniques. BIB006 developed the framework CABINS for schedule repair in a job shop using case-based reasoning. Cases represent the repair context and suitable repair actions. Case based reasoning allows capturing and re-use of this knowledge to repair similar situations. The schedule is repaired incrementally, when necessary, using the cases stored in the system. Jahangirian and Conroy (2000), and BIB011 developed a hybrid framework for dynamic scheduling consisting of a knowledge-base describing the dispatching rules, a simulation module to evaluate the performance of the dispatching rules, an artificial neural network, and genetic algorithms which allow machine learning techniques to tailor the approaches to specific problem instances. Dorn (1995b) used casebased reasoning and fuzzy logic for reactive scheduling of the continuous caster in the steel industry.  used fuzzy logic to diagnose critical jobs in order to reschedule them. As a result, the decision-maker on the shop floor gets the information concerning which jobs must be rescheduled now, soon, later or probably not at all.  used fuzzy logic for dynamic scheduling of steel continuous casting. A fuzzy logic based decision support system for parallel machine scheduling and rescheduling in the presence of uncertain disruptions in a pottery company was presented in BIB013 . The uncertain disruption considered was material shortage, described by the number of disruption occurrences and disruption repair period. These parameters were specified imprecisely and modelled and combined using fuzzy sets and level 2 fuzzy sets, respectively. Sugeno type fuzzy rules were proposed to determine when to reschedule and which rescheduling method to use.  and  used knowledge-based systems and neural networks in reactive scheduling. The neural networks were used to decide on the best set of dispatching rules when a real-time event occurs. BIB012 proposed a fault diagnosis system for reactive scheduling in multipurpose batch chemical plants. The system combines the adaptive learning diagnostic procedure of neural networks and a knowledge-based expert system.