SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Robust Predictive-reactive Scheduling <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> Robust Predictive-reactive Scheduling <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> Robust Predictive-reactive Scheduling <s> 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... <s> BIB003 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Robust Predictive-reactive Scheduling <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> Robust Predictive-reactive Scheduling <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> Robust Predictive-reactive Scheduling <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> BIB006 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Robust Predictive-reactive Scheduling <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> BIB007 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Robust Predictive-reactive Scheduling <s> 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. <s> BIB008
Most of the predictive-reactive scheduling strategies are based on simple schedule adjustments which consider only shop efficiency. The new schedule may deviate significantly from the original schedule, which can seriously affect other planning activities that are based on the original schedule and may lead to poor performance of the schedule. It is therefore desirable to generate predictive-reactive schedules that are robust. Robust predictive-reactive scheduling focuses on building predictive-reactive schedules to minimise the effects of disruption on the performance measure value of the realised schedule BIB001 BIB002  4 BIB003 . Even though the need to create a robust schedule was recognised over two decades ago by Graves 1981 BIB004 , there is little research in the literature to find out how a robust schedule can be generated in a dynamic environment. A typical solution to this problem is to reschedule considering both shop efficiency and deviation from the original schedule (stability) simultaneously. Stability measures the deviation from the original predictive schedule caused by schedule revision to quantify the undesirability of making changes to the initial schedule BIB001 BIB002 BIB007 BIB008 . BIB001 BIB002 ) defined a bi-criterion robustness measure for one-machine rescheduling problem with machine breakdown. The criteria include the minimisation of the makespan (schedule efficiency) and the impact of schedule change (schedule stability). For the stability, they investigated two measures: the deviation from the original job starting times, and the deviation from the original sequence. Their experimental results showed the effectiveness of the robustness measure in that the schedule stability can be increased significantly with little or no reduction in makespan. In the same order of idea, BIB005 used two measures to define a robust schedule: efficiency (makespan) and stability measures (starting time deviation and sequence deviations). The scheduling objective is to maximise shop efficiency, and at the same time minimise system impact caused by schedule changes. BIB006 investigated different robustness measures to improve tardiness and total flow-time for machine breakdowns. BIB003 developed robustness measures and robust scheduling to deal with machine breakdowns and processing time variability in the case where a right-shift repair strategy is used. The robustness is defined as the minimisation of the bi-criterion objective function expressed in terms of both expected makespan and expected delay. The expected delay is the deviation between the deterministic makespan before disruption, and the actual makespan after applying right shifting. The experimental results showed that robust schedules significantly outperform schedules based on makespan alone. BIB004 defined robustness measures for a single machine environment to cope against processing time uncertainty where the scheduling objective is to minimise the flow time of jobs. The robustness is defined as the minimisation of both the flow time and the absolute deviation from the original schedule caused by schedule revision. Extensive computational results reported the efficiency and effectiveness of the proposed robustness measures. Recently Cowling and Johanson (2002) and defined general measures of utility and stability to guide the decision as what strategy should be used to react to real-time events in order to define a robust schedule. Utility measures the change in the value of the schedule objective function following the schedule revision. It is expressed by the difference between the value of the objective function of the new schedule after reacting into the real-time events and the objective function of the predictive schedule before taking into account real-time events. They have then investigated a number of utility and stability measures for single machine scheduling model with the objective of minimising the average completion time.