SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Heuristics <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> BIB001 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Heuristics <s> 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. <s> BIB002 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Heuristics <s> 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... <s> BIB003 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Heuristics <s> 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... <s> BIB004 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Heuristics <s> 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... <s> BIB005 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Heuristics <s> 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... <s> BIB006 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Heuristics <s> 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. <s> BIB007 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Heuristics <s> 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. <s> BIB008 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Heuristics <s> 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 ... <s> BIB009
Heuristics in this context are problem specific schedule repair methods, which do not guarantee to find an optimal schedule, but have the ability to find reasonably good solutions in a short time. The most common schedule repair heuristics are: right-shift schedule repair, match-up schedule repair, and partial schedule repair. The Right-shift heuristic shifts the remaining operations schedule forwards in time by the amount of downtime in the event of machine failure. Match-up schedule repair strategy reschedules to match-up with the pre-schedule at some point in the future. Partial schedule repair reschedules only the operations in failure. BIB001 investigated the performance of the right-shift heuristic compared with dispatching rules and complete rescheduling using branch and bound. The experimental results showed that right shifting outperforms priority rules and complete rescheduling. BIB005 and BIB006 used the right-shift heuristic for inserting idle time to define predictable schedules. Abumaizar and Svestka (1997) compared the performance of partial schedule repair (affected operations schedule repair), complete rescheduling, and right shift schedule repair with respect to measures of efficiency (makespan) and stability (deviation from the initial schedule). The partial schedule repair heuristic reschedules only the operations directly and indirectly affected by the disruption so as to minimise both the increase in makespan and the deviation from the initial schedule. The results demonstrated that the affected operations heuristic reduces much of the deviation and computational complexity associated with complete rescheduling and right shifting. Right shifting gives the worst performance with respect to makespan due to the fact that this method is a simple shifting of the schedule by the amount of the disruption. Thus, the longer the disruption, the larger the expected shift, and the greater the increase in makespan. BIB002 proposed a match-up schedule repair heuristic for the shop floor rescheduling with multiple resources in the presence of machine breakdowns. The strategy reschedules to match up with the pre-schedule at some point in the future whenever machine breakdown occurs. Their experimental results showed that this method provides near-optimal solutions while achieving higher predictability than complete rescheduling. Later, BIB007 applied this approach for flow shop rescheduling. The results indicated that the match-up heuristic is very effective in terms of schedule quality, computation time, and schedule stability. A variety of more specific schedule repair heuristics have been also proposed in the literature. BIB003 proposed several rescheduling strategies for process time variations, machine breakdown, and new job arrival in a manufacturing cell. The rescheduling strategies are: rerouting the jobs to alternative machines, job-splitting (for batch production), and complete rescheduling. BIB009 proposed several schedule repair heuristics in the presence of machine failures. These schedule repair heuristics are based on rerouting the jobs to their alternative machines. BIB008 considered the problem of minimising makespan on a single batch-processing machine for oven scheduling in a semiconductor-manufacturing environment with dynamic job arrivals. They proposed and evaluated the performance of two schedule repair heuristics, delay schedule repair heuristic (delays the processing of a batch to integrate jobs arriving very soon in the future), and update schedule repair heuristic (updates the release time of the job to delay in the batch). The results indicated that the heuristics showed an excellent 10 average performance with a modest computational burden. BIB004 proposed various schedule repair heuristics for production rescheduling in flexible manufacturing systems for machine breakdown, arrival of rush jobs, increased job priority and job cancellation. When a machine breakdown occurs, the remaining operations are performed on alternative machines. For arrival of new jobs, if the new job is not a rush job, then priority is assigned based on EDD (Earliest Due Date) or FCFS (First Come First Served) dispatching rules, otherwise highest priority is assigned to it and all the disturbed tasks are moved forward in time. When a job priority is increased or a job is cancelled the remaining tasks are shifted forward in time on their respective machines.