SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS
---
paper_title: Scheduling: Theory, Algorithms, and Systems

paper_content:

This book on scheduling covers theoretical models as well as scheduling problems in the real world. Author Michael Pinedo also includes a CD that contains slide-shows from industry and movies dealing with implementations of scheduling systems. The book consists of three parts. The first part focuses on deterministic scheduling with the associated combinatorial problems. The second part covers probabilistic scheduling models. In this part it is assumed that processing times and other problem data are not known in advance. The third part deals with scheduling in practice. It covers heuristics that are popular with practitioners and discusses system design and development issues. Each chapter contains a series of computational and theoretical exercises. This book is of interest to theoreticians and practitioners alike. Graduate students in operations management, operations research, industrial engineering and computer science will find the book to be an accessible and invaluable resource. Scheduling will serve as an essential reference for professionals working on scheduling problems in manufacturing and computing environments. Michael Pinedo is the Julius Schlesinger Professor of Operations Management at New York University.
---
paper_title: Addressing the gap in scheduling research: a review of optimization and heuristic methods in production scheduling

paper_content:

Abstract This paper considers the gap between scheduling theory and scheduling practice. The development and the main results of classical scheduling theory are reviewed and presented in an easily accessible way. Recent trends in scheduling research which attempt to make it more relevant and applicable are described. The nature of the gap between theory and practice is discussed. The failure of classical scheduling theory to address the total environment within which the scheduling function operates is noted. However, scheduling research in operations management and manufacturing systems tends to ignore the rich vein of methods, techniques and results in the classical theory. The need for an integrated scheduling research effort, containing elements of both approaches, is stressed.
---
paper_title: Deterministic Job-Shop Scheduling: Past, Present and Future

paper_content:

Abstract Due to the stubborn nature of the deterministic job-shop scheduling problem many solutions proposed are of hybrid construction cutting across the traditional disciplines. The problem has been investigated from a variety of perspectives resulting in several analytical techniques combining generic as well as problem specific strategies. We seek to assess a subclass of this problem in which the objective is minimising makespan, by providing an overview of the history, the techniques used and the researchers involved. The sense and direction of their work is evaluated by assessing the reported results of their techniques on the available benchmark problems. From these results the current situation and pointers for future work are provided. © 1999 Elsevier Science B.V. All rights reserved.
---
paper_title: Rescheduling manufacturing systems: A framework of strategies, policies, and methods

paper_content:

Many manufacturing facilities generate and update production schedules, which are plans that state when certain controllable activities (e.g., processing of jobs by resources) should take place. Production schedules help managers and supervisors coordinate activities to increase productivity and reduce operating costs. Because a manufacturing system is dynamic and unexpected events occur, rescheduling is necessary to update a production schedule when the state of the manufacturing system makes it infeasible. Rescheduling updates an existing production schedule in response to disruptions or other changes. Though many studies discuss rescheduling, there are no standard definitions or classification of the strategies, policies, and methods presented in the rescheduling literature. This paper presents definitions appropriate for most applications of rescheduling manufacturing systems and describes a framework for understanding rescheduling strategies, policies, and methods. This framework is based on a wide variety of experimental and practical approaches that have been described in the rescheduling literature. The paper also discusses studies that show how rescheduling affects the performance of a manufacturing system, and it concludes with a discussion of how understanding rescheduling can bring closer some aspects of scheduling theory and practice.
---
paper_title: Workshop scheduling using practical (inaccurate) data Part 2: An investigation of the robustness of scheduling rules in a dynamic and stochastic environment

paper_content:

In research on generating a predictive schedule, the scheduling problem is often viewed as a deterministic problem. However, the real-life job shop environment is stochastic in that information on job attributes and shop floor status is not precisely known in advance. In this situation, in order to increase the effectiveness of a predictive schedule in practice, the focus should be on creating a robust schedule. The purpose of this paper is to investigate the robustness of a number of scheduling rules in a dynamic and stochastic environment using the rolling time horizon approach. A cost-based performance measure is used to evaluate the scheduling rules. The simulation results, under various conditions in a balanced and unbalanced shop, are presented and the effects of the rescheduling interval and operational factors including shop load conditions and a bottleneck on the robustness of the schedule are studied. From the results the key factors that influence the robustness of a scheduling system are ident...
---
paper_title: The state of the art in intelligent real-time FMS control: a comprehensive survey

paper_content:

Flexible manufacturing systems (FMS) have been developed with the hope that they would provide a means to tackle a threefold challenge — better quality, lower cost and shorter lead times — by integrating machine tools, robots, material handling and storage systems, and computers. Control of the integrated system presented a new set of problems as well as challenges, which have been receiving considerable attention from the academic community as well as from industrial system users. Intelligent control, which involves using computers to assist in decision making at various stages of the control process, has been advocated by many researchers as a possible avenue to reach a solution to these problems. This paper provides a review of the state of the art in intelligent control of FMS, in an attempt to supplement earlier general reviews via a more focused perspective. The principles of several techniques, namely simulation, knowledge based, example based, petri nets, and hybrid approaches are briefly introduced, and publications are reviewed, followed by discussions ontheir potential. Suggestions for further research and development are also enumerated.
---
paper_title: Predictable scheduling of a single machine subject to breakdowns

paper_content:

The predictive production schedule has two important functions; allocating shop resources to the different jobs to optimize some measure of shop performance and serving as a basis for planning activities such as material procurement, preventive maintenance and delivery of orders to external or internal customers. This schedule is modified during execution on the occurrence of disruptions such as machine breakdowns. The schedule modification process may delay or render infeasible the execution of activities planned on the basis of the predictive schedule. Thus it is of interest to develop predictive schedules which can absorb disruptions without affecting planned activities while maintaining high shop performance. A predictable scheduling approach is presented, where the predictive schedule is built with such objectives. The effects of disruptions on planned activities are measured by the difference between planned and realized job completion times. The specific scheduling model considered is minimizing ma...
---
paper_title: Rescheduling manufacturing systems: A framework of strategies, policies, and methods

paper_content:

Many manufacturing facilities generate and update production schedules, which are plans that state when certain controllable activities (e.g., processing of jobs by resources) should take place. Production schedules help managers and supervisors coordinate activities to increase productivity and reduce operating costs. Because a manufacturing system is dynamic and unexpected events occur, rescheduling is necessary to update a production schedule when the state of the manufacturing system makes it infeasible. Rescheduling updates an existing production schedule in response to disruptions or other changes. Though many studies discuss rescheduling, there are no standard definitions or classification of the strategies, policies, and methods presented in the rescheduling literature. This paper presents definitions appropriate for most applications of rescheduling manufacturing systems and describes a framework for understanding rescheduling strategies, policies, and methods. This framework is based on a wide variety of experimental and practical approaches that have been described in the rescheduling literature. The paper also discusses studies that show how rescheduling affects the performance of a manufacturing system, and it concludes with a discussion of how understanding rescheduling can bring closer some aspects of scheduling theory and practice.
---
paper_title: Executing production schedules in the face of uncertainties : A review and some future directions

paper_content:

We review the literature on executing production schedules in the presence of unforeseen disruptions on the shop floor. We discuss a number of issues related to problem formulation, and discuss the functions of the production schedule in the organization and provide a taxonomy of the different types of uncertainty faced by scheduling algorithms. We then review previous research relative to these issues, and suggest a number of directions for future work in this area. � 2003 Elsevier B.V. All rights reserved.
---
paper_title: The complexity of machine scheduling for stability with a single disrupted job

paper_content:

A stable schedule is a robust schedule that will change little when uncertain events occur. The purpose of this paper is to investigate the complexity status of a number of machine scheduling problems with stability objective, when the duration of a single job is anticipated to be disrupted.
---
paper_title: Analytical models to predict the performance of a single-machine system under periodic and event-driven rescheduling strategies

paper_content:

This article presents initial results in the search for analytical models that can predict the performance of one-machine systems under periodic and event-driven rescheduling strategies in an environment where different job types arrive dynamically for processing and set-up must incur when production changes from one product type to another. The scheduling algorithm considered uses a first-in firstout dispatching rule to sequence jobs and it also groups jobs with similar types to save set-up time. The analytical models can estimate important performance measures like average flow time and machine utilization, which can then be used to determine optimal rescheduling parameters. Simulation experiments are used to show that the analytical models accurately predict the performance of the single machine under the scheduling algorithm proposed.
---
paper_title: A Rescheduling Procedure for Manufacturing Systems Under Random Disruptions

paper_content:

Short to medium term schedules of a manufacturing system are often produced a priori in order to direct production operations and to support other planning activities such as tooling, raw material delivery and resource allocation. Unfortunately, as soon as the a priori schedule is released to the shop, myriad disturbances will arise which render the schedule obsolete. “Rescheduling” is a means of restoring the operations schedule when such a disruption has occurred. Complications arise when schedule changes induce major cost impact to other planning activities which use the a priori schedule as a basis. This problem of shop rescheduling is of great practical importance and has been addressed in various areas of Operations Research including stochastic scheduling and combinatorial optimization.
---
paper_title: Robust Scheduling to Hedge Against Processing Time Uncertainty in Single-Stage Production

paper_content:

Schedulers confronted with significant processing time uncertainty often discover that a schedule which is optimal with respect to a deterministic or stochastic scheduling model yields quite poor performance when evaluated relative to the actual processing times. In these environments, the notion of schedule robustness, i.e., determining the schedule with the best worst-case performance compared to the corresponding optimal solution over all potential realizations of job processing times, is a more appropriate guide to schedule selection. In this paper, we formalize the robust scheduling concept for scheduling situations with uncertain or variable processing times. To illustrate the development of solution approaches for a robust scheduling problem, we consider a single-machine environment where the performance criterion of interest is the total flow time over all jobs. We define two measures of schedule robustness, formulate the robust scheduling problem, establish its complexity, describe properties of the optimal schedule, and present exact and heuristic solution procedures. Extensive computational results are reported to demonstrate the efficiency and effectiveness of the proposed solution procedures.
---
paper_title: ROBUSTNESS MEASURES AND ROBUST SCHEDULING FOR JOB SHOPS

paper_content:

Abstract A robust schedule is defined as a schedule that is insensitive to unforeseen shop floor disturbances given an assumed control policy. In this paper, a definition of schedule robustness is developed which comprises two components: post-disturbance make-span and post-disturbance makespan variability. We have developed robustness measures and robust scheduling methods for the case where a “right-shift” control policy is used. On occurrence of a disruption, the right-shift policy maintains the scheduling sequence while delaying the unfinished jobs as much as necessary to accommodate the disruption. An exact measure of schedule robustness is derived for the case in which only a single disruption occurs within the planning horizon. A surrogate measure is developed for the more complex case in which multiple disruptions may occur. This surrogate measure is then embedded in a genetic algorithm to generate robust schedules for job-shops. Experimental results show that robust schedules significantly outper...
---
paper_title: Using real time information for effective dynamic scheduling

paper_content:

Abstract In many production processes real time information may be obtained from process control computers and other monitoring systems, but most existing scheduling models are unable to use this information to effectively influence scheduling decisions in real time. In this paper we develop a general framework for using real time information to improve scheduling decisions, which allows us to trade off the quality of the revised schedule against the production disturbance which results from changing the planned schedule. We illustrate how our framework can be used to select a strategy for using real time information for a single machine scheduling model and discuss how it may be used to incorporate real time information into scheduling the complex production processes of steel continuous caster planning.
---
paper_title: One-machine rescheduling heuristics with efficiency and stability as criteria

paper_content:

Abstract Heuristics for the problem of rescheduling a machine on occurrence of an unforeseen disruption are developed. The criteria include minimization of the makespan (schedule efficiency) and the impact of the schedule change (schedule stability). The impact of schedule change is a non-regular performance measure defined in two ways: (1) the starting time deviations between the new schedule and the original schedule, and (2) a measure of the sequence difference between the two schedules. Three local search procedures are developed for the bicriterion problem and a set of experiments are conducted to test the efficacy of the heuristics. The heuristic solutions are shown to be effective in that the schedule stability can be increased significantly with little or no sacrifice in makespan.
---
paper_title: Rescheduling job shops under random disruptions

paper_content:

In this work, an algorithm for rescheduling the affected operations in a job shop is presented and its performance, with respect to measures of efficiency and stability, is compared with that of Total Rescheduling and Right-Shift Rescheduling. Algorithms for all three methods are implemented in a rescheduling program which, based on keyed-in disruption information, produces three new schedules and outputs their related performance measures. A designed factorial experiment is performed on benchmark scheduling problems to study the effect of different rescheduling methods as well as various problem characteristics and disruption scenarios on the performance of the new schedules. The results demonstrate that the Affected Operations Algorithm overcomes the disadvantages associated with other rescheduling methods.
---
paper_title: The complexity of machine scheduling for stability with a single disrupted job

paper_content:

A stable schedule is a robust schedule that will change little when uncertain events occur. The purpose of this paper is to investigate the complexity status of a number of machine scheduling problems with stability objective, when the duration of a single job is anticipated to be disrupted.
---
paper_title: Improving Robustness and Flexibility of Tardiness and Total Flowtime Job Shops Using Robustness Measures

paper_content:

Abstract The traditional focus of scheduling research is on finding schedules with a low implementation cost. However, in many real world scheduling applications finding a robust or flexible schedule is just as important. A robust schedule is a quality schedule expected to still be acceptable if something unforeseen happens, while a flexible schedule is a quality schedule expected to be easy to change. In this paper, the robustness and flexibility of schedules produced by minimising different robustness measures are investigated. One kind of robustness measure is the neighbourhood-based robustness measure, in which the basic idea is to minimise the implementation costs of a set of schedules located around a centre schedule. For tardiness problems another way of improving robustness is to increase the slack of the schedule by minimising lateness instead of tardiness. The problems used in the experiments are maximum tardiness, summed tardiness and total flow-time job shop problems. The experiments showed that the neighbourhood-based robustness measures improves robustness for all the problem types. Flexibility is improved for maximum tardiness and loose summed tardiness problems, while it is not improved for tight summed tardiness problems and total flow-time problems. The lateness-based robustness measures are found to also improve robustness and in some cases flexibility for the same problems, but the improvement is not as substantial as with the neighbourhood-based measures. Based on these observations, it is conjectured that neighbourhood-based robustness can be expected to improve flexibility on problems with few critical points.
---
paper_title: Predictable scheduling of a single machine subject to breakdowns

paper_content:

The predictive production schedule has two important functions; allocating shop resources to the different jobs to optimize some measure of shop performance and serving as a basis for planning activities such as material procurement, preventive maintenance and delivery of orders to external or internal customers. This schedule is modified during execution on the occurrence of disruptions such as machine breakdowns. The schedule modification process may delay or render infeasible the execution of activities planned on the basis of the predictive schedule. Thus it is of interest to develop predictive schedules which can absorb disruptions without affecting planned activities while maintaining high shop performance. A predictable scheduling approach is presented, where the predictive schedule is built with such objectives. The effects of disruptions on planned activities are measured by the difference between planned and realized job completion times. The specific scheduling model considered is minimizing ma...
---
paper_title: Slack-Based Techniques for Robust Schedules

paper_content:

Many scheduling systems assume a static environment within which a schedule will be executed. The real world is not so stable: machines break down, operations take longer to execute than expected, and orders may be added or canceled. One approach to dealing with such disruptions is to generate robust schedules: schedules that are able to absorb some level of unexpected events without rescheduling. In this paper we investigate three techniques for generating robust schedules based on the insertion of temporal slack. Simulation-based results indicate that the two novel techniques out-perform the existing temporal protection technique both in terms of producing schedules with low simulated tardiness and in producing schedules that better predict the level of simulated tardiness.
---
paper_title: Rescheduling manufacturing systems: A framework of strategies, policies, and methods

paper_content:

Many manufacturing facilities generate and update production schedules, which are plans that state when certain controllable activities (e.g., processing of jobs by resources) should take place. Production schedules help managers and supervisors coordinate activities to increase productivity and reduce operating costs. Because a manufacturing system is dynamic and unexpected events occur, rescheduling is necessary to update a production schedule when the state of the manufacturing system makes it infeasible. Rescheduling updates an existing production schedule in response to disruptions or other changes. Though many studies discuss rescheduling, there are no standard definitions or classification of the strategies, policies, and methods presented in the rescheduling literature. This paper presents definitions appropriate for most applications of rescheduling manufacturing systems and describes a framework for understanding rescheduling strategies, policies, and methods. This framework is based on a wide variety of experimental and practical approaches that have been described in the rescheduling literature. The paper also discusses studies that show how rescheduling affects the performance of a manufacturing system, and it concludes with a discussion of how understanding rescheduling can bring closer some aspects of scheduling theory and practice.
---
paper_title: Scheduling/rescheduling in the manufacturing operating system environment†

paper_content:

Abstract A scheduling/rescheduling procedure is proposed for real-time control of a computerized manufacturing facility managed by a central manufacturing operating system. The procedure implies schedule revisions upon significant operational changes such as machine breakdowns. Experiments to evaluate the total production time of a computerized manufacturing system with breakdowns under scheduling/rescheduling have yielded advantages of between 25% to 7-0% compared to fixed sequencing and priority despatching procedures, respectively. Computation times required for the scheduling procedures on a CDC 65OO/66OO have also been studied. The scheduling/rescheduling procedure for an actual facility required less than two minutes, and the computation time can be regulated by the selection of parameters in an approximate method of scheduling. A shorter version of this article has appeared in Japanese (Yamumoto and Nof 1982)
---
paper_title: Job shop scheduling heuristics and frequency of scheduling

paper_content:

Abstract This paper presents a job scheduling problem. Two important aspects are included in the subsequent analysis. The first is the dynamic nature whereby new jobs arrive to be included intermittently through time. The second is the uncertainty, or error in estimating process times, and the likelihood of machine breakdown. An experiment is presented which shows the performance of a number of heuristics in the form of dispatching disciplines under different scheduling conditions which are determined by the scheduling period and the level of uncertainty in the process times and machine breakdowns. Various different measures of performance which could be of importance to management are considered. These include mean ratio of flow time to process time, mean queueing time, mean lateness, percentage of jobs late and net CPU times required to generate schedules in the simulation process. Results are presented showing the relationship between the performance of the heuristics relative to the different measures...
---
paper_title: Rescheduling manufacturing systems: A framework of strategies, policies, and methods

paper_content:

Many manufacturing facilities generate and update production schedules, which are plans that state when certain controllable activities (e.g., processing of jobs by resources) should take place. Production schedules help managers and supervisors coordinate activities to increase productivity and reduce operating costs. Because a manufacturing system is dynamic and unexpected events occur, rescheduling is necessary to update a production schedule when the state of the manufacturing system makes it infeasible. Rescheduling updates an existing production schedule in response to disruptions or other changes. Though many studies discuss rescheduling, there are no standard definitions or classification of the strategies, policies, and methods presented in the rescheduling literature. This paper presents definitions appropriate for most applications of rescheduling manufacturing systems and describes a framework for understanding rescheduling strategies, policies, and methods. This framework is based on a wide variety of experimental and practical approaches that have been described in the rescheduling literature. The paper also discusses studies that show how rescheduling affects the performance of a manufacturing system, and it concludes with a discussion of how understanding rescheduling can bring closer some aspects of scheduling theory and practice.
---
paper_title: Executing production schedules in the face of uncertainties : A review and some future directions

paper_content:

We review the literature on executing production schedules in the presence of unforeseen disruptions on the shop floor. We discuss a number of issues related to problem formulation, and discuss the functions of the production schedule in the organization and provide a taxonomy of the different types of uncertainty faced by scheduling algorithms. We then review previous research relative to these issues, and suggest a number of directions for future work in this area. � 2003 Elsevier B.V. All rights reserved.
---
paper_title: Rolling horizon algorithms for a single-machine dynamic scheduling problem with sequence-dependent setup times

paper_content:

We present a family of rolling horizon heuristics to minimize maximum lateness on a single machine in the presence of sequence-dependent setup times. This problem occurs as a subproblem in a decomposition procedure for more complicated job shop scheduling problems. The procedures solve a sequence of subproblems to optimality with a branch and bound algorithm and implements only part of the solution obtained. The size and number of the subproblems are controlled by algorithm parameters. Extensive computational experiments show that these procedures outperform myopic dispatching rules by an order of magnitude, both on average and in the worst case, in very reasonable computation times.
---
paper_title: Analysis of reactive scheduling problems in a job shop environment

paper_content:

Abstract In this paper, we study the reactive scheduling problems in a stochastic manufacturing environment. Specifically, we test the several scheduling policies under machine breakdowns in a classical job shop system. In addition, we measure the effect of system size and type of work allocation (uniform and bottleneck) on the system performance. The performance of the system is measured for the mean tardiness and makespan criteria. We also investigate a partial scheduling scheme under both deterministic and stochastic environments for several system configurations.
---
paper_title: Rescheduling frequency in an FMS with uncertain processing times and unreliable machines

paper_content:

This paper studies the scheduling/rescheduling problem in a multi-resource FMS environment. Several reactive scheduling policies are proposed to address the effects of machine breakdowns and processing time variations. Both off-line and on-line scheduling methods are tested under a variety of experimental conditions. The performance of the system is measured for mean tardiness and makespan criteria. The relationships between scheduling frequency and other scheduling factors are investigated. The results indicated that a periodic response with an appropriate period length would be sufficient to cope with interruptions. It was also observed that machine breakdowns have more significant impact on the system performance than processing time variations. In addition, dispatching rules were found to be more robust to interruptions than the optimum-seeking off-line scheduling algorithm. A comprehensive bibliography is also included in the paper.
---
paper_title: Simulation-based real-time scheduling in a flexible manufacturing system

paper_content:

Abstract We present a simulation-based real-time scheduling methodology for a flexible manufacturing system. Developed is a scheduling mechanism in which the job dispatching rule varies dynamically based on information from discrete event simulation that evaluates a set of candidate rules. Major components of the scheduling mechanism are a simulation mechanism and a real-time control system. The simulation mechanism evaluates dispatching rules and selects the best dispatching rule for a given criterion. The real-time control system periodically monitors the shop floor and checks the performance value of the system. The selected dispatching rule is used until the difference between the actual performance value and the value estimated by simulation exceeds a given limit. Then a new simulation is performed with the remaining operations in the simulation mechanism to select a new rule. Results of computational tests show that the scheduling mechanism can be used effectively in real situations because it can fully use the information on the actual state of shop floors.
---
paper_title: Analytical models to predict the performance of a single-machine system under periodic and event-driven rescheduling strategies

paper_content:

This article presents initial results in the search for analytical models that can predict the performance of one-machine systems under periodic and event-driven rescheduling strategies in an environment where different job types arrive dynamically for processing and set-up must incur when production changes from one product type to another. The scheduling algorithm considered uses a first-in firstout dispatching rule to sequence jobs and it also groups jobs with similar types to save set-up time. The analytical models can estimate important performance measures like average flow time and machine utilization, which can then be used to determine optimal rescheduling parameters. Simulation experiments are used to show that the analytical models accurately predict the performance of the single machine under the scheduling algorithm proposed.
---
paper_title: Analysis of periodic and event-driven rescheduling policies in dynamic shops

paper_content:

Abstract We address the problem of rescheduling production systems in the face of dynamic job arrivals. Using simple single-and parallel-machine models to gain insight, we provide worst-case and computational analyses of periodic and event-driven rescheduling policies. Our results indicate that event-driven policies can obtain high-quality schedules with less rescheduling than continuous rescheduling policies. We also show that if structure in the job arrival process is exploited very effective periodic rescheduling policies can be designed.
---
paper_title: A Rescheduling Procedure for Manufacturing Systems Under Random Disruptions

paper_content:

Short to medium term schedules of a manufacturing system are often produced a priori in order to direct production operations and to support other planning activities such as tooling, raw material delivery and resource allocation. Unfortunately, as soon as the a priori schedule is released to the shop, myriad disturbances will arise which render the schedule obsolete. “Rescheduling” is a means of restoring the operations schedule when such a disruption has occurred. Complications arise when schedule changes induce major cost impact to other planning activities which use the a priori schedule as a basis. This problem of shop rescheduling is of great practical importance and has been addressed in various areas of Operations Research including stochastic scheduling and combinatorial optimization.
---
paper_title: Robust Scheduling to Hedge Against Processing Time Uncertainty in Single-Stage Production

paper_content:

Schedulers confronted with significant processing time uncertainty often discover that a schedule which is optimal with respect to a deterministic or stochastic scheduling model yields quite poor performance when evaluated relative to the actual processing times. In these environments, the notion of schedule robustness, i.e., determining the schedule with the best worst-case performance compared to the corresponding optimal solution over all potential realizations of job processing times, is a more appropriate guide to schedule selection. In this paper, we formalize the robust scheduling concept for scheduling situations with uncertain or variable processing times. To illustrate the development of solution approaches for a robust scheduling problem, we consider a single-machine environment where the performance criterion of interest is the total flow time over all jobs. We define two measures of schedule robustness, formulate the robust scheduling problem, establish its complexity, describe properties of the optimal schedule, and present exact and heuristic solution procedures. Extensive computational results are reported to demonstrate the efficiency and effectiveness of the proposed solution procedures.
---
paper_title: Utility and stability measures for agent-based dynamic scheduling of steel continuous casting

paper_content:

This paper describes a new model for robust predictive/reactive scheduling of steel continuous casting based on the use of multi-agents, tabu search and heuristic approaches. A continuous caster agent generates a predictive production schedule taking into account manufacturing requirements and local constraints using tabu search. The predictive schedule is modifies so as to minimize deviation between the performance measure values of the realized and predictive schedules in order to react to real-time events. We propose several schedule-repair and complete reschedule strategies to handle the real-time events, evaluate and compare their performance. The decision as to whether to locally repair the schedule or reschedule from scratch (complete reschedule) is based on three measures: robustness, utility and stability. Utility measures the change in schedule objective following schedule revision. Stability measures the deviation from the original schedule caused by schedule revision to quantify the undesirability of making large changes to the initial predictive schedule unless absolutely necessary. Robustness combines the utility and stability measures. In order to investigate the performance of these measures and strategies, simulation experiments were carried out and results are reported.
---
paper_title: Using real time information for effective dynamic scheduling

paper_content:

Abstract In many production processes real time information may be obtained from process control computers and other monitoring systems, but most existing scheduling models are unable to use this information to effectively influence scheduling decisions in real time. In this paper we develop a general framework for using real time information to improve scheduling decisions, which allows us to trade off the quality of the revised schedule against the production disturbance which results from changing the planned schedule. We illustrate how our framework can be used to select a strategy for using real time information for a single machine scheduling model and discuss how it may be used to incorporate real time information into scheduling the complex production processes of steel continuous caster planning.
---
paper_title: Rescheduling manufacturing systems: A framework of strategies, policies, and methods

paper_content:

Many manufacturing facilities generate and update production schedules, which are plans that state when certain controllable activities (e.g., processing of jobs by resources) should take place. Production schedules help managers and supervisors coordinate activities to increase productivity and reduce operating costs. Because a manufacturing system is dynamic and unexpected events occur, rescheduling is necessary to update a production schedule when the state of the manufacturing system makes it infeasible. Rescheduling updates an existing production schedule in response to disruptions or other changes. Though many studies discuss rescheduling, there are no standard definitions or classification of the strategies, policies, and methods presented in the rescheduling literature. This paper presents definitions appropriate for most applications of rescheduling manufacturing systems and describes a framework for understanding rescheduling strategies, policies, and methods. This framework is based on a wide variety of experimental and practical approaches that have been described in the rescheduling literature. The paper also discusses studies that show how rescheduling affects the performance of a manufacturing system, and it concludes with a discussion of how understanding rescheduling can bring closer some aspects of scheduling theory and practice.
---
paper_title: One-machine rescheduling heuristics with efficiency and stability as criteria

paper_content:

Abstract Heuristics for the problem of rescheduling a machine on occurrence of an unforeseen disruption are developed. The criteria include minimization of the makespan (schedule efficiency) and the impact of the schedule change (schedule stability). The impact of schedule change is a non-regular performance measure defined in two ways: (1) the starting time deviations between the new schedule and the original schedule, and (2) a measure of the sequence difference between the two schedules. Three local search procedures are developed for the bicriterion problem and a set of experiments are conducted to test the efficacy of the heuristics. The heuristic solutions are shown to be effective in that the schedule stability can be increased significantly with little or no sacrifice in makespan.
---
paper_title: Rescheduling job shops under random disruptions

paper_content:

In this work, an algorithm for rescheduling the affected operations in a job shop is presented and its performance, with respect to measures of efficiency and stability, is compared with that of Total Rescheduling and Right-Shift Rescheduling. Algorithms for all three methods are implemented in a rescheduling program which, based on keyed-in disruption information, produces three new schedules and outputs their related performance measures. A designed factorial experiment is performed on benchmark scheduling problems to study the effect of different rescheduling methods as well as various problem characteristics and disruption scenarios on the performance of the new schedules. The results demonstrate that the Affected Operations Algorithm overcomes the disadvantages associated with other rescheduling methods.
---
paper_title: Reactive Scheduling - Improving the Robustness of Schedules and Restricting the Effects of Shop Floor Disturbances by Fuzzy Reasoning

paper_content:

Abstract Practical scheduling usually has to reach to many unpredictable events and uncertainties in the production environment. Although often possible in theory, it is undesirable to reschedule from scratch in such cases. Since the surrounding organization will be prepared for the predicted schedule, it is important to change only those features of the schedule that are necessary. We show how, on one side, fuzzy logic can be used to support the construction of schedules that are robust with respect to changes due to certain types of event. On the other side, we show how a reaction can be restricted to a small environment by means of fuzzy constraints and a repair-based problem-solving strategy. We demonstrate the proposed representation and problem-solving method by introducing a scheduling application in a steelmaking plant. We construct a preliminary schedule by taking into account only the most likely duration of operations. This schedule is iteratively "repaired" until some threshold evaluation is found. A repair is found with a local search procedure based on Tabu Search. Finally, we show which events can lead to reactive scheduling and how this is supported by the repair strategy.
---
paper_title: Analysis of reactive scheduling problems in a job shop environment

paper_content:

Abstract In this paper, we study the reactive scheduling problems in a stochastic manufacturing environment. Specifically, we test the several scheduling policies under machine breakdowns in a classical job shop system. In addition, we measure the effect of system size and type of work allocation (uniform and bottleneck) on the system performance. The performance of the system is measured for the mean tardiness and makespan criteria. We also investigate a partial scheduling scheme under both deterministic and stochastic environments for several system configurations.
---
paper_title: Improving Robustness and Flexibility of Tardiness and Total Flowtime Job Shops Using Robustness Measures

paper_content:

Abstract The traditional focus of scheduling research is on finding schedules with a low implementation cost. However, in many real world scheduling applications finding a robust or flexible schedule is just as important. A robust schedule is a quality schedule expected to still be acceptable if something unforeseen happens, while a flexible schedule is a quality schedule expected to be easy to change. In this paper, the robustness and flexibility of schedules produced by minimising different robustness measures are investigated. One kind of robustness measure is the neighbourhood-based robustness measure, in which the basic idea is to minimise the implementation costs of a set of schedules located around a centre schedule. For tardiness problems another way of improving robustness is to increase the slack of the schedule by minimising lateness instead of tardiness. The problems used in the experiments are maximum tardiness, summed tardiness and total flow-time job shop problems. The experiments showed that the neighbourhood-based robustness measures improves robustness for all the problem types. Flexibility is improved for maximum tardiness and loose summed tardiness problems, while it is not improved for tight summed tardiness problems and total flow-time problems. The lateness-based robustness measures are found to also improve robustness and in some cases flexibility for the same problems, but the improvement is not as substantial as with the neighbourhood-based measures. Based on these observations, it is conjectured that neighbourhood-based robustness can be expected to improve flexibility on problems with few critical points.
---
paper_title: A dynamic reactive scheduling mechanism for responding to changes of production orders and manufacturing resources

paper_content:

Abstract This research introduces a dynamic reactive production scheduling mechanism for modifying the originally created schedules when these schedules cannot be completed due to changes of production orders and manufacturing resources. Production order changes include removal of an order that is canceled by a customer and insertion of an order that has to be completed within a short period of time. Manufacturing resource changes include breakdowns of machines and sudden sickness of workers. Match-up and agent-based collaboration approaches are employed to modify only part of the originally created schedules for improving the reactive scheduling efficiency, while maintaining the scheduling quality. The dynamic reactive production scheduling system was implemented using Smalltalk, an object oriented programming language.
---
paper_title: Modeling Manufacturing Systems: from Aggregate Planning to Real-Time Control

paper_content:

Modelling Manufacturing Systems: an Introduction: P. Brandimarte, A. Villa: Introduction and Overview of the Contributions.- For Further Reading.- References.- From the Aggregate Plan to Lot-Sizing in Multi-level Production Planning: J.-C. Hennet: Introduction.- The Planning Process.- The Lot-Sizing Problem.- Example.- Conclusion.- References.- Shop Floor Scheduling in Discrete Parts Manufacturing: G. J. Meester, J. M. J. Schutten, S. L. van de Velde, W. H. M. Zijm: Introduction.- Basic Decomposition Approach.- Multi-Resource Scheduling.- Set-Up Times.- Convergent and Divergent Job Routings.- Further Extensions and Practical Aspects.- JOBPLANNER.- Conclusions.- References.- Appendix A: Derivation of Set-Up Jobs.- Integrating Layout Design and Material Flow Management in Assembly Systems: M. Lucertini, D. Pacciaretti, A. Pacifici: Introduction.- Statement of the Problem.- Feasibility Properties.- Optimization Properties.- Conclusions.- References.- Appendix: Proofs of Theorems.- Reactive Scheduling in Real Time Production Control: E. Szelke, L. Monostori: Reactive Operation Management - Predictive, Reactive and Proactive Scheduling.- Models of Reactive and Proactive Scheduling Problems.- Solution Approaches - Methods, Techniques, Tools.- Conclusions: Future Research Issues in the Field.- References.- Simulation within CAD-Environment: P. Kopacek, G. Kronreif, T. Perme: Introduction.- Simulation System LASIMCO.- Simulation in Robotics - ROMOBIL/SITAR.- Conclusion.- References.- Model of Material Handling and Robotics.- C.-Y. Huang: Introduction.- Traditional Models of Material Handling and Robotics.- Facility Description Language (FDL).- Concurrent Flexible Specifications (CFS) for Material Handling and Robotics.- Discussion and Conclusion.- References.- A Simultaneous Approach for IMS Design: a Possibility Based Approach: G. Perrone, S. Noto La Diega: Introduction.- The Decisional Environment for Strategic IMS Design.- The Strategic IMS Design Decision-Making Tool: The Possibilistic Programming Theory.- The Possibilistic Framework for Strategic FMS Design.- Numerical Example.- Conclusions.- References.- Adaptive Production Control in Modern Industries: K. N. McKay, J. A. Buzacott: Introduction.- Motivation - Inherent Uncertainty.- Applying Production Control Methods - A Perspective.- Production Control Concepts for Immaturity or Uncertainty.- Conclusion.- Acknowledgments.- References.
---
paper_title: The state of the art in intelligent real-time FMS control: a comprehensive survey

paper_content:

Flexible manufacturing systems (FMS) have been developed with the hope that they would provide a means to tackle a threefold challenge — better quality, lower cost and shorter lead times — by integrating machine tools, robots, material handling and storage systems, and computers. Control of the integrated system presented a new set of problems as well as challenges, which have been receiving considerable attention from the academic community as well as from industrial system users. Intelligent control, which involves using computers to assist in decision making at various stages of the control process, has been advocated by many researchers as a possible avenue to reach a solution to these problems. This paper provides a review of the state of the art in intelligent control of FMS, in an attempt to supplement earlier general reviews via a more focused perspective. The principles of several techniques, namely simulation, knowledge based, example based, petri nets, and hybrid approaches are briefly introduced, and publications are reviewed, followed by discussions ontheir potential. Suggestions for further research and development are also enumerated.
---
paper_title: Dynamic scheduling--a survey of research

paper_content:

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.
---
paper_title: Dynamic job shop scheduling: A survey of simulation research

paper_content:

Scheduling of job shops has been extensively researched over the last three decades and it continues to attract the interests of both academic researchers and practitioners. This paper provides a state-of-the-art survey of the simulation-based research on dynamic job shop scheduling with a distinct emphasis on two important aspects. First, job-shop simulation modeling and experimental considerations are discussed with a review of the different approaches taken in the literature. Second, a review of the different studies is provided with a focus on their findings on the job shop performance criteria of interest. This paper is aimed at both practicing managers and researchers in the area of job shop scheduling because of the following considerations: 1. (i) The number of factors that characterize a job shop is very large and there is considerable variation in modeling and experimentation across the vast number of studies reported. Important research findings relevant to these issues reviewed in this paper would facilitate comparison of the currently available research results and their extension or application to other situations.2. (ii) A review of the various studies focusing on some of the more important performance criteria should help practitioners in the selection of scheduling rules to match the criterion particularly relevant to their shops.3. (iii) Recent studies which have modeled job shops as dual-resource constrained systems and assembly shops have been included in this survey for a more comprehensive coverage. A detailed bibliography is included and every effort has been made to make the survey up-to-date.
---
paper_title: A study of scheduling rules of flexible manufacturing systems: A simulation approach

paper_content:

This study examines the effects of scheduling rules on the performance of flexible manufacturing systems (FMSs). Several machine and AGV scheduling rules are tested against the mean flowtime criterion. In general, scheduling rules are widely used in practice ranging from direct applications as a stand-alone scheduling scheme to indirect application as a part of complicated scheduling systems. In this paper, we compare the rules under various experimental conditions by using an FMS simulation model. Our objective is to measure sensitivity of the rules to changes in processing time distributions, various levels of breakdown rates, and types of AGV priority schemes. A comprehensive bibliography is also presented in the paper.
---
paper_title: Simulation-based real-time scheduling in a flexible manufacturing system

paper_content:

Abstract We present a simulation-based real-time scheduling methodology for a flexible manufacturing system. Developed is a scheduling mechanism in which the job dispatching rule varies dynamically based on information from discrete event simulation that evaluates a set of candidate rules. Major components of the scheduling mechanism are a simulation mechanism and a real-time control system. The simulation mechanism evaluates dispatching rules and selects the best dispatching rule for a given criterion. The real-time control system periodically monitors the shop floor and checks the performance value of the system. The selected dispatching rule is used until the difference between the actual performance value and the value estimated by simulation exceeds a given limit. Then a new simulation is performed with the remaining operations in the simulation mechanism to select a new rule. Results of computational tests show that the scheduling mechanism can be used effectively in real situations because it can fully use the information on the actual state of shop floors.
---
paper_title: Production scheduling/rescheduling in flexible manufacturing

paper_content:

Scheduling of production in flexible manufacturing systems (FMSs) has been extensively researched over the past years and it continues to attract the interests of both academic researchers and practitioners. The generation of new and modified production schedules is becoming a necessity in today's complex manufacturing environment. Genetic algorithms are used in this paper to obtain an initial schedule. Uncertainties in the production environment and modelling limitations inevitably result in deviations from the generated schedules. This makes rescheduling or reactive scheduling essential. Four different types of uncertainties that normally cause discrepancies between the actual output and the planned output are considered in this paper. These include unforeseen machine breakdowns, increased order priority, rush orders arrival and order cancellations. In this paper, the current status of the shop is considered while rescheduling. The proposed algorithms revise only those operations that must be reschedule...
---
paper_title: Scheduling/rescheduling in the manufacturing operating system environment†

paper_content:

Abstract A scheduling/rescheduling procedure is proposed for real-time control of a computerized manufacturing facility managed by a central manufacturing operating system. The procedure implies schedule revisions upon significant operational changes such as machine breakdowns. Experiments to evaluate the total production time of a computerized manufacturing system with breakdowns under scheduling/rescheduling have yielded advantages of between 25% to 7-0% compared to fixed sequencing and priority despatching procedures, respectively. Computation times required for the scheduling procedures on a CDC 65OO/66OO have also been studied. The scheduling/rescheduling procedure for an actual facility required less than two minutes, and the computation time can be regulated by the selection of parameters in an approximate method of scheduling. A shorter version of this article has appeared in Japanese (Yamumoto and Nof 1982)
---
paper_title: Predictable scheduling of a single machine subject to breakdowns

paper_content:

The predictive production schedule has two important functions; allocating shop resources to the different jobs to optimize some measure of shop performance and serving as a basis for planning activities such as material procurement, preventive maintenance and delivery of orders to external or internal customers. This schedule is modified during execution on the occurrence of disruptions such as machine breakdowns. The schedule modification process may delay or render infeasible the execution of activities planned on the basis of the predictive schedule. Thus it is of interest to develop predictive schedules which can absorb disruptions without affecting planned activities while maintaining high shop performance. A predictable scheduling approach is presented, where the predictive schedule is built with such objectives. The effects of disruptions on planned activities are measured by the difference between planned and realized job completion times. The specific scheduling model considered is minimizing ma...
---
paper_title: Matchup Scheduling with Multiple Resources, Release Dates and Disruptions

paper_content:

This paper considers the rescheduling of operations with release dates and multiple resources when disruptions prevent the use of a preplanned schedule. The overall strategy is to follow the preschedule until a disruption occurs. After a disruption, part of the schedule is reconstructed to match up with the preschedule at some future time. Conditions are given for the optimality of this approach. A practical implementation is compared with the alternatives of preplanned static scheduling and myopic dynamic scheduling. A set of practical test problems demonstrates the advantages of the matchup approach. We also explore the solution of the matchup scheduling problem and show the advantages of an integer programming approach for allocating resources to jobs.
---
paper_title: Adaptive/predictive scheduling: review and a general framework

paper_content:

Abstract Abstract. Effective production scheduling can have a dramatic impact on manufacturing productivity. In modern automated manufacturing systems, the ability to revise and adjust the schedule can help reduce indirect costs which comprise a large portion of manufacturing costs in those systems. The objective of the research discussed here has been to study the feasibility of automatically scheduling multi-machine complexes and adjusting the schedule on a real-time basis by a unified computer system. We arc investigating selective real-time schedule adaptation by distinguishing between schedule generation and regeneration tasks (which might not be cost-effective) from schedule adaptation/recovery tasks (basically, causing less cosily disruption of the original plans). The article describes our general framework for automatic adaptive/predictive scheduling that includes five main functions: scheduler; monitor;comparator; resolvcr; recovery adaptor. Some experimental results demonstrating the effectiven...
---
paper_title: Minimizing Makespan on a Single Batch Processing Machine with Dynamic Job Arrivals

paper_content:

We consider the problem of minimizing makespan Cmax on a single batch processing machine in the presence of dynamic job arrivals. The batch processing machine can process up to B jobs simultaneously. The processing time of a batch is given by the processing time of the longest job in the batch. We present polynomial and pseudopolynomial-time algorithms for several special cases, develop efficient heuristics for the general problem and evaluate their performance through extensive computational experiments. Our results indicate that several of the heuristics have an excellent average performance with a modest computational burden.
---
paper_title: Match-up scheduling under a machine breakdown

paper_content:

When a machine breakdown forces a modified flow shop (MFS) out of the prescribed state, the proposed strategy reschedules part of the initial schedule to match up with the preschedule at some point. The objective is to create a new schedule that is consistent with the other production planning decisions like material flow, tooling and purchasing by utilizing the time critical decision making concept. We propose a new rescheduling strategy and a match-up point determination procedure through a feedback mechanism to increase both the schedule quality and stability. The proposed approach is compared with alternative reactive scheduling methods under different experimental settings.
---
paper_title: Routing-based reactive scheduling policies for machine failures in dynamic job shops

paper_content:

A scheduling and control system can be viewed as a vital component of modern manufacturing systems that determines companies' overall performance in their respective supply chains. This paper studies reactive scheduling policies developed against unexpected machine failures. These reactive policies are based on rerouting the jobs to their alternative machines when their primary machine fails. Depending on the subset of the jobs considered for rerouting, the long-term performance of four policies are tested under various conditions. Expecting that these rerouting policies would bring an extra load for a material-handling system (MHS), a dynamic job shop environment was studied with and without a MHS. It is shown that the proper selection of a good reactive policy is based not only on the system characteristics such as utilization, machine down times and frequency of machine failures, but also on the MHS capacity (in terms of speed and number of MH devices). The extensive experiments show that when the MHS ...
---
paper_title: Predictable scheduling of a single machine with breakdowns and sensitive jobs

paper_content:

Production schedules released to the shop floor have two important functions: allocating shop resources to different jobs to optimize some measure of shop performance and serving as a basis for planning external activities such as material procurement, preventive maintenance and delivery of orders to customers. Schedule modification may delay or render infeasible the execution of external activities planned on the basis of the predictive schedule. Thus it is of interest to develop predictive schedules that can absorb disruptions without affecting planned external activities while maintaining high shop performance. We present a predictable scheduling approach, that inserts additional idle time into the schedule to absorb the impacts of breakdowns. The effects of disruptions on planned support activities are measured by the deviations of job completion times in the realized schedule from those in the predictive schedule. We apply our approach to minimizing total tardiness on a single machine with stochastic...
---
paper_title: A Rescheduling Procedure for Manufacturing Systems Under Random Disruptions

paper_content:

Short to medium term schedules of a manufacturing system are often produced a priori in order to direct production operations and to support other planning activities such as tooling, raw material delivery and resource allocation. Unfortunately, as soon as the a priori schedule is released to the shop, myriad disturbances will arise which render the schedule obsolete. “Rescheduling” is a means of restoring the operations schedule when such a disruption has occurred. Complications arise when schedule changes induce major cost impact to other planning activities which use the a priori schedule as a basis. This problem of shop rescheduling is of great practical importance and has been addressed in various areas of Operations Research including stochastic scheduling and combinatorial optimization.
---
paper_title: Dynamic scheduling of manufacturing job shops using genetic algorithms

paper_content:

Most job shop scheduling methods reported in the literature usually address the static scheduling problem. These methods do not consider multiple criteria, nor do they accommodate alternate resources to process a job operation. In this paper, a scheduling method based on genetic algorithms is developed and it addresses all the shortcomings mentioned above. The genetic algorithms approach is a schedule permutation approach that systematically permutes an initial pool of randomly generated schedules to return the best schedule found to date.
---
paper_title: ROBUSTNESS MEASURES AND ROBUST SCHEDULING FOR JOB SHOPS

paper_content:

Abstract A robust schedule is defined as a schedule that is insensitive to unforeseen shop floor disturbances given an assumed control policy. In this paper, a definition of schedule robustness is developed which comprises two components: post-disturbance make-span and post-disturbance makespan variability. We have developed robustness measures and robust scheduling methods for the case where a “right-shift” control policy is used. On occurrence of a disruption, the right-shift policy maintains the scheduling sequence while delaying the unfinished jobs as much as necessary to accommodate the disruption. An exact measure of schedule robustness is derived for the case in which only a single disruption occurs within the planning horizon. A surrogate measure is developed for the more complex case in which multiple disruptions may occur. This surrogate measure is then embedded in a genetic algorithm to generate robust schedules for job-shops. Experimental results show that robust schedules significantly outper...
---
paper_title: Predictable scheduling of a single machine subject to breakdowns

paper_content:

The predictive production schedule has two important functions; allocating shop resources to the different jobs to optimize some measure of shop performance and serving as a basis for planning activities such as material procurement, preventive maintenance and delivery of orders to external or internal customers. This schedule is modified during execution on the occurrence of disruptions such as machine breakdowns. The schedule modification process may delay or render infeasible the execution of activities planned on the basis of the predictive schedule. Thus it is of interest to develop predictive schedules which can absorb disruptions without affecting planned activities while maintaining high shop performance. A predictable scheduling approach is presented, where the predictive schedule is built with such objectives. The effects of disruptions on planned activities are measured by the difference between planned and realized job completion times. The specific scheduling model considered is minimizing ma...
---
paper_title: One-machine rescheduling heuristics with efficiency and stability as criteria

paper_content:

Abstract Heuristics for the problem of rescheduling a machine on occurrence of an unforeseen disruption are developed. The criteria include minimization of the makespan (schedule efficiency) and the impact of the schedule change (schedule stability). The impact of schedule change is a non-regular performance measure defined in two ways: (1) the starting time deviations between the new schedule and the original schedule, and (2) a measure of the sequence difference between the two schedules. Three local search procedures are developed for the bicriterion problem and a set of experiments are conducted to test the efficacy of the heuristics. The heuristic solutions are shown to be effective in that the schedule stability can be increased significantly with little or no sacrifice in makespan.
---
paper_title: Production Scheduling and Rescheduling with Genetic Algorithms

paper_content:

A general model for job shop scheduling is described which applies to static, dynamic and non-deterministic production environments. Next, a Genetic Algorithm is presented which solves the job shop scheduling problem. This algorithm is tested in a dynamic environment under different workload situations. Thereby, a highly efficient decoding procedure is proposed which strongly improves the quality of schedules. Finally, this technique is tested for scheduling and rescheduling in a non-deterministic environment. It is shown by experiment that conventional methods of production control are clearly outperformed atreasonable runtime costs.
---
paper_title: Modern heuristic techniques for combinatorial problems

paper_content:

Part 1 Introduction: combinatorial problems local and global optima heuristics. Part 2 Simulated annealing: the basic method enhancements and modifications applications conclusions. Part 3 Tabu search: the tabu framework broader aspects of intensification and diversification tabu search applications connections and conclusions. Part 4 Genetic algorithms: basic concepts a simple example extensions and modifications applications conclusions. Part 5 Artificial neural networks: neural networks combinatorial optimization problems the graph bisection problem the graph partition problem the travelling salesman problem scheduling problems deformable templates inequality constraints, the Knapsack problem summary. Part 6 Lagrangian relaxation: overview basic methodology Lagrangian heuristics and problem reduction determination of Lagrange multipliers dual ascent tree search applications conclusions. Part 7 Evaluation of heuristic performance: analytical methods empirical testing statistical inference conclusions.
---
paper_title: Reactive Scheduling - Improving the Robustness of Schedules and Restricting the Effects of Shop Floor Disturbances by Fuzzy Reasoning

paper_content:

Abstract Practical scheduling usually has to reach to many unpredictable events and uncertainties in the production environment. Although often possible in theory, it is undesirable to reschedule from scratch in such cases. Since the surrounding organization will be prepared for the predicted schedule, it is important to change only those features of the schedule that are necessary. We show how, on one side, fuzzy logic can be used to support the construction of schedules that are robust with respect to changes due to certain types of event. On the other side, we show how a reaction can be restricted to a small environment by means of fuzzy constraints and a repair-based problem-solving strategy. We demonstrate the proposed representation and problem-solving method by introducing a scheduling application in a steelmaking plant. We construct a preliminary schedule by taking into account only the most likely duration of operations. This schedule is iteratively "repaired" until some threshold evaluation is found. A repair is found with a local search procedure based on Tabu Search. Finally, we show which events can lead to reactive scheduling and how this is supported by the repair strategy.
---
paper_title: Dynamic scheduling of FMS using a real-time genetic algorithm

paper_content:

The paper presents a genetic algorithm capable of generating optimised production plans in flexible manufacturing systems. The ability of the system to generate alternative plans following part-flow changes and unforeseen situations is particularly stressed (dynamic scheduling). Two contrasting objectives represented by the reduction of machine idle-times, thanks to dynamic scheduling computation and the reduction of the makespan, are taken into account by the proposed system. The key-point is the real-time response obtained by an optimised evolutionary strategy capable of minimising the number of genetic operations needed to reach the optimal schedule in complex manufacturing systems.
---
paper_title: Improving Robustness and Flexibility of Tardiness and Total Flowtime Job Shops Using Robustness Measures

paper_content:

Abstract The traditional focus of scheduling research is on finding schedules with a low implementation cost. However, in many real world scheduling applications finding a robust or flexible schedule is just as important. A robust schedule is a quality schedule expected to still be acceptable if something unforeseen happens, while a flexible schedule is a quality schedule expected to be easy to change. In this paper, the robustness and flexibility of schedules produced by minimising different robustness measures are investigated. One kind of robustness measure is the neighbourhood-based robustness measure, in which the basic idea is to minimise the implementation costs of a set of schedules located around a centre schedule. For tardiness problems another way of improving robustness is to increase the slack of the schedule by minimising lateness instead of tardiness. The problems used in the experiments are maximum tardiness, summed tardiness and total flow-time job shop problems. The experiments showed that the neighbourhood-based robustness measures improves robustness for all the problem types. Flexibility is improved for maximum tardiness and loose summed tardiness problems, while it is not improved for tight summed tardiness problems and total flow-time problems. The lateness-based robustness measures are found to also improve robustness and in some cases flexibility for the same problems, but the improvement is not as substantial as with the neighbourhood-based measures. Based on these observations, it is conjectured that neighbourhood-based robustness can be expected to improve flexibility on problems with few critical points.
---
paper_title: Intelligent Optimisation Techniques: Genetic Algorithms, Tabu Search, Simulated Annealing and Neural Networks

paper_content:

This work gives a concise introduction to four important optimization techniques, presenting a range of applications drawn from electrical, manufacturing, mechanical, and systems engineering-such as the design of microstrip antennas, digital FIR filters, and fuzzy logic controllers. The book also contains the C programs used to implement the main techniques for those wishing to experiment with them.
---
paper_title: Knowledge-based predictive and reactive scheduling in industrial environments

paper_content:

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.
---
paper_title: Combining knowledge-based systems and simulation to solve rescheduling problems

paper_content:

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.
---
paper_title: A production rescheduling expert simulation system

paper_content:

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.
---
paper_title: On-line fault diagnosis system support for reactive scheduling in multipurpose batch chemical plants

paper_content:

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.
---
paper_title: Knowledge-based reactive scheduling

paper_content:

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...
---
paper_title: Reactive Scheduling Systems

paper_content:

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.
---
paper_title: Reacting to scheduling exceptions in FMS environments

paper_content:

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.
---
paper_title: An intelligent operations scheduling system in a job shop

paper_content:

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.
---
paper_title: Intelligent systems in manufacturing: current developments and future prospects

paper_content:

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.
---
paper_title: A fuzzy logic based production scheduling/rescheduling in the presence of uncertain disruptions

paper_content:

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.
---
paper_title: CABINS: A Framework of Knowledge Acquisition and Iterative Revision for Schedule Improvement and Reactive Repair

paper_content:

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.
---
paper_title: Dynamic scheduling--a survey of research

paper_content:

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.
---
paper_title: Development of a knowledge-based system for dynamic scheduling

paper_content:

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.
---
paper_title: Agent-Based Systems for Intelligent Manufacturing: A State-of-the-Art Survey

paper_content:

Agent technology has been considered as an important approach for developing distributed intelligent manufacturing systems. A number of researchers have attempted to apply agent technology to manufacturing enterprise integration, supply chain management, manufacturing planning, scheduling and control, materials handling, and holonic manufacturing systems. This paper gives a brief survey of some related projects in this area, and discusses some key issues in developing agent-based manufacturing systems such as agent technology for enterprise integration and supply chain management, agent encapsulation, system architectures, dynamic system reconfiguration, learning, design and manufacturability assessments, distributed dynamic scheduling, integration of planning and scheduling, concurrent scheduling and execution, factory control structures, potential tools and standards for developing agent-based manufacturing systems. An extensive annotated bibliography is provided.
---
paper_title: Hierarchy in distributed shop floor control

paper_content:

Abstract This discussion paper examines the role of hierarchy within the domain of shop floor control in manufacturing plants. Specifically, three distinct structures for shop floor control are considered, namely, hierarchical, heterarchical and holonic control systems. Holonic manufacturing is a novel paradigm for manufacturing that tries to merge the best properties of both hierarchical and heterarchical systems, namely, a high and predictable performance with a high robustness against disturbances. The paper identifies the concept of hierarchy in distributed shop floor control as one of the key contributions of holonic manufacturing. In a holonic architecture, the mapping of functions to control units remains flexible, such that decision power can be distributed over these units as needed. Based on the invariants concept of computer science, a modelling framework is proposed to identify the decision making needs of each unit. It can be used not only to describe the behaviour of the system, but also to impose performance and operational guarantees.
---
paper_title: Holonic manufacturing scheduling: architecture, cooperation mechanism and implementation

paper_content:

Abstract A Holonic Manufacturing System (HMS) is a manufacturing system where key elements, such as machines, cells, factories, parts, products, operators, teams, etc., are modeled as `holons' having autonomous and cooperative properties. The decentralized information structure, the distributed decision-making authority, the integration of physical and informational aspects, and the cooperative relationship among holons, make the HMS a new paradigm, with great potential for meeting today's agile manufacturing challenges. Critical issues to be investigated include how to define holons for a given problem context, what should be the appropriate system architecture, and how to design effective cooperation mechanisms for good system performance. In this paper, holonic scheduling is developed for a factory consisting of multiple cells. Relevant holons are identified, and their relationships are delineated through a novel modeling of the interactions among parts, machines, and cells. The cooperation mechanisms among holons are established based on the pricing concept of market economy following `Lagrangian relaxation' of mathematical optimization, and cooperation across cells is performed without accessing individual cells' local information nor intruding on their decision authority. The system also possesses structural recursivity and extendibility. Numerical testing shows that the method can generate near-optimal schedules with quantifiable quality in a timely fashion, and has comparable computational requirements and performance as compared to the centralized method following single-level Lagrangian relaxation. The method thus provides a theoretical foundation for guiding the cooperation among holons, leading to globally near-optimal performance.
---
paper_title: Evaluating the performance of reactive control architectures for manufacturing production control

paper_content:

Abstract The requirement for adaptable and re-configurable control systems for manufacturing has highlighted the inadequacies of traditional centralised control approaches, leading researchers to focus on decentralised approaches. The question of what is the most appropriate control architecture for a given system has led industrial and academic researchers to develop a spectrum of decentralised control architectures ranging from hierarchical to non-hierarchical structures. While current research has confirmed the potential of decentralised architectures, neither extreme of this control architecture spectrum has proven to be the most appropriate choice for a given manufacturing system. Recent research into providing an objective comparison of alternative control architectures has shown that some degree of hierarchy is important for distributed manufacturing control architectures. This paper is concerned with our current investigations into why these partial hierarchies appear to display superior performance.
---
paper_title: Agent-Based Systems for Intelligent Manufacturing: A State-of-the-Art Survey

paper_content:

Agent technology has been considered as an important approach for developing distributed intelligent manufacturing systems. A number of researchers have attempted to apply agent technology to manufacturing enterprise integration, supply chain management, manufacturing planning, scheduling and control, materials handling, and holonic manufacturing systems. This paper gives a brief survey of some related projects in this area, and discusses some key issues in developing agent-based manufacturing systems such as agent technology for enterprise integration and supply chain management, agent encapsulation, system architectures, dynamic system reconfiguration, learning, design and manufacturability assessments, distributed dynamic scheduling, integration of planning and scheduling, concurrent scheduling and execution, factory control structures, potential tools and standards for developing agent-based manufacturing systems. An extensive annotated bibliography is provided.
---
paper_title: Hierarchy in distributed shop floor control

paper_content:

Abstract This discussion paper examines the role of hierarchy within the domain of shop floor control in manufacturing plants. Specifically, three distinct structures for shop floor control are considered, namely, hierarchical, heterarchical and holonic control systems. Holonic manufacturing is a novel paradigm for manufacturing that tries to merge the best properties of both hierarchical and heterarchical systems, namely, a high and predictable performance with a high robustness against disturbances. The paper identifies the concept of hierarchy in distributed shop floor control as one of the key contributions of holonic manufacturing. In a holonic architecture, the mapping of functions to control units remains flexible, such that decision power can be distributed over these units as needed. Based on the invariants concept of computer science, a modelling framework is proposed to identify the decision making needs of each unit. It can be used not only to describe the behaviour of the system, but also to impose performance and operational guarantees.
---
paper_title: Approaches and issues in scheduling a distributed shop-floor environment

paper_content:

Abstract There is increasing trend towards more autonomous and distributed shop-floor organisations. Operational characteristics of such a shop-floor will derive from independently acting but cooperating entities. These would have capabilities for scheduling in relative isolation while resolving conflicts among themselves to maintain consistency between local schedules. We review both negotiation and the emerging behaviour-based methods for scheduling and coordinating distributed entities within both hierarchical and heterarchical control structures. The approaches are reviewed with a focus on the issues that are of practical importance.
---
paper_title: Agents in Overalls: Experiences and Issues in the Development and Deployment of Industrial Agent-Based Systems

paper_content:

Agent technologies have steadily matured in moving from the research laboratory to industrial application over the last ten years. Numerous systems have been deployed or are under advanced development with strong industrial support. These systems suggest important lessons for both industry and researchers. From an industrial perspective, these examples reflect trends in both business and technology that make agents an increasingly attractive commercial tool. From a research perspective, these examples identify important gaps in agent technology that merit the attention of academicians.
---
paper_title: A multi-contract net protocol for dynamic scheduling in flexible manufacturing systems (FMS)

paper_content:

Deals with a multi-agent architecture and a negotiation protocol for the dynamic scheduling of flexible manufacturing systems. The originality of the multi-agent architecture resides in the existence of task agents and resource agents. The multi-contract net protocol proposed, is an innovation with regard to the contract-net protocol due to the way that it makes it possible to negotiate several tasks concurrently, in real time and with more optimal results taking into account uncertainty and conflict situations in the scheduling of operations. The paper, also, stresses the efficiency and the optimality of the distributed implementation.
---
paper_title: Utility and stability measures for agent-based dynamic scheduling of steel continuous casting

paper_content:

This paper describes a new model for robust predictive/reactive scheduling of steel continuous casting based on the use of multi-agents, tabu search and heuristic approaches. A continuous caster agent generates a predictive production schedule taking into account manufacturing requirements and local constraints using tabu search. The predictive schedule is modifies so as to minimize deviation between the performance measure values of the realized and predictive schedules in order to react to real-time events. We propose several schedule-repair and complete reschedule strategies to handle the real-time events, evaluate and compare their performance. The decision as to whether to locally repair the schedule or reschedule from scratch (complete reschedule) is based on three measures: robustness, utility and stability. Utility measures the change in schedule objective following schedule revision. Stability measures the deviation from the original schedule caused by schedule revision to quantify the undesirability of making large changes to the initial predictive schedule unless absolutely necessary. Robustness combines the utility and stability measures. In order to investigate the performance of these measures and strategies, simulation experiments were carried out and results are reported.
---
paper_title: Multi-agent system for dynamic scheduling and control in manufacturing cells

paper_content:

Describes an intelligent real time cell control architecture for flexible manufacturing systems. This architecture is based on the multi-agent concept of the distributed artificial intelligence. We propose an actor architecture. This multi-agent prototype system involves the following functions: scheduling, dispatching, monitoring and error handling. A new contract protocol for dynamic scheduling is presented. The purpose of this protocol is to dynamically assign operations to the resources of the manufacturing system in order to accomplish the proposed tasks. This protocol is able to deal with exceptions.
---
paper_title: A computational study on design and performance issues of multi-agent intelligent systems for dynamic scheduling environments

paper_content:

Abstract Multi-Agent Intelligent Systems (MAIS) are loosely-coupled network of problem solving systems that, whenever needed, work together with each other to dynamically solve problems that none of the system can individually solve. Among the advantages of the MAIS, when compared to the centralized systems, are increased reliability, faster problem solving, decreased communication, and more flexibility. Learning to coordinate the actions is one of the most important task in MAIS. In the current research, we use a widely reported dynamic job shop scheduling simulation model that uses distributed genetic learning of job scheduling strategies (Pendharkar, P.C., 1997. Doctoral Dissertation, Graduate School, Southern Illinois University at Carbondale; Pendharkar, P.C., 1998. Distributed learning of objectives for adaptive scheduling (in review); Pendharkar, P.C., Bhattacharyya, S., 1997. Multi-agent learning in distributed artificial intelligence. Proc. 2nd INFORMS Conference on Information Systems and Technology. San Diego, CA, p.156–163; Bhattacharyya, S., Koehler, G.J., 1997. Learning by objectives for adaptive shop-floor learning. Decision Sciences (to appear). Aytug, H., Koehler, G.J., Snowdon, J.L., 1994. Genetic learning of dynamic scheduling within a simulation environment, Computers and Operations Research, 21 (8), 909–925; Aytug, H., Bhattacharyya, S., Koehler, G.J., Snowdon, J.L., 1994. A review of machine learning in scheduling, IEEE Transactions on Engineering Management 41 (2) ) and study the performance and design issues in multi-agents information systems for dynamic scheduling in manufacturing. Among the design issue and performance issues considered in this research are coordination between agents, number of agents, and frequency of learning. Our results indicate that coordination between agents, and learning frequency play a significant role in the performance of multi-agent intelligent systems.
---
paper_title: Multi-agent architecture for distributed monitoring in flexible manufacturing systems (FMS)

paper_content:

This paper describes an intelligent distributed monitoring architecture for flexible manufacturing systems (FMS) based on the multi-agent paradigm. The proposed approach models the FMS by a society of cognitive agents, which monitor a set of heterogeneous resources. These agents have sufficient knowledge for the decision-making and they co-operate together in order to achieve the FMS monitoring functions. The originality of this approach resides in the total distribution of the monitoring functions over the agents and the co-operation of these agents by the contract net protocol for the real-time supervision. These characteristics improve flexibility, extensibility, real-time running, autonomy, fast reaction to faults, and development cost. Experimental results developed in simulation show the feasibility and the potentialities of the proposed multi-agent architecture for distributed monitoring where concepts such us flexibility, co-ordination, reactivity and integration are involved.
---
paper_title: A Multi-Agent Architecture for Dynamic Scheduling of Steel Hot Rolling

paper_content:

Steel production is a complex process and finding coherent and effective schedules for the wide variety of production steps, in a dynamic environment, is a challenging task. In this paper, we propose a multi-agent architecture for integrated dynamic scheduling of the hot strip mill (HSM) and the continuous caster. The scheduling systems of these processes have very different objectives and constraints, and operate in an environment where there is a substantial quantity of real-time information concerning production failures and customer requests. Each process is assigned to an agent which independently, seeks an optimal dynamic schedule at a local level taking into account local objectives, real-time information and information received from other agents. Each agent can react to real-time events in order to fix any problems that occur. We focus here, particularly, on the HSM agent which uses a tabu search heuristic to create good predictive–reactive schedules quickly. The other agents simulate the production of the coil orders and the real-time events, which occur during the scheduling process. When real-time events occur on the HSM, the HSM agent might decide whether to repair the current schedule or reschedule from scratch. To address this problem, a range of schedule repair and complete rescheduling strategies are investigated and their performance is assessed with respect to measures of utility, stability and robustness, using an experimental simulation framework.
---
paper_title: Contract Net Protocol for Cooperative Optimisation and Dynamic Scheduling of Steel Production

paper_content:

This paper describes a negotiation protocol proposed for inter-agent cooperation in a multi-agent system we developed for optimisation and dynamic integrated scheduling of steel production. The negotiation protocol is a two-level bidding mechanism based on the contract net protocol. The purpose of this protocol is to allow the agents to cooperate and coordinate their actions in order to find globally near-optimal robust schedules, which are able to optimise the original production goals whilst minimising the disruption caused by the occurrence of unexpected real-time events. Experimental results show the performance of this negotiation protocol to coordinate the agents in generating good quality robust schedules. This performance is evaluated in terms of stability and utility measures used to evaluate the robustness of the steel production processes in the presence of real-time events.
---
paper_title: A distributed architecture and negotiation protocol for scheduling in manufacturing systems

paper_content:

Abstract This paper deals with a new architecture and negotiation protocol for the dynamic scheduling of Manufacturing Systems. The architecture is based on two paradigms: Multi-Agent Systems and Holonic Systems. The main contribution in the architecture is the development of Holons representing tasks and resources. The well-known Contract Net Protocol [R. Davis, R. Smith, Negotiation as a metaphor for distributed problem solving, Artificial Intelligence, 20, (1), (1983) 63–109] has been adapted to handle temporal constraints and to deal with scheduling conflicts. The purpose of this protocol is to dynamically assign operations to the resources of the Manufacturing System to accomplish the proposed tasks. This protocol involves a renegotiation phase whenever exceptions appear. It also deals with conflict situations, namely, with the case of the `indecision problem'. The used approach assumes that deadlines are the most important constraints to consider. Thus the acceptance or refusal of a resource for a specific operation depends on the capability of executing the operation within the specified deadline.
---
paper_title: An Autonomous Manufacturing Collective for Job Shop Scheduling

paper_content:

This paper describes an ongoing research project in distributed, agent-based manufacturing scheduling systems which exhibit collective system behavior. A scheduling system is described which exhibits purely low-level, reactive behavior. Two types of agents comprise the collective: part agents and machine agents. The collective is a mixedinitiative system in which agents representing parts attempt to maximize part flow to the next machine and agents representing machines attempt to maximize their utilization. Agents of the collective contain only local knowledge: a machine agent schedules operations on its machine and a part agent commits available parts to machine operations. This architecture provides an opportunity to use reinforcement learning techniques to allow an agent of the collective to improve performance by learning patterns of local interactions over time. Furthermore, both agent types of the collective exhibit anytime behavior by continuously computing the next decision until it is required to commit a decision to a fellow agent. Such agent information will bc of value in further research, the goal of which is to allow the dynamic collective adapts its architecture at runtime in response to unresolvable scheduling conflicts by creating temporary, higher-level agents opportunistically to handle particular situations. The architecture of the Autonomous Manufacturing Collective (AMC) is described herein.
---
paper_title: The AARIA Agent Architecture: An Example of Requirements-Driven Agent-Based System Design

paper_content:

Designs for real-world agent-based systems must reflect domain requirements as well as the technical capabilities of agents. This needs-driven approach is being applied in AARIA (Autonomous Agents for Rock Island Arsenal), an industrial-strength agent-based factory scheduling and simulation system being developed for an Army manufacturing facility. A review of the operations of Rock Island in the light of broader industrial needs yields seven requirements. After introducing the AARIA agent community, we summarize each of these requirements and how AARIA supports it. More information is available at http://www.aaria.uc.edu . The AARIA Agent Community In discrete manufacturing, Parts move through a network of Unit Processes (UP’s) and Buffers. Each UP acquires one or more input Parts from Buffers of the needed types, and engages certain Resources to produce one or more output Parts into appropriate Buffers. In AARIA, we use linguistic case theory [Parunak 95] over a set of declarative sentences describing the domain to identify candidate agents, then refine this population using the requirements. Figure 1 shows the resulting community, with its flows of Parts and Engagements for Resources along orthogonal axes that intersect at UP’s. Previous research on agentbased factory control and scheduling (including our own) differs widely on what is represented as an agent: levels in a hierarchical decomposition of the factory (Butler & Ohtsubo 92, Tilley & Williams 92, Parunak 87), Resources (Shaw & Whinston 85, Baker 96, Parunak et al. 87, Heaton 94), or Parts (Maley 88, Duffie et al. 88). In AARIA, Separate full-fledged agents represent parts, resources and unit processes with substantially equal intelligence and responsibility in each type of agent. The AARIA system has a number of other important enhancements from past work in multi-agent manufacturing. The system incorporates new features for schedule optimization and fault recovery. Unlike many past systems, these agents are being implemented in an agent infrastructure that allows true agent behavior by supporting true broadcast and multicast communications, subject based mail handling, multithreaded agent activity, multi-platform instantiation, agent migration, and the implementation of multiple scheduled activities within an agent. Also, the system is being implemented with dual functionality so it can run a real factory or run in simulation mode. The sections below outline AARIA's seven design requirements and highlight other enhancements to past work. Meeting the AARIA Requirements Uniformity (An operation at the boundary of AARIA interacts with external suppliers or customers in the same way that it does with internal ones.)—Both an external customer and an internal UP draw from Buffers, and both an external supplier and a UP feed Buffers. Thus UP’s represent both customers and suppliers. This result offers a novel approach to supply-chain integration. Traditionally, each firm in a supply chain is viewed as a monolithic entity with its own internal mechanisms, requiring a special set of mechanisms to interact with other firms. AARIA views each firm as an internal supply chain. As a result, the interfaces between AARIA agents within a firm are the same as those between one firm and another, and integrating multiple AARIA-based firms into a supply chain becomes immediate and transparent. Metamorphosis (The system maintains continuity between different entities that represent different stages in a common life cycle, for example, an order for a part, the part itself, and its production history.)—AARIA distinguishes persistent agents, whose behavior does not change over the time scale involved in daily shop operation, from transient agents, which represent interactions among persistent agents and which go through a In pu t P ar ts Unit Process Buffer Buffer Buffer Buffer Buffer Buffer
---
paper_title: Survey of resource allocation methods for distributed manufacturing systems

paper_content:

Distributed manufacturing systems are more flexible in their arrangement and use of their resources. This permits a more dynamic and opportunistic allocation of manufacturing resources to work elements than is possible with today's centralized allocation systems. However, unlike solving the problem from a single solver view, there is no absolute control or tight coordination over how and when to decompose the problem, when to undertake a solution or the procedure for verifying consistency. Such activities will largely be left to the distributed entities to decide either individually or jointly. As a consequence the resulting allocations may suffer and induce myopic behaviour lacking in stability and regularity in the performance of the total system. Thus, the issues connected with solving the problem often move beyond the pure algorithmic focus of computation to include how the problem is decomposed, how or to whom it is assigned, and the organization for solving the subproblems, strategies used for resol...
---
paper_title: Modeling Manufacturing Systems: from Aggregate Planning to Real-Time Control

paper_content:

Modelling Manufacturing Systems: an Introduction: P. Brandimarte, A. Villa: Introduction and Overview of the Contributions.- For Further Reading.- References.- From the Aggregate Plan to Lot-Sizing in Multi-level Production Planning: J.-C. Hennet: Introduction.- The Planning Process.- The Lot-Sizing Problem.- Example.- Conclusion.- References.- Shop Floor Scheduling in Discrete Parts Manufacturing: G. J. Meester, J. M. J. Schutten, S. L. van de Velde, W. H. M. Zijm: Introduction.- Basic Decomposition Approach.- Multi-Resource Scheduling.- Set-Up Times.- Convergent and Divergent Job Routings.- Further Extensions and Practical Aspects.- JOBPLANNER.- Conclusions.- References.- Appendix A: Derivation of Set-Up Jobs.- Integrating Layout Design and Material Flow Management in Assembly Systems: M. Lucertini, D. Pacciaretti, A. Pacifici: Introduction.- Statement of the Problem.- Feasibility Properties.- Optimization Properties.- Conclusions.- References.- Appendix: Proofs of Theorems.- Reactive Scheduling in Real Time Production Control: E. Szelke, L. Monostori: Reactive Operation Management - Predictive, Reactive and Proactive Scheduling.- Models of Reactive and Proactive Scheduling Problems.- Solution Approaches - Methods, Techniques, Tools.- Conclusions: Future Research Issues in the Field.- References.- Simulation within CAD-Environment: P. Kopacek, G. Kronreif, T. Perme: Introduction.- Simulation System LASIMCO.- Simulation in Robotics - ROMOBIL/SITAR.- Conclusion.- References.- Model of Material Handling and Robotics.- C.-Y. Huang: Introduction.- Traditional Models of Material Handling and Robotics.- Facility Description Language (FDL).- Concurrent Flexible Specifications (CFS) for Material Handling and Robotics.- Discussion and Conclusion.- References.- A Simultaneous Approach for IMS Design: a Possibility Based Approach: G. Perrone, S. Noto La Diega: Introduction.- The Decisional Environment for Strategic IMS Design.- The Strategic IMS Design Decision-Making Tool: The Possibilistic Programming Theory.- The Possibilistic Framework for Strategic FMS Design.- Numerical Example.- Conclusions.- References.- Adaptive Production Control in Modern Industries: K. N. McKay, J. A. Buzacott: Introduction.- Motivation - Inherent Uncertainty.- Applying Production Control Methods - A Perspective.- Production Control Concepts for Immaturity or Uncertainty.- Conclusion.- Acknowledgments.- References.
---
paper_title: Evaluating the performance of reactive control architectures for manufacturing production control

paper_content:

Abstract The requirement for adaptable and re-configurable control systems for manufacturing has highlighted the inadequacies of traditional centralised control approaches, leading researchers to focus on decentralised approaches. The question of what is the most appropriate control architecture for a given system has led industrial and academic researchers to develop a spectrum of decentralised control architectures ranging from hierarchical to non-hierarchical structures. While current research has confirmed the potential of decentralised architectures, neither extreme of this control architecture spectrum has proven to be the most appropriate choice for a given manufacturing system. Recent research into providing an objective comparison of alternative control architectures has shown that some degree of hierarchy is important for distributed manufacturing control architectures. This paper is concerned with our current investigations into why these partial hierarchies appear to display superior performance.
---
paper_title: Agent-Based Systems for Intelligent Manufacturing: A State-of-the-Art Survey

paper_content:

Agent technology has been considered as an important approach for developing distributed intelligent manufacturing systems. A number of researchers have attempted to apply agent technology to manufacturing enterprise integration, supply chain management, manufacturing planning, scheduling and control, materials handling, and holonic manufacturing systems. This paper gives a brief survey of some related projects in this area, and discusses some key issues in developing agent-based manufacturing systems such as agent technology for enterprise integration and supply chain management, agent encapsulation, system architectures, dynamic system reconfiguration, learning, design and manufacturability assessments, distributed dynamic scheduling, integration of planning and scheduling, concurrent scheduling and execution, factory control structures, potential tools and standards for developing agent-based manufacturing systems. An extensive annotated bibliography is provided.
---
paper_title: An experimental benchmarking of two multi-agent architectures for production scheduling and control

paper_content:

The paper provides a first experimental contribution to the validation and comparison of multi-agent heterarchical architectures in order to point out their limits, their main peculiarities and real applicability. For this purpose, the behaviours of two particular control solutions, characterised by a different degree of decision-making delegation assigned to physical and information units in the production system, have been simulated. The experimental campaign is divided into three trials, in order to measure the performances of the two architectures not only under stable and predictable conditions, but also in case of unexpected events, such as the release of urgent manufacturing orders and the occurrence of failures in production resources.
---
paper_title: Hierarchy in distributed shop floor control

paper_content:

Abstract This discussion paper examines the role of hierarchy within the domain of shop floor control in manufacturing plants. Specifically, three distinct structures for shop floor control are considered, namely, hierarchical, heterarchical and holonic control systems. Holonic manufacturing is a novel paradigm for manufacturing that tries to merge the best properties of both hierarchical and heterarchical systems, namely, a high and predictable performance with a high robustness against disturbances. The paper identifies the concept of hierarchy in distributed shop floor control as one of the key contributions of holonic manufacturing. In a holonic architecture, the mapping of functions to control units remains flexible, such that decision power can be distributed over these units as needed. Based on the invariants concept of computer science, a modelling framework is proposed to identify the decision making needs of each unit. It can be used not only to describe the behaviour of the system, but also to impose performance and operational guarantees.
---
paper_title: An architecture and a negotiation protocol for the dynamic scheduling of manufacturing systems

paper_content:

This paper deals with a new architecture and negotiation protocol for the dynamic scheduling of manufacturing systems. The architecture is based on the paradigm of distributed intelligence and multi-agent systems. In what concerns the architecture, this paper has two original contributions: the existence of agents representing tasks together with agents representing resources and the important role of the resource manager agent. A new negotiation protocol for manufacturing systems is also presented in this paper. The purpose of this protocol is to dynamically assign operations to the resources of the manufacturing system in order to accomplish the proposed tasks. This protocol involves a renegotiation phase whenever exceptions appear. >
---
paper_title: Holonic manufacturing scheduling: architecture, cooperation mechanism and implementation

paper_content:

Abstract A Holonic Manufacturing System (HMS) is a manufacturing system where key elements, such as machines, cells, factories, parts, products, operators, teams, etc., are modeled as `holons' having autonomous and cooperative properties. The decentralized information structure, the distributed decision-making authority, the integration of physical and informational aspects, and the cooperative relationship among holons, make the HMS a new paradigm, with great potential for meeting today's agile manufacturing challenges. Critical issues to be investigated include how to define holons for a given problem context, what should be the appropriate system architecture, and how to design effective cooperation mechanisms for good system performance. In this paper, holonic scheduling is developed for a factory consisting of multiple cells. Relevant holons are identified, and their relationships are delineated through a novel modeling of the interactions among parts, machines, and cells. The cooperation mechanisms among holons are established based on the pricing concept of market economy following `Lagrangian relaxation' of mathematical optimization, and cooperation across cells is performed without accessing individual cells' local information nor intruding on their decision authority. The system also possesses structural recursivity and extendibility. Numerical testing shows that the method can generate near-optimal schedules with quantifiable quality in a timely fashion, and has comparable computational requirements and performance as compared to the centralized method following single-level Lagrangian relaxation. The method thus provides a theoretical foundation for guiding the cooperation among holons, leading to globally near-optimal performance.
---
paper_title: MetaMorph: An Adaptive Agent-Based Architecture for Intelligent Manufacturing

paper_content:

Global competition and rapidly changing customer requirements are forcing major changes in the production styles and configuration of manufacturing organizations. Traditional centralized manufacturing systems are not able to meet such requirements. This paper proposes an agent-based approach for dynamically creating and managing agent communities in such widely distributed and everchanging manufacturing environments. After reviewing the research literature, an adaptive multi-agent manufacturing system architecture called MetaMorph is presented and its main features are described. Such architecture facilitates multi-agent coordination by minimizing communication and processing overheads. Adaptation is facilitated through organizational structural change and two learning mechanisms: learning from past experiences and learning future agent interactions by simulating future dynamic, emergent behaviours. The MetaMorph architecture also addresses other specific requirements for next generation manufacturing sys...
---
paper_title: The state of the art in intelligent real-time FMS control: a comprehensive survey

paper_content:

Flexible manufacturing systems (FMS) have been developed with the hope that they would provide a means to tackle a threefold challenge — better quality, lower cost and shorter lead times — by integrating machine tools, robots, material handling and storage systems, and computers. Control of the integrated system presented a new set of problems as well as challenges, which have been receiving considerable attention from the academic community as well as from industrial system users. Intelligent control, which involves using computers to assist in decision making at various stages of the control process, has been advocated by many researchers as a possible avenue to reach a solution to these problems. This paper provides a review of the state of the art in intelligent control of FMS, in an attempt to supplement earlier general reviews via a more focused perspective. The principles of several techniques, namely simulation, knowledge based, example based, petri nets, and hybrid approaches are briefly introduced, and publications are reviewed, followed by discussions ontheir potential. Suggestions for further research and development are also enumerated.
---
paper_title: Evolutionary algorithms, simulated annealing, and Tabu search: a comparative study

paper_content:

Evolutionary algorithms, simulated annealing (SA), and Tabu Search (TS) are general iterative algorithms for combinatorial optimization. The term evolutionary algorithm is used to refer to any probabilistic algorithm whose design is inspired by evolutionary mechanisms found in biological species. Most widely known algorithms of this category are Genetic Algorithms (GA). GA, SA, and TS have been found to be very effective and robust in solving numerous problems from a wide range of application domains.Furthermore, they are even suitable for ill-posed problems where some of the parameters are not known before hand. These properties are lacking in all traditional optimization techniques. In this paper we perform a comparative study among GA, SA, and TS. These algorithms have many similarities, but they also possess distinctive features, mainly in their strategies for searching the solution state space. the three heuristics are applied on the same optimization problem and compared with respect to (1) quality of the best solution identified by each heuristic, (2) progress of the search from initial solution(s) until stopping criteria are met, (3) the progress of the cost of the best solution as a function of time, and (4) the number of solutions found at successive intervals of the cost function. The benchmark problem was is the floorplanning of very large scale integrated circuits. This is a hard multi-criteria optimization problem. Fuzzy logic is used to combine all objective criteria into a single fuzzy evaluation function, which is then used to rate competing solutions.© (1998) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only.
---
paper_title: Survey of resource allocation methods for distributed manufacturing systems

paper_content:

Distributed manufacturing systems are more flexible in their arrangement and use of their resources. This permits a more dynamic and opportunistic allocation of manufacturing resources to work elements than is possible with today's centralized allocation systems. However, unlike solving the problem from a single solver view, there is no absolute control or tight coordination over how and when to decompose the problem, when to undertake a solution or the procedure for verifying consistency. Such activities will largely be left to the distributed entities to decide either individually or jointly. As a consequence the resulting allocations may suffer and induce myopic behaviour lacking in stability and regularity in the performance of the total system. Thus, the issues connected with solving the problem often move beyond the pure algorithmic focus of computation to include how the problem is decomposed, how or to whom it is assigned, and the organization for solving the subproblems, strategies used for resol...
---
paper_title: Evaluating the performance of reactive control architectures for manufacturing production control

paper_content:

Abstract The requirement for adaptable and re-configurable control systems for manufacturing has highlighted the inadequacies of traditional centralised control approaches, leading researchers to focus on decentralised approaches. The question of what is the most appropriate control architecture for a given system has led industrial and academic researchers to develop a spectrum of decentralised control architectures ranging from hierarchical to non-hierarchical structures. While current research has confirmed the potential of decentralised architectures, neither extreme of this control architecture spectrum has proven to be the most appropriate choice for a given manufacturing system. Recent research into providing an objective comparison of alternative control architectures has shown that some degree of hierarchy is important for distributed manufacturing control architectures. This paper is concerned with our current investigations into why these partial hierarchies appear to display superior performance.
---
paper_title: Agent-Based Systems for Intelligent Manufacturing: A State-of-the-Art Survey

paper_content:

Agent technology has been considered as an important approach for developing distributed intelligent manufacturing systems. A number of researchers have attempted to apply agent technology to manufacturing enterprise integration, supply chain management, manufacturing planning, scheduling and control, materials handling, and holonic manufacturing systems. This paper gives a brief survey of some related projects in this area, and discusses some key issues in developing agent-based manufacturing systems such as agent technology for enterprise integration and supply chain management, agent encapsulation, system architectures, dynamic system reconfiguration, learning, design and manufacturability assessments, distributed dynamic scheduling, integration of planning and scheduling, concurrent scheduling and execution, factory control structures, potential tools and standards for developing agent-based manufacturing systems. An extensive annotated bibliography is provided.
---
paper_title: Hierarchy in distributed shop floor control

paper_content:

Abstract This discussion paper examines the role of hierarchy within the domain of shop floor control in manufacturing plants. Specifically, three distinct structures for shop floor control are considered, namely, hierarchical, heterarchical and holonic control systems. Holonic manufacturing is a novel paradigm for manufacturing that tries to merge the best properties of both hierarchical and heterarchical systems, namely, a high and predictable performance with a high robustness against disturbances. The paper identifies the concept of hierarchy in distributed shop floor control as one of the key contributions of holonic manufacturing. In a holonic architecture, the mapping of functions to control units remains flexible, such that decision power can be distributed over these units as needed. Based on the invariants concept of computer science, a modelling framework is proposed to identify the decision making needs of each unit. It can be used not only to describe the behaviour of the system, but also to impose performance and operational guarantees.
---
paper_title: The hybrid heuristic genetic algorithm for job shop scheduling

paper_content:

Abstract Scheduling for the job shop is very important in both fields of production management and combinatorial optimization. However, it is quite difficult to achieve an optimal solution to this problem with traditional optimization methods owing to the high computational complexity (NP-hard). Genetic algorithms (GA) have been proved to be effective for a variety of situations, including scheduling and sequencing. Unfortunately, its efficiency is not satisfactory. In order to make GA more efficient and practical, the knowledge relevant to the problem to be solved is helpful. In this paper, a kind of hybrid heuristic GA is proposed for problem n/m/G/Cmax, where the scheduling rules, such as shortest processing time (SPT) and MWKR, are integrated into the process of genetic evolution. In addition, the neighborhood search technique (NST) is adopted as an auxiliary procedure to improve the solution performance. The new algorithm is proved to be effective and efficient by comparing it with some popular methods, i.e. the heuristic of neighborhood search, simulated annealing (SA), and traditional GA.
---
paper_title: Agents in Overalls: Experiences and Issues in the Development and Deployment of Industrial Agent-Based Systems

paper_content:

Agent technologies have steadily matured in moving from the research laboratory to industrial application over the last ten years. Numerous systems have been deployed or are under advanced development with strong industrial support. These systems suggest important lessons for both industry and researchers. From an industrial perspective, these examples reflect trends in both business and technology that make agents an increasingly attractive commercial tool. From a research perspective, these examples identify important gaps in agent technology that merit the attention of academicians.
---

Title: SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS

Section 1: INTRODUCTION
Description 1: This section introduces the concept of scheduling, its importance, challenges, and the primary focus of the paper on dynamic scheduling in manufacturing systems.

Section 2: REAL-TIME EVENTS
Description 2: This section categorizes and describes various real-time events that impact manufacturing systems, such as machine breakdowns and job-related disruptions.

Section 3: DYNAMIC SCHEDULING APPROACHES
Description 3: This section defines and explains the four categories of dynamic scheduling approaches: completely reactive scheduling, predictive-reactive scheduling, robust predictive-reactive scheduling, and robust pro-active scheduling.

Section 4: RESCHEDULING IN THE PRESENCE OF REAL-TIME EVENTS
Description 4: This section discusses the policies and strategies for rescheduling in response to real-time events, including when to reschedule and the strategies for doing so.

Section 5: DYNAMIC SCHEDULING TECHNIQUES
Description 5: This section reviews various techniques used for dynamic scheduling, such as dispatching rules, heuristics, meta-heuristics, artificial intelligence techniques, and multi-agent systems.

Section 6: COMPARISON OF SOLUTION TECHNIQUES
Description 6: This section provides a comparative analysis of different solution techniques for dynamic scheduling, highlighting their strengths, weaknesses, and applicability.

Section 7: CONCLUSION
Description 7: This section summarizes the findings and discussions from the paper, emphasizing the importance of dynamic scheduling and the need for further research in generating robust schedules.