SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> When to Reschedule <s> 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... <s> BIB001 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> When to Reschedule <s> 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) <s> BIB002 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> When to Reschedule <s> 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. <s> BIB003 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> When to Reschedule <s> 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. <s> BIB004 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> When to Reschedule <s> 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. <s> BIB005 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> When to Reschedule <s> 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. <s> BIB006 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> When to Reschedule <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> BIB007 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> When to Reschedule <s> 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. <s> BIB008 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> When to Reschedule <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> BIB009 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> When to Reschedule <s> 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. <s> BIB010
Regarding the first issue, when to reschedule, three policies have been proposed in the literature BIB007 BIB009 : periodic, event driven, and hybrid. The periodic and hybrid policies have received special attention under the name rolling time horizon BIB003 BIB004 BIB006 BIB008 BIB010 . In the periodic policy, schedules are generated at regular intervals, which gather all available information from the shop floor. The dynamic scheduling problem is decomposed into a series of static problems that can be solved by using classical scheduling algorithms. The schedule is then executed and not revised until the next period begins, where the planning horizon is renewed by taking into account new information gathered from the current shop floor status. The periodic policy yields more schedule stability and less schedule nervousness. Unfortunately, following an established schedule in the face of significant changes in the shop floor status may compromise performance since unwanted products or intermediates may be produced. Determining the rescheduling period is also a difficult task. The primary application of the rolling horizon approach to dynamic scheduling is due to BIB001 . They investigated how the frequency of scheduling in a dynamic job shop environment affected the performance where the processing time variations and machine breakdowns may occur randomly. At each rescheduling period, a static schedule for current jobs is generated by a dispatching rule. As anticipated, performance generally deteriorates when the rescheduling period increases. BIB004 used the rolling horizon policy for a single machine dynamic scheduling problem with sequence-dependent set-up 6 time to minimise maximum lateness. They found that rolling horizon scheduling outperforms myopic dispatching rules. BIB006 studied the rescheduling frequency in a multi-process flexible manufacturing system environment for machine breakdowns and processing time variations. The performance of the system is measured for mean tardiness and makespan criteria. Their results on the investigation on scheduling frequency indicated that a periodic response with an appropriate period length would be sufficient to cope with real-time events. It was observed that machine breakdowns have more significant impact on the system performance than processing time variations. BIB005 proposed a mechanism that periodically monitored the system and ran a dispatching rule found by means of simulation runs with multiple rules. If the difference between the actual performance, which deteriorates under machine failures, and the estimated performance exceeds a given limit, then a new simulation run is performed to select a new dispatching rule. The experiments show that the monitoring interval and performance limits should be carefully designed to achieve better performances. In Event driven policy rescheduling is triggered in response to an unexpected event that alters the current system status. Most of the approaches to dynamic scheduling use this policy. BIB002 studied the event driven rescheduling policy for job shop scheduling environment with random machine breakdowns. Rescheduling is triggered whenever a machine breakdown occurs. The results indicated that event driven rescheduling with lower computational burden and higher predictability outperforms the sequencing periodic policy and dispatching rules. BIB008 described analytical models to estimate the performance of a single machine system under periodic and event-driven rescheduling strategies in an environment where jobs arrive dynamically. They proposed to evaluate the performance of periodic rescheduling and event driven rescheduling using analytical models that can easily and quickly estimate important performance measures, such as average flow time and machine utilisation.  extended that study by investigating parallel machine systems. It was shown that rescheduling frequency can significantly affect the system performance (average flow time). A lower rescheduling frequency lowers the number of set ups. A higher rescheduling frequency allows the system to react more quickly to disruptions but may increase the number of set-ups. All these studies agreed that the event driven rescheduling is much better than periodic rescheduling. A hybrid policy reschedules the system periodically and also when an exception occurs. Events usually considered are machine breakdowns, arrival of urgent jobs, cancellation of jobs, or job priority changes. Church and Ozsoy (1992) developed a hybrid event-driven rescheduling policy for rescheduling in a singlemachine and parallel machine environment with dynamic job arrivals. Their system does rescheduling periodically. Events classified as regular occurring between periodic rescheduling are ignored until the next rescheduling moment. However, when an event is classified as urgent, complete rescheduling is immediately performed. The results indicated that the performance of periodic scheduling deteriorates as the length of rescheduling period increases, while event driven method achieves a reasonably good performance. 