SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> COMPARISON OF SOLUTION TECHNIQUES <s> Evolutionary algorithms, simulated annealing (SA), and Tabu Search (TS) are general iterative algorithms for combinatorial optimization. The term evolutionary algorithm is used to refer to any probabilistic algorithm whose design is inspired by evolutionary mechanisms found in biological species. Most widely known algorithms of this category are Genetic Algorithms (GA). GA, SA, and TS have been found to be very effective and robust in solving numerous problems from a wide range of application domains.Furthermore, they are even suitable for ill-posed problems where some of the parameters are not known before hand. These properties are lacking in all traditional optimization techniques. In this paper we perform a comparative study among GA, SA, and TS. These algorithms have many similarities, but they also possess distinctive features, mainly in their strategies for searching the solution state space. the three heuristics are applied on the same optimization problem and compared with respect to (1) quality of the best solution identified by each heuristic, (2) progress of the search from initial solution(s) until stopping criteria are met, (3) the progress of the cost of the best solution as a function of time, and (4) the number of solutions found at successive intervals of the cost function. The benchmark problem was is the floorplanning of very large scale integrated circuits. This is a hard multi-criteria optimization problem. Fuzzy logic is used to combine all objective criteria into a single fuzzy evaluation function, which is then used to rate competing solutions.© (1998) COPYRIGHT SPIE--The International Society for Optical Engineering. Downloading of the abstract is permitted for personal use only. <s> BIB001 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> COMPARISON OF SOLUTION TECHNIQUES <s> Agent technologies have steadily matured in moving from the research laboratory to industrial application over the last ten years. Numerous systems have been deployed or are under advanced development with strong industrial support. These systems suggest important lessons for both industry and researchers. From an industrial perspective, these examples reflect trends in both business and technology that make agents an increasingly attractive commercial tool. From a research perspective, these examples identify important gaps in agent technology that merit the attention of academicians. <s> BIB002 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> COMPARISON OF SOLUTION TECHNIQUES <s> Abstract This discussion paper examines the role of hierarchy within the domain of shop floor control in manufacturing plants. Specifically, three distinct structures for shop floor control are considered, namely, hierarchical, heterarchical and holonic control systems. Holonic manufacturing is a novel paradigm for manufacturing that tries to merge the best properties of both hierarchical and heterarchical systems, namely, a high and predictable performance with a high robustness against disturbances. The paper identifies the concept of hierarchy in distributed shop floor control as one of the key contributions of holonic manufacturing. In a holonic architecture, the mapping of functions to control units remains flexible, such that decision power can be distributed over these units as needed. Based on the invariants concept of computer science, a modelling framework is proposed to identify the decision making needs of each unit. It can be used not only to describe the behaviour of the system, but also to impose performance and operational guarantees. <s> BIB003 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> COMPARISON OF SOLUTION TECHNIQUES <s> Abstract Scheduling for the job shop is very important in both fields of production management and combinatorial optimization. However, it is quite difficult to achieve an optimal solution to this problem with traditional optimization methods owing to the high computational complexity (NP-hard). Genetic algorithms (GA) have been proved to be effective for a variety of situations, including scheduling and sequencing. Unfortunately, its efficiency is not satisfactory. In order to make GA more efficient and practical, the knowledge relevant to the problem to be solved is helpful. In this paper, a kind of hybrid heuristic GA is proposed for problem n/m/G/Cmax, where the scheduling rules, such as shortest processing time (SPT) and MWKR, are integrated into the process of genetic evolution. In addition, the neighborhood search technique (NST) is adopted as an auxiliary procedure to improve the solution performance. The new algorithm is proved to be effective and efficient by comparing it with some popular methods, i.e. the heuristic of neighborhood search, simulated annealing (SA), and traditional GA. <s> BIB004 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> COMPARISON OF SOLUTION TECHNIQUES <s> Abstract The requirement for adaptable and re-configurable control systems for manufacturing has highlighted the inadequacies of traditional centralised control approaches, leading researchers to focus on decentralised approaches. The question of what is the most appropriate control architecture for a given system has led industrial and academic researchers to develop a spectrum of decentralised control architectures ranging from hierarchical to non-hierarchical structures. While current research has confirmed the potential of decentralised architectures, neither extreme of this control architecture spectrum has proven to be the most appropriate choice for a given manufacturing system. Recent research into providing an objective comparison of alternative control architectures has shown that some degree of hierarchy is important for distributed manufacturing control architectures. This paper is concerned with our current investigations into why these partial hierarchies appear to display superior performance. <s> BIB005 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> COMPARISON OF SOLUTION TECHNIQUES <s> Distributed manufacturing systems are more flexible in their arrangement and use of their resources. This permits a more dynamic and opportunistic allocation of manufacturing resources to work elements than is possible with today's centralized allocation systems. However, unlike solving the problem from a single solver view, there is no absolute control or tight coordination over how and when to decompose the problem, when to undertake a solution or the procedure for verifying consistency. Such activities will largely be left to the distributed entities to decide either individually or jointly. As a consequence the resulting allocations may suffer and induce myopic behaviour lacking in stability and regularity in the performance of the total system. Thus, the issues connected with solving the problem often move beyond the pure algorithmic focus of computation to include how the problem is decomposed, how or to whom it is assigned, and the organization for solving the subproblems, strategies used for resol... <s> BIB006 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> COMPARISON OF SOLUTION TECHNIQUES <s> Agent technology has been considered as an important approach for developing distributed intelligent manufacturing systems. A number of researchers have attempted to apply agent technology to manufacturing enterprise integration, supply chain management, manufacturing planning, scheduling and control, materials handling, and holonic manufacturing systems. This paper gives a brief survey of some related projects in this area, and discusses some key issues in developing agent-based manufacturing systems such as agent technology for enterprise integration and supply chain management, agent encapsulation, system architectures, dynamic system reconfiguration, learning, design and manufacturability assessments, distributed dynamic scheduling, integration of planning and scheduling, concurrent scheduling and execution, factory control structures, potential tools and standards for developing agent-based manufacturing systems. An extensive annotated bibliography is provided. <s> BIB007
Dispatching rules are easy and can find reasonable solutions rapidly. However, their main drawback is that the solution quality is usually poor due to their myopic nature. Heuristics have been widely used to react to the presence of real-time events because of their simplicity, but they may become stuck in poor local optima. To overcome this, meta-heuristics such as tabu search, simulated annealing, and genetic algorithms have been proposed. Several comparative studies have been provided in literature to compare the performance of tabu search, genetic algorithms, and simulated annealing. Unlike simulated annealing and tabu search based on manipulating one feasible solution, genetic algorithms maintain and manipulate a population of feasible solutions. Genetic algorithms were found inadequate because they are not efficient to find a near-optimal solution in a reasonable time compared to tabu search and simulated annealing which operate on a single configuration and not on an entire population   BIB001 BIB004 . Knowledge-based systems possess the potential for automating human expert reasoning and heuristic knowledge to run production scheduling systems. They model the shop floor by means of many hard and soft constraints. However, they usually lack the ability to optimise the system and require considerable effort to build and maintain. They are aimed at generating feasible schedules conforming to the domain knowledge. In terms of effectiveness of the decision-making capability, knowledge-based systems are limited by the quality and integrity of the specific domain knowledge. Fuzzy logic has not yet been explored to its fullest potential. Neural networks cannot guarantee to provide optimal decisions, but their learning capability makes them ideally suited for rapidly changing systems. Integrating neural networks, simulation and expert systems seems to have a lot of promise. Most scheduling systems developed in manufacturing environments are centralised and hierarchical. Centralised scheduling systems provide a consistent global view of the state of the enterprise and globally better schedules. However, practical experience has indicated that these systems tend to have problems with reactivity to disturbances. A large research field, currently subject of many in depth studies, regards the use of multi-agent systems in dynamic scheduling. The primary motivation in designing these systems is to decentralise the control of manufacturing systems, thereby reducing the complexity, increasing flexibility, 20 and enhancing fault tolerance. Refusing the traditional idea of a central scheduling system, which establishes a manufacturing plan for all the machines and jobs, multi-agent systems assume the presence of several agents with a good deal of decision making autonomy, distributed inside the manufacturing system. The agents interact and cooperate with each other in order to achieve effective global performances. Local autonomy allows the agents to take the responsibility for carrying out local scheduling for one or more functional or physical components in the production process (such as machines and jobs). Agents have the ability to observe their environment and to communicate and cooperate with other agents in order to ensure that local schedules lead to globally desirable schedules. Local autonomy allows the agents to respond locally to local variations, increasing the robustness and the flexibility of the system. Multi-agent technology appears to be a highly suitable approach for dynamic scheduling presenting capabilities such as decentralisation, integration, robustness, and flexibility. Several comparative studies have discussed the features of multi-agent systems that make them attractive candidates for implementing dynamic scheduling in contrast to centralised and hierarchical scheduling systems.  BIB002 demonstrated that multi-agent systems are well suited for applications that are modular, decentralised, likely to change frequently, ill-structured, and complex.  , Tahrumarajah and Bemelman (1997) , BIB005 presented in their comparative studies various advantages of multi-agent systems, such as heterogeneity, high modularity, high flexibility, high robustness against failures, reduced complexity, and reduced software development cost. According to Sandholm (2000) , the most important point that supports multi-agent systems is reactivity: agents can locally react to local changes faster than a centralised system could. Multi-agent systems provide the foundation for the creation of an architecture that possesses the capability to benefit manufacturing by enhancing a system's reliability, maintainability, flexibility, robustness, and stability, as well as providing means for real-time planning and scheduling. BIB007 discussed the advantages of using multi-agent systems in production scheduling which provide capabilities of integration, robustness and reactivity, flexibility, heterogeneity, and autonomy.(may be to delete) Two main multi-agent architectures for dynamic scheduling have been investigated: autonomous and mediator architectures. Autonomous architectures are a highly distributed form of control, where a network of independent agents cooperates directly towards a common goal. In mediator architectures, the agents cooperate via a mediator agent. The comparative studies of BIB005 , BIB007 , BIB003 , Shen et al. (2001), and BIB006 reported that autonomous architectures have prospects of reduced complexity, integrity, cost-efficiency, high flexibility, and a high robustness against disturbances. They are well suitable for applications with a small number of agents. However, they have problems in providing globally optimised performance, and the behaviour of the system can be unpredictable in complex environments with large number of agents. In contrast, mediator architectures show improved performance relative to autonomous architectures for developing distributed manufacturing systems, which are complex and composed of a large number of agents such as virtual enterprises. They combine robustness against disturbances with global performance optimisation and predictability. 21