SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> 15 <s> Designs for real-world agent-based systems must reflect domain requirements as well as the technical capabilities of agents. This needs-driven approach is being applied in AARIA (Autonomous Agents for Rock Island Arsenal), an industrial-strength agent-based factory scheduling and simulation system being developed for an Army manufacturing facility. A review of the operations of Rock Island in the light of broader industrial needs yields seven requirements. After introducing the AARIA agent community, we summarize each of these requirements and how AARIA supports it. More information is available at http://www.aaria.uc.edu . The AARIA Agent Community In discrete manufacturing, Parts move through a network of Unit Processes (UP’s) and Buffers. Each UP acquires one or more input Parts from Buffers of the needed types, and engages certain Resources to produce one or more output Parts into appropriate Buffers. In AARIA, we use linguistic case theory [Parunak 95] over a set of declarative sentences describing the domain to identify candidate agents, then refine this population using the requirements. Figure 1 shows the resulting community, with its flows of Parts and Engagements for Resources along orthogonal axes that intersect at UP’s. Previous research on agentbased factory control and scheduling (including our own) differs widely on what is represented as an agent: levels in a hierarchical decomposition of the factory (Butler & Ohtsubo 92, Tilley & Williams 92, Parunak 87), Resources (Shaw & Whinston 85, Baker 96, Parunak et al. 87, Heaton 94), or Parts (Maley 88, Duffie et al. 88). In AARIA, Separate full-fledged agents represent parts, resources and unit processes with substantially equal intelligence and responsibility in each type of agent. The AARIA system has a number of other important enhancements from past work in multi-agent manufacturing. The system incorporates new features for schedule optimization and fault recovery. Unlike many past systems, these agents are being implemented in an agent infrastructure that allows true agent behavior by supporting true broadcast and multicast communications, subject based mail handling, multithreaded agent activity, multi-platform instantiation, agent migration, and the implementation of multiple scheduled activities within an agent. Also, the system is being implemented with dual functionality so it can run a real factory or run in simulation mode. The sections below outline AARIA's seven design requirements and highlight other enhancements to past work. Meeting the AARIA Requirements Uniformity (An operation at the boundary of AARIA interacts with external suppliers or customers in the same way that it does with internal ones.)—Both an external customer and an internal UP draw from Buffers, and both an external supplier and a UP feed Buffers. Thus UP’s represent both customers and suppliers. This result offers a novel approach to supply-chain integration. Traditionally, each firm in a supply chain is viewed as a monolithic entity with its own internal mechanisms, requiring a special set of mechanisms to interact with other firms. AARIA views each firm as an internal supply chain. As a result, the interfaces between AARIA agents within a firm are the same as those between one firm and another, and integrating multiple AARIA-based firms into a supply chain becomes immediate and transparent. Metamorphosis (The system maintains continuity between different entities that represent different stages in a common life cycle, for example, an order for a part, the part itself, and its production history.)—AARIA distinguishes persistent agents, whose behavior does not change over the time scale involved in daily shop operation, from transient agents, which represent interactions among persistent agents and which go through a In pu t P ar ts Unit Process Buffer Buffer Buffer Buffer Buffer Buffer <s> BIB001 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> 15 <s> This paper describes an ongoing research project in distributed, agent-based manufacturing scheduling systems which exhibit collective system behavior. A scheduling system is described which exhibits purely low-level, reactive behavior. Two types of agents comprise the collective: part agents and machine agents. The collective is a mixedinitiative system in which agents representing parts attempt to maximize part flow to the next machine and agents representing machines attempt to maximize their utilization. Agents of the collective contain only local knowledge: a machine agent schedules operations on its machine and a part agent commits available parts to machine operations. This architecture provides an opportunity to use reinforcement learning techniques to allow an agent of the collective to improve performance by learning patterns of local interactions over time. Furthermore, both agent types of the collective exhibit anytime behavior by continuously computing the next decision until it is required to commit a decision to a fellow agent. Such agent information will bc of value in further research, the goal of which is to allow the dynamic collective adapts its architecture at runtime in response to unresolvable scheduling conflicts by creating temporary, higher-level agents opportunistically to handle particular situations. The architecture of the Autonomous Manufacturing Collective (AMC) is described herein. <s> BIB002 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> 15 <s> Describes an intelligent real time cell control architecture for flexible manufacturing systems. This architecture is based on the multi-agent concept of the distributed artificial intelligence. We propose an actor architecture. This multi-agent prototype system involves the following functions: scheduling, dispatching, monitoring and error handling. A new contract protocol for dynamic scheduling is presented. The purpose of this protocol is to dynamically assign operations to the resources of the manufacturing system in order to accomplish the proposed tasks. This protocol is able to deal with exceptions. <s> BIB003 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> 15 <s> Deals with a multi-agent architecture and a negotiation protocol for the dynamic scheduling of flexible manufacturing systems. The originality of the multi-agent architecture resides in the existence of task agents and resource agents. The multi-contract net protocol proposed, is an innovation with regard to the contract-net protocol due to the way that it makes it possible to negotiate several tasks concurrently, in real time and with more optimal results taking into account uncertainty and conflict situations in the scheduling of operations. The paper, also, stresses the efficiency and the optimality of the distributed implementation. <s> BIB004 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> 15 <s> Abstract This paper deals with a new architecture and negotiation protocol for the dynamic scheduling of Manufacturing Systems. The architecture is based on two paradigms: Multi-Agent Systems and Holonic Systems. The main contribution in the architecture is the development of Holons representing tasks and resources. The well-known Contract Net Protocol [R. Davis, R. Smith, Negotiation as a metaphor for distributed problem solving, Artificial Intelligence, 20, (1), (1983) 63–109] has been adapted to handle temporal constraints and to deal with scheduling conflicts. The purpose of this protocol is to dynamically assign operations to the resources of the Manufacturing System to accomplish the proposed tasks. This protocol involves a renegotiation phase whenever exceptions appear. It also deals with conflict situations, namely, with the case of the `indecision problem'. The used approach assumes that deadlines are the most important constraints to consider. Thus the acceptance or refusal of a resource for a specific operation depends on the capability of executing the operation within the specified deadline. <s> BIB005 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> 15 <s> Abstract Multi-Agent Intelligent Systems (MAIS) are loosely-coupled network of problem solving systems that, whenever needed, work together with each other to dynamically solve problems that none of the system can individually solve. Among the advantages of the MAIS, when compared to the centralized systems, are increased reliability, faster problem solving, decreased communication, and more flexibility. Learning to coordinate the actions is one of the most important task in MAIS. In the current research, we use a widely reported dynamic job shop scheduling simulation model that uses distributed genetic learning of job scheduling strategies (Pendharkar, P.C., 1997. Doctoral Dissertation, Graduate School, Southern Illinois University at Carbondale; Pendharkar, P.C., 1998. Distributed learning of objectives for adaptive scheduling (in review); Pendharkar, P.C., Bhattacharyya, S., 1997. Multi-agent learning in distributed artificial intelligence. Proc. 2nd INFORMS Conference on Information Systems and Technology. San Diego, CA, p.156–163; Bhattacharyya, S., Koehler, G.J., 1997. Learning by objectives for adaptive shop-floor learning. Decision Sciences (to appear). Aytug, H., Koehler, G.J., Snowdon, J.L., 1994. Genetic learning of dynamic scheduling within a simulation environment, Computers and Operations Research, 21 (8), 909–925; Aytug, H., Bhattacharyya, S., Koehler, G.J., Snowdon, J.L., 1994. A review of machine learning in scheduling, IEEE Transactions on Engineering Management 41 (2) ) and study the performance and design issues in multi-agents information systems for dynamic scheduling in manufacturing. Among the design issue and performance issues considered in this research are coordination between agents, number of agents, and frequency of learning. Our results indicate that coordination between agents, and learning frequency play a significant role in the performance of multi-agent intelligent systems. <s> BIB006 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> 15 <s> This paper describes an intelligent distributed monitoring architecture for flexible manufacturing systems (FMS) based on the multi-agent paradigm. The proposed approach models the FMS by a society of cognitive agents, which monitor a set of heterogeneous resources. These agents have sufficient knowledge for the decision-making and they co-operate together in order to achieve the FMS monitoring functions. The originality of this approach resides in the total distribution of the monitoring functions over the agents and the co-operation of these agents by the contract net protocol for the real-time supervision. These characteristics improve flexibility, extensibility, real-time running, autonomy, fast reaction to faults, and development cost. Experimental results developed in simulation show the feasibility and the potentialities of the proposed multi-agent architecture for distributed monitoring where concepts such us flexibility, co-ordination, reactivity and integration are involved. <s> BIB007 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> 15 <s> Steel production is a complex process and finding coherent and effective schedules for the wide variety of production steps, in a dynamic environment, is a challenging task. In this paper, we propose a multi-agent architecture for integrated dynamic scheduling of the hot strip mill (HSM) and the continuous caster. The scheduling systems of these processes have very different objectives and constraints, and operate in an environment where there is a substantial quantity of real-time information concerning production failures and customer requests. Each process is assigned to an agent which independently, seeks an optimal dynamic schedule at a local level taking into account local objectives, real-time information and information received from other agents. Each agent can react to real-time events in order to fix any problems that occur. We focus here, particularly, on the HSM agent which uses a tabu search heuristic to create good predictive–reactive schedules quickly. The other agents simulate the production of the coil orders and the real-time events, which occur during the scheduling process. When real-time events occur on the HSM, the HSM agent might decide whether to repair the current schedule or reschedule from scratch. To address this problem, a range of schedule repair and complete rescheduling strategies are investigated and their performance is assessed with respect to measures of utility, stability and robustness, using an experimental simulation framework. <s> BIB008 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> 15 <s> This paper describes a negotiation protocol proposed for inter-agent cooperation in a multi-agent system we developed for optimisation and dynamic integrated scheduling of steel production. The negotiation protocol is a two-level bidding mechanism based on the contract net protocol. The purpose of this protocol is to allow the agents to cooperate and coordinate their actions in order to find globally near-optimal robust schedules, which are able to optimise the original production goals whilst minimising the disruption caused by the occurrence of unexpected real-time events. Experimental results show the performance of this negotiation protocol to coordinate the agents in generating good quality robust schedules. This performance is evaluated in terms of stability and utility measures used to evaluate the robustness of the steel production processes in the presence of real-time events. <s> BIB009 </s> SURVEY OF DYNAMIC SCHEDULING IN MANUFACTURING SYSTEMS <s> 15 <s> This paper describes a new model for robust predictive/reactive scheduling of steel continuous casting based on the use of multi-agents, tabu search and heuristic approaches. A continuous caster agent generates a predictive production schedule taking into account manufacturing requirements and local constraints using tabu search. The predictive schedule is modifies so as to minimize deviation between the performance measure values of the realized and predictive schedules in order to react to real-time events. We propose several schedule-repair and complete reschedule strategies to handle the real-time events, evaluate and compare their performance. The decision as to whether to locally repair the schedule or reschedule from scratch (complete reschedule) is based on three measures: robustness, utility and stability. Utility measures the change in schedule objective following schedule revision. Stability measures the deviation from the original schedule caused by schedule revision to quantify the undesirability of making large changes to the initial predictive schedule unless absolutely necessary. Robustness combines the utility and stability measures. In order to investigate the performance of these measures and strategies, simulation experiments were carried out and results are reported. <s> BIB010
Yams (Yet Another Manufacturing System)  ) is one of the earliest agent-based manufacturing system which assigns an agent to each node in a control hierarchy (factory, cell, workstation, machine, jobs). The main idea of Yams is that the job agents negotiate with resource agents to assign tasks to the machine agents using the contract net protocol.  developed a dynamic scheduling system in a cellular manufacturing system. In their work a manufacturing cell agent could sub-contract work to other cells through the contract net protocol  . Request for bid messages are broadcast to cells, and cells evaluate operations specification and submit bids, which describe their estimation on the earliest finishing time or shortest processing time. The cell that optimises a predefined criterion is selected to perform the operation. BIB002 , BIB003 BIB004 BIB007 proposed a simple multiagent architecture for dynamic scheduling in flexible manufacturing systems which involves only resource agents. The resource agents are responsible for dynamic scheduling of the resources and they have no control over each other. They negotiate using the contract net protocol to produce a global schedule. Each resource agent performs the following functions: scheduling, detection, diagnosis and error handling. Resource agents react locally to real-time events occurring on the corresponding resource using the corrective actions described in a knowledge base. When real-time events occur, such as machine breakdown, the resource agent renegotiates the jobs operations in failure to find alternative resource agents. For an increased flexibility and robustness BIB005 proposed a multi-agent architecture for dynamic scheduling in manufacturing systems which involves job and resource agents. The job agents negotiate the operations of the job with the resource agents using the contract net protocol. When a resource agent detects a malfunction, it sends a machine fault message to every job agent that has contracted its operations. On receiving the machine fault message, the job agent renegotiates the operations in failure with other resource agents capable of performing the operations. BIB008 BIB008  and BIB009 BIB010 proposed a novel multi-agent architecture for integrated and dynamic scheduling in steel production. Each steel production process is represented by an agent, including the continuous caster agents, the hot strip mill agent, the slabyard agent and the user agent. The hot strip mill and continuous caster agent perform the robust predictive-reactive scheduling of the hot strip mill and the continuous caster, respectively. Robust predictive-reactive scheduling generates robust predictive-reactive schedules in the presence of real-time events using utility, stability, and robustness measures and a variety of rescheduling heuristics. Recently levelled commitment contracts were proposed as an extension of the contract net protocol for increasing the economic efficiency of contracts between agents in the presence of incomplete information about future events. Sandholm (2000) described a levelled commitment contracting protocol for automated contracting in distributed manufacturing. The extended protocol allows self-interested agents to efficiently accommodate future events by giving the possibility for each agent to decommit from the contract by simply paying a de-commitment penalty to the other contract party. A de-commitment penalty is assigned to both agents in a contract to be freed from the contract. Some multi-agent-based scheduling systems used the auction and currency mechanisms for inter-agents negotiation. Agents exchange resources for money at prices determined through communication of bids. Solberg (1992, 1994) proposed an autonomous multi-agent architecture for shop floor dynamic scheduling based on a currency model that combined the scheduling objectives and price mechanism. Their model treats each job and resource as an agent. Job agents negotiate with resource agents via a contract net bidding mechanism to optimise a weighted objective that is a function of due date, price, quality, and other user defined factors. The part agent enters the system with certain currency and solicits and evaluates bids from several resource agents capable of fulfilling the processing requirements and selects the one that optimises its objective. Each resource agent sets its charging price based on its status, then it decides on the basis of the currency offered which of the announced jobs to consider more interesting for a possible bid submission. The job agent tries to minimise the price paid, but the resource agent's goal is to maximise the price charged. Each deal is completed once the job and resource agents are mutually committed. When a resource agent is in failure, it informs the corresponding job agent, and the latter proceeds to a renegotiation process on the operations in failure with the resource agents. AARIA (Autonomous Agents for Rock Island Arsenal) BIB001 ) is an autonomous multi-agent architecture developed for scheduling in an army manufacturing facility. Manufacturing resources, parts and people are encapsulated as autonomous agents. The system incorporates features of schedule optimisation and fault recovery. Agents cooperate using the currency negotiation protocol Other multi-agent based dynamic scheduling systems used learning approaches for dynamic scheduling. Aydin and Oztemel (2000) proposed a dynamic job shop scheduling using reinforcement learning agents. The agent is trained by an improved reinforcement-learning algorithm through the learning stage and then successfully makes the decisions to schedule the operations. The scheduling system consists of two parts: the simulated environment and the intelligent agent. The agent selects the most appropriate priority rule to select a job to assign to a machine according to the shop conditions, while simulated environment performs scheduling activities using the rule selected by the agent. BIB006 proposed multi-agent learning approaches for dynamic scheduling. In the multi-agent architecture, the work areas are controlled by agents with a knowledge base containing the dispatching rules and uses genetic algorithms-based learning to update 17 the rules in the knowledge-base at periodic intervals of time. The higher frequency of learning may help an agent to quickly adapt to variations on the shop floor.