SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Meta-heuristics: Tabu search, Simulated Annealing, and Genetic Algorithms <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> Meta-heuristics: Tabu search, Simulated Annealing, and Genetic Algorithms <s> Part 1 Introduction: combinatorial problems local and global optima heuristics. Part 2 Simulated annealing: the basic method enhancements and modifications applications conclusions. Part 3 Tabu search: the tabu framework broader aspects of intensification and diversification tabu search applications connections and conclusions. Part 4 Genetic algorithms: basic concepts a simple example extensions and modifications applications conclusions. Part 5 Artificial neural networks: neural networks combinatorial optimization problems the graph bisection problem the graph partition problem the travelling salesman problem scheduling problems deformable templates inequality constraints, the Knapsack problem summary. Part 6 Lagrangian relaxation: overview basic methodology Lagrangian heuristics and problem reduction determination of Lagrange multipliers dual ascent tree search applications conclusions. Part 7 Evaluation of heuristic performance: analytical methods empirical testing statistical inference conclusions. <s> BIB002 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Meta-heuristics: Tabu search, Simulated Annealing, and Genetic Algorithms <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> BIB003 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Meta-heuristics: Tabu search, Simulated Annealing, and Genetic Algorithms <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> BIB004 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Meta-heuristics: Tabu search, Simulated Annealing, and Genetic Algorithms <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> BIB005 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Meta-heuristics: Tabu search, Simulated Annealing, and Genetic Algorithms <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> BIB006 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Meta-heuristics: Tabu search, Simulated Annealing, and Genetic Algorithms <s> A general model for job shop scheduling is described which applies to static, dynamic and non-deterministic production environments. Next, a Genetic Algorithm is presented which solves the job shop scheduling problem. This algorithm is tested in a dynamic environment under different workload situations. Thereby, a highly efficient decoding procedure is proposed which strongly improves the quality of schedules. Finally, this technique is tested for scheduling and rescheduling in a non-deterministic environment. It is shown by experiment that conventional methods of production control are clearly outperformed atreasonable runtime costs. <s> BIB007 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Meta-heuristics: Tabu search, Simulated Annealing, and Genetic Algorithms <s> The paper presents a genetic algorithm capable of generating optimised production plans in flexible manufacturing systems. The ability of the system to generate alternative plans following part-flow changes and unforeseen situations is particularly stressed (dynamic scheduling). Two contrasting objectives represented by the reduction of machine idle-times, thanks to dynamic scheduling computation and the reduction of the makespan, are taken into account by the proposed system. The key-point is the real-time response obtained by an optimised evolutionary strategy capable of minimising the number of genetic operations needed to reach the optimal schedule in complex manufacturing systems. <s> BIB008 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Meta-heuristics: Tabu search, Simulated Annealing, and Genetic Algorithms <s> Most job shop scheduling methods reported in the literature usually address the static scheduling problem. These methods do not consider multiple criteria, nor do they accommodate alternate resources to process a job operation. In this paper, a scheduling method based on genetic algorithms is developed and it addresses all the shortcomings mentioned above. The genetic algorithms approach is a schedule permutation approach that systematically permutes an initial pool of randomly generated schedules to return the best schedule found to date. <s> BIB009 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Meta-heuristics: Tabu search, Simulated Annealing, and Genetic Algorithms <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> BIB010 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> Meta-heuristics: Tabu search, Simulated Annealing, and Genetic Algorithms <s> This work gives a concise introduction to four important optimization techniques, presenting a range of applications drawn from electrical, manufacturing, mechanical, and systems engineering-such as the design of microstrip antennas, digital FIR filters, and fuzzy logic controllers. The book also contains the C programs used to implement the main techniques for those wishing to experiment with them. <s> BIB011
In recent years, meta-heuristics (tabu search, simulated annealing and genetic algorithms) have been successfully used to solve production scheduling problems. Meta-heuristics are high level heuristics which guide local search heuristics to escape from local optima BIB002 Glover and Laguna, 1997; BIB011 . Local search heuristics are neighbourhood search methods based on the idea of searching neighbourhoods. In local neighbourhood search, the search starts from some given solution, and tries iteratively to move to a better solution in an appropriately defined neighbourhood of the current solution using move operators. The search process stops when no better solution can be found in the neighbourhood of the current solution, which is the local optimum. Meta-heuristics such as tabu search, simulated annealing and genetic algorithms improve the local search algorithms to escape local optima by either accepting worse solutions, or by generating good starting solutions for the local search in a more intelligent way than just providing random initial solutions. Tabu search, genetic algorithms, and simulated annealing have been widely used to solve static deterministic production scheduling problems in several domains including job shops, open shops, flowshops, flexible manufacturing systems, batch processing, etc. However, little research work has addressed the use of meta-heuristics in dynamic scheduling. BIB005 and discussed the importance of using meta-heuristics to schedule repair instead of using local search or simple heuristics as they can be trapped in a poor local optimum. BIB006 used tabu search to search for predictable schedules. BIB005 used tabu search to repair a schedule caused by uncertain time processes in steel continuous caster scheduling. used simulated annealing to repair schedules for space shuttle ground operations. To repair a schedule, the system chooses between five repair heuristics using a choice-function, and applies simulated annealing search to perform multiple repair iterations. It was found that tabu search and simulated annealing generate good quality schedules in a short time of period. BIB009 used genetic algorithms for dynamic scheduling of manufacturing job shops in the presence of machine breakdown and alternate job routine. Two performance measures, namely mean job tardiness and mean job cost, were used. Whenever a dynamic event occurs, genetic algorithms are used to propose an alternative schedule. In addition, the solution of genetic algorithms was compared to several common dispatching rules. The results indicated that the performance of genetic 11 algorithms is significantly superior to that of the common dispatching rules. BIB008 used genetic algorithms for dynamic batch scheduling of flexible manufacturing systems. They considered the following real-time events: arrival of a new batch, unavailability of parts to be machined (due to the failure of feeding systems, the presence of defects on work pieces, etc.), and machine breakdowns (due to unavailability of tools, unplanned maintenance, etc.). Schedules produced using dispatching rules were improved using genetic algorithms. The results showed that genetic algorithms greatly reduce the makespan. BIB004 and BIB010 used genetic algorithms to generate robust schedules and to evaluate the performance of various robustness measures. BIB001 BIB003 compared the performance of genetic algorithms and local search heuristics to generate robust schedules. The results showed the performance of genetic algorithms in generating schedules with much better makespan and stability than local search heuristics. However, BIB007 reported in their experimental results that the capabilities of genetic algorithms vanish with an increasing problem size, and they are not efficient to find a near-optimal solution in a reasonable time.