Hedging production schedules against uncertainty in manufacturing environment with a review of robustness and stability research
---
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: 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: Reactive scheduling in a dynamic and stochastic FMS environment

paper_content:

In this paper, we study the reactive scheduling problems in a dynamic and stochastic manufacturing environment. Specifically, we develop a simulation-based scheduling system for flexible manufactur...
---
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: Experimental investigation of iterative simulation-based scheduling in a dynamic and stochastic job shop

paper_content:

Abstract A vital component of modern manufacturing systems is the scheduling and control system, which determines companies' overall performance in their respective supply chains. This paper studies iterative simulation-based scheduling mechanisms for manufacturing systems that operate in dynamic and stochastic environments. Also assessed are the issues involved when these mechanisms are used to make higher-level scheduling decisions, such as dispatching rule selection, instead of generation of a full schedule. A typical simulation-based system is outlined and tested under various experimental conditions. Examined are the effects of stochastic events such as machine breakdowns and processing time variations on the system performance, and the effectiveness of the simulation-based approach from the control point of view is evaluated. Finally, different levels of two important factors (look-ahead window and scheduling period) are compared for the iterative approach. Computational results show that, although simulation-based scheduling proves effective when these parameters are properly set, the overall performance diminishes due to the dynamic and stochastic nature of the system, which degrades the multi-pass improvement capability of the simulation runs. Experimental results also support the initial expectation in that frequent updates to the higher-level schedule may not be necessary when these decisions are naturally “adaptive” to the unexpected system changes.
---
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: Reactive scheduling in a dynamic and stochastic FMS environment

paper_content:

In this paper, we study the reactive scheduling problems in a dynamic and stochastic manufacturing environment. Specifically, we develop a simulation-based scheduling system for flexible manufactur...
---
paper_title: Real-time scheduling of an automated manufacturing center

paper_content:

Abstract This paper investigates the dynamic scheduling of an automated manufacturing workcenter at which jobs are processed in batches, and there is a constant changeover time between batches of different part types. The primary measures of schedule performance are mean flow time and mean tardiness. The dynamic scheduling problem is treated as a series of static problems which are solved on a rolling-horizon basis. Characteristics of the optimal solutions to the mean flow time and mean tardiness problems are developed, and an implicit enumeration approach to the mean tardiness problem is proposed. These results are used for constructing efficient scheduling procedures for the dynamic problem. We also derive the steady state relationship between workcenter utilization level, batch size and mean flow time for one and two part types. A simulation study extends this relationship to a larger number of part types.
---
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: 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: 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: 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: Stability of an optimal schedule in a job shop

paper_content:

This paper is devoted to the calculation of the stability radius of an optimal schedule for a job shop problem, when the objective is to minimize mean or maximum flow times. The approach used may be regarded as an a posteriori analysis, in which an optimal schedule has already been constructed and the question is to determine such changes in the processing times of operations as do not destroy the optimality of the schedule at hand. More precisely, the stability radius denotes the largest quantity of independent variations of the processing times of the operations such that an optimal schedule of the problem remains optimal. Although in scheduling theory mainly deterministic problems are considered and the processing times are supposed to be given in advance, such scheduling problems do not often arise in practice. Even if the processing times are know before applying a scheduling procedure, OR workers are forced to take into account possible changes and errors within the practical realization of a schedule, e.g. additionally arriving jobs, machine breakdowns, the precision of equipment which is used to calculate the processing times, and so on. In other words, usually in practice a schedule has to be realized under conditions of uncertainty. This paper investigates the influence of errors and possible changes of the processing times on the optimality of a schedule. To this end, extensive numerical experiments with randomly generated job shop scheduling problems are performed and discussed. The developed software provides the possibility of comparing the values of the stability radii, the numbers of optimal schedules and some other "numbers" for two often used criteria. The main question we try to answer is how large the stability radius is, on average, for randomly generated job shop problems.
---
paper_title: Project scheduling under uncertainty: Survey and research potentials

paper_content:

The vast majority of the research efforts in project scheduling assume complete information about the scheduling problem to be solved and a static deterministic environment within which the pre-computed baseline schedule will be executed. However, in the real world, project activities are subject to considerable uncertainty, which is gradually resolved during project execution. In this survey we review the fundamental approaches for scheduling under uncertainty: reactive scheduling, stochastic project scheduling, fuzzy project scheduling, robust (proactive) scheduling and sensitivity analysis. We discuss the potentials of these approaches for scheduling under uncertainty projects with deterministic network evolution structure.
---
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: 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: 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: 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: Maximization of solution flexibility for robust shop scheduling

paper_content:

We consider the problem of introducing flexibility in the schedule determination phase, for shop scheduling problems with release dates and deadlines. The flexibility is provided by generating a family of schedules, instead of a unique one. We represent a family of schedules by an ordered group assignment defining for each machine a sequence of groups where the operations within a group are totally permutable. We propose a polynomial time algorithm to evaluate the worst case completion time of operations in an ordered group assignment. We then consider the single machine problem with heads and deadlines associated to operations, as a sub-problem of the job shop problem. We propose polynomial time dynamic programming algorithms for minimizing the number of groups and for maximizing the number of characterized sequences, under specific constraints. Finally, computational experiences on job shop benchmarks, show the impact of grouping operations on the solution makespan value.
---
paper_title: A Graph-Theoretic Decomposition of the Job Shop Scheduling Problem to Achieve Scheduling Robustness

paper_content:

In this paper we study the weighted tardiness job-shop scheduling problem, taking into consideration the presence of random shop disturbances. A basic thesis of the paper is that global scheduling performance is determined primarily by a subset of the scheduling decisions to be made. By making these decisions in an a priori static fashion, which maintains a global perspective, overall performance efficiency can be achieved. Further, by allowing the remaining decisions to be made dynamically, flexibility can be retained in the schedule to compensate for unforeseen system disturbances. We develop a decomposition method that partitions job operations into an ordered sequence of subsets. This decomposition identifies and resolves a "crucial subset" of scheduling decisions through the use of a branch-and-bound algorithm. We conduct computational experiments that demonstrate the performance of the approach under deterministic cases, and the robustness of the approach under a wide range of processing time perturbations. We show that the performance of the method is superior, particularly for low to medium levels of disturbances.
---
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: 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: Experimental investigation of iterative simulation-based scheduling in a dynamic and stochastic job shop

paper_content:

Abstract A vital component of modern manufacturing systems is the scheduling and control system, which determines companies' overall performance in their respective supply chains. This paper studies iterative simulation-based scheduling mechanisms for manufacturing systems that operate in dynamic and stochastic environments. Also assessed are the issues involved when these mechanisms are used to make higher-level scheduling decisions, such as dispatching rule selection, instead of generation of a full schedule. A typical simulation-based system is outlined and tested under various experimental conditions. Examined are the effects of stochastic events such as machine breakdowns and processing time variations on the system performance, and the effectiveness of the simulation-based approach from the control point of view is evaluated. Finally, different levels of two important factors (look-ahead window and scheduling period) are compared for the iterative approach. Computational results show that, although simulation-based scheduling proves effective when these parameters are properly set, the overall performance diminishes due to the dynamic and stochastic nature of the system, which degrades the multi-pass improvement capability of the simulation runs. Experimental results also support the initial expectation in that frequent updates to the higher-level schedule may not be necessary when these decisions are naturally “adaptive” to the unexpected system changes.
---
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: Predictable scheduling of a job shop subject to breakdowns

paper_content:

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 which can absorb disruptions without affecting planned external activities, while maintaining high shop performance. We present a predictable scheduling approach where the predictive schedule is built with such objectives. The procedure inserts additional idle time into the schedule to absorb the impacts of breakdowns. The amount and location of the additional idle time is determined from the breakdown and repair distributions as well as the structure of the predictive schedule. 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 maximum lateness in a job shop environment with random machine breakdowns, and show that it provides high predictability with minor sacrifices in shop performance.
---
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: 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: 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: Maximization of solution flexibility for robust shop scheduling

paper_content:

We consider the problem of introducing flexibility in the schedule determination phase, for shop scheduling problems with release dates and deadlines. The flexibility is provided by generating a family of schedules, instead of a unique one. We represent a family of schedules by an ordered group assignment defining for each machine a sequence of groups where the operations within a group are totally permutable. We propose a polynomial time algorithm to evaluate the worst case completion time of operations in an ordered group assignment. We then consider the single machine problem with heads and deadlines associated to operations, as a sub-problem of the job shop problem. We propose polynomial time dynamic programming algorithms for minimizing the number of groups and for maximizing the number of characterized sequences, under specific constraints. Finally, computational experiences on job shop benchmarks, show the impact of grouping operations on the solution makespan value.
---
paper_title: A Graph-Theoretic Decomposition of the Job Shop Scheduling Problem to Achieve Scheduling Robustness

paper_content:

In this paper we study the weighted tardiness job-shop scheduling problem, taking into consideration the presence of random shop disturbances. A basic thesis of the paper is that global scheduling performance is determined primarily by a subset of the scheduling decisions to be made. By making these decisions in an a priori static fashion, which maintains a global perspective, overall performance efficiency can be achieved. Further, by allowing the remaining decisions to be made dynamically, flexibility can be retained in the schedule to compensate for unforeseen system disturbances. We develop a decomposition method that partitions job operations into an ordered sequence of subsets. This decomposition identifies and resolves a "crucial subset" of scheduling decisions through the use of a branch-and-bound algorithm. We conduct computational experiments that demonstrate the performance of the approach under deterministic cases, and the robustness of the approach under a wide range of processing time perturbations. We show that the performance of the method is superior, particularly for low to medium levels of disturbances.
---
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: 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: 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: The one-machine sequencing problem

paper_content:

Let M 1 and M 3 be non-bottleneck machines and M 2 a bottleneck machine processing only one job at a time. Suppose that n jobs have to be processed on M 1 , M 2 and M 1 (in that order) and job i has to spend a time a , on M 1 , d 1 on M 2 and q 1 on M 3 : we want to minimize the makespan. This problem is important since its resolution provides a bound on the makespan of complicated systems such as job shops. It is NP-hard in the strong sense. However, efficient branch and bound methods exist and we describe one of them. Our bound for the tree-search is very close to the bound used by Florian et al., but the principle of branching is quite different. At every node, we construct by an O( n log n ) algorithm a Schrage schedule; then we define a critical job c , a critical set J and consider two subsets of schedules; the schedules when c procedes every job of J and the schedules when c follows every job of J . We give the results of this method and prove that the difference between the optimum and the Schrage schedule is less than d 1 .
---
paper_title: Rescheduling and optimization of schedules considering machine failures

paper_content:

The objective of the research discussed in this paper has been to make the effect of a machine failure to a schedule less. A robust function is defined. A rescheduling approach by which the rescheduling policy is obtained corresponding to the different lengths of downtime of a machine is proposed. A trigger value of rescheduling is obtained. By the above research, the schedules minimizing the completion time of all jobs can be evaluated and an optimal schedule against machine failures can be selected.
---
paper_title: Proactive heuristic procedures for robust project scheduling: An experimental analysis

paper_content:

Solution-robust project scheduling is a growing research field aiming at constructing proactive schedules to cope with multiple disruptions during project execution. When stochastic activity durations are considered, including time buffers between activities is a proven method to improve the stability of a baseline schedule. This paper introduces multiple algorithms to include time buffers in a given schedule while a predefined project due date remains respected. Multiple efficient heuristic and meta-heuristic procedures are proposed to allocate buffers throughout the schedule. An extensive simulation-based analysis of the performance of all algorithms is given. The impact of the activity duration variance structure on the performance is discussed in detail.
---
paper_title: Predictable scheduling of a job shop subject to breakdowns

paper_content:

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 which can absorb disruptions without affecting planned external activities, while maintaining high shop performance. We present a predictable scheduling approach where the predictive schedule is built with such objectives. The procedure inserts additional idle time into the schedule to absorb the impacts of breakdowns. The amount and location of the additional idle time is determined from the breakdown and repair distributions as well as the structure of the predictive schedule. 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 maximum lateness in a job shop environment with random machine breakdowns, and show that it provides high predictability with minor sacrifices in shop performance.
---
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: Minimizing maximal regret in the single machine sequencing problem with maximum lateness criterion

paper_content:

In this paper, the single machine sequencing problem with maximum lateness criterion is discussed. The parameters of the problem are imprecise and they are specified as intervals. The maximal regret criterion is applied to calculate the optimal sequence. A polynomial algorithm for the studied problem is constructed.
---
paper_title: On the Robust Single Machine Scheduling Problem

paper_content:

The single machine scheduling problem with sum of completion times criterion (SS) can be solved easily by the Shortest Processing Time (SPT) rule. In the case of significant uncertainty of the processing times, a robustness approach is appropriate. In this paper, we show that the robust version of the (SS) problem is NP-complete even for very restricted cases. We present an algorithm for finding optimal solutions for the robust (SS) problem using dynamic programming. We also provide two polynomial time heuristics and demonstrate their effectiveness.
---
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: Reactive scheduling in a dynamic and stochastic FMS environment

paper_content:

In this paper, we study the reactive scheduling problems in a dynamic and stochastic manufacturing environment. Specifically, we develop a simulation-based scheduling system for flexible manufactur...
---

Title: Hedging production schedules against uncertainty in manufacturing environment with a review of robustness and stability research

Section 1: Introduction
Description 1: Discuss the significance of scheduling in manufacturing, the nature of disruptions in the production environment, and introduce the concepts of proactive and reactive scheduling. Outline the paper's purpose and organization.

Section 2: Two major issues of scheduling
Description 2: Explain the challenges of scheduling in dynamic and uncertain environments, particularly addressing the issues of 'when-to-schedule' and 'how-to-schedule'.

Section 3: Reacting to disruptions
Description 3: Detail the different types of responses to schedule disruptions, providing examples and proposing suitable responses based on the type and frequency of disruptions.

Section 4: Scheduling approaches: reactive versus proactive scheduling
Description 4: Compare and contrast reactive and proactive scheduling approaches, discussing their implementations, advantages, and limitations.

Section 5: Proactive scheduling
Description 5: Explore the methods and measures for generating proactive schedules that can withstand disruptions, including scenario planning and decision-theoretic criteria.

Section 6: Recent studies in scheduling robustness and stability
Description 6: Review recent literature on robustness and stability in scheduling, highlighting key findings and methodologies used in these studies.

Section 7: Concluding remarks and future research directions
Description 7: Summarize the importance of robustness and stability in scheduling, provide final thoughts, and suggest potential areas for future research.