SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Rescheduling Strategies <s> 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. <s> BIB001 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Rescheduling Strategies <s> 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. <s> BIB002 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Rescheduling Strategies <s> 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. <s> BIB003 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Rescheduling Strategies <s> 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. <s> BIB004 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Rescheduling Strategies <s> 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. <s> BIB005 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Rescheduling Strategies <s> 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. <s> BIB006 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Rescheduling Strategies <s> 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. <s> BIB007 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Rescheduling Strategies <s> 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. <s> BIB008 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Rescheduling Strategies <s> 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. <s> BIB009 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Rescheduling Strategies <s> 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. <s> BIB010 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Rescheduling Strategies <s> 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. <s> BIB011
Regarding the second issue, what strategies to use to reschedule, the literature provided two main rescheduling strategies BIB006 Cowling and Johanson, 2002; BIB010 : schedule repair and complete rescheduling. Schedule repair refers to some local adjustment of the current schedule and may be preferable because of the potential saving in CPU times and the stability of the system is preserved. Section 5.2 presents examples of schedule repair strategies. Complete rescheduling regenerates a new schedule from scratch. Complete rescheduling might, in principle, be better in maintaining optimal solutions, but these solutions are rarely achievable in practice and require prohibitive computation time. Moreover, complete rescheduling can result in instability and lack of continuity in detailed plant schedules, leading to additional production costs attributable to what has been termed shop floor nervousness. BIB007 , and BIB003 reported that most of the reactive scheduling systems attempt to revise only part of the originally created schedule for responding to the production environment changes without rescheduling from scratch. BIB005 stated that in practice rescheduling has been done by schedule repair. While complete rescheduling has been used also to a limited degree. BIB006 demonstrated the potential effectiveness of schedule repair in terms of stability and CPU time compared with complete rescheduling. Another problem of practical importance is the decision whether to reschedule from scratch (complete rescheduling) or schedule repair, and which schedule repair strategy to choose to react to real-time events. To deal with this problem, simulation and robustness measures were used to evaluate the performance of the rescheduling strategies and to select the best strategy. BIB001 BIB002 , BIB004 , BIB005 , BIB008 used robustness measures (efficiency and stability) to decide on the best rescheduling strategy to apply. BIB009 and BIB011 used utility and stability measures to assess the performance of various schedule repair and complete rescheduling strategies, and to select the best rescheduling strategy. Examples of applications of simulation are presented in Subsection 4.4.1.