T u t o r i a l
`
`Distributed Manufacturing
`Scheduling Using Intelligent
`Agents
`
`Weiming Shen, National Research Council Canada
`
`Manufacturing scheduling is an optimization process
`
`that allocates limited manufacturing resources over
`time among parallel and sequential manufacturing activities.
`This allocation must obey a set of rules or constraints that
`
`reflect the temporal relationships between manufacturing
`activities and the capacity limitations of a set of shared
`resources. The allocation also affects a schedule’s opti-
`mality with respect to criteria such as cost, lateness, or
`throughput.
`The globalization of manufacturing makes such opti-
`mization increasingly important. To survive in this com-
`petitive market, manufacturing enterprises must increase
`their productivity and profitability through greater shop
`floor agility. Agent-based manufacturing scheduling sys-
`tems are a promising way to provide this optimization.
`
`Manufacturing scheduling’s complexity
`Scheduling problems are not exclusive to manufactur-
`ing systems. Similar situations happen routinely in pub-
`lishing houses, universities, hospitals, airports, transporta-
`tion companies, and so on. Scheduling problems are
`typically NP-hard; that is, finding an optimal solution is
`impossible without using an essentially enumerative algo-
`rithm, and the computation time increases exponentially
`with the problem size. Manufacturing scheduling is one of
`the most difficult scheduling problems.
`A well-known manufacturing scheduling problem is
`classical job shop scheduling, which involves a set of jobs
`and a set of machines. Each machine can handle at most
`one job at a time. Each job consists of a chain of opera-
`tions, each of which must be processed during an uninter-
`rupted time period of given length on a given machine.
`The purpose is to find a best schedule—that is, an alloca-
`tion of the operations to time intervals on the machines
`that has the minimum duration required to complete all
`jobs. The total possible solutions for this problem with n
`jobs and m machines is (n!)m.
`The problem becomes even more complex when it
`includes other variables.
`
`Additional resources
`In a real manufacturing enterprise, production mana-
`gers or human schedulers must consider all kinds of man-
`ufacturing resources, not just jobs and machines. For
`example, a classical job shop scheduling problem with n
`jobs, m machines, and k operators could have ((n!)m)k pos-
`sible solutions.
`
`Simultaneous planning and scheduling
`Traditional approaches separating process planning and
`scheduling can obtain suboptimal solutions at two sepa-
`rate phases. Global optimization of a manufacturing sys-
`tem is only possible when process planning and schedul-
`ing are integrated. However, this makes the scheduling
`problem much more difficult to solve.
`
`Unforeseen dynamic situations
`In a job shop manufacturing environment, things rarely
`go as expected. Scheduled jobs get canceled and new jobs
`are inserted. Certain resources become unavailable and
`additional resources are introduced. A scheduled task
`takes more or less time than anticipated, and tasks arrive
`early or late. Other uncertainties include power system
`failures, machine failures, operator absence, and unavail-
`ability of tools and materials. An optimal schedule, gener-
`ated after considerable effort, might become unacceptable
`because of unforeseen dynamic situations on the shop
`floor. If this happens, a new schedule must be generated to
`restore performance. We call such a rescheduling problem
`dynamic scheduling or real-time scheduling.
`
`Manufacturing scheduling solutions
`The scheduling problem has received considerable
`attention because of its highly combinatorial aspects (NP-
`hard), dynamic nature, and practical interest for industrial
`applications. Consequently, researchers have proposed
`many different solutions.
`
`Traditional approaches
`Because direct methods are not available for complex
`scheduling problems, search is the usual strategy to solve
`
`88
`
`1094-7167/02/$17.00 © 2002 IEEE
`
`IEEE INTELLIGENT SYSTEMS
`
`Authorized licensed use limited to: Don Zhe Nan Wang. Downloaded on July 10,2021 at 01:31:05 UTC from IEEE Xplore. Restrictions apply.
`
`Applied Materials, Inc. Ex. 1014
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 1 of 7
`
`

`

`them. Generate-and-test is the simplest
`approach. It is often reasonable for simple
`problems but is not reasonable for large,
`complex problems, and there is no guaran-
`tee that a solution will ever be found. Many
`local search algorithms are generally appli-
`cable and flexible. They require a cost func-
`tion, a neighborhood function, and an effi-
`cient method for searching the neighborhood.
`Neighborhood search methods offer
`heuristic refinements to generate-and-test.
`Heuristic search lets us discover solutions
`that point us in interesting directions (that
`is, toward the optimum solution), although
`these solutions might be “bad” in that they
`might miss the true optimum. A good heu-
`ristic method can reach good (although
`possibly nonoptimum) solutions to hard
`problems in reasonable time. Heuristic
`methods try to replace the exhaustive search
`with some experience, thus reducing com-
`putational difficulty.
`Constraint satisfaction is another popu-
`lar approach; it operates in a space of con-
`straint sets rather than in a solution set
`space.1,2 Constraint satisfaction algorithms
`fall into two groups: search algorithms for
`finding a solution, and preprocessing algo-
`rithms (also called consistency algorithms)
`for reducing futile search space. Widely
`used algorithms include systematic depth-
`first tree search algorithms (backtracking)
`and hill-climbing algorithms (iterative
`improvement).
`Several approaches exploit search strate-
`gies that accept even cost-deteriorating
`neighbors. These approaches need some
`kind of learning mechanism. One example
`is simulated annealing, a randomized
`neighborhood search algorithm. It was
`inspired by physical annealing, which con-
`verts a solid to a pure lattice structure by
`placing it in a heat bath until it melts, then
`cooling it down slowly until it solidifies
`into a low-energy state. Simulated anneal-
`ing has been successfully applied to many
`single-objective scheduling problems.
`Another example is Tabu search. This
`approach combines deterministic iterative
`improvements with the possibility of accept-
`ing cost-increasing solutions occasionally, to
`direct the search away from local minimums.
`In genetic algorithms, learning occurs
`through a solution selection process. GAs
`discover superior solutions to global opti-
`mization problems adaptively—much like
`biological evolution—looking for small,
`local improvements rather than big jumps
`
`in a solution space. GA methodology
`seems to achieve small local climbs (adap-
`tations) without gradient information about
`the objective function being optimized.
`All traditional methods, whether analyti-
`cal, heuristic, or metaheuristic (including
`GAs, Tabu search, and simulated anneal-
`ing), encounter great difficulties when deal-
`ing with real situations. This is because they
`use simplified theoretical models and are
`essentially centralized—that is, a central
`computing unit performs all computations.
`This suggests that traditional approaches
`are inflexible, expensive, and slow to satisfy
`real-world scheduling problems.
`
`Agent-based approaches
`With agent-based approaches, manufac-
`turing resources (for example, machines,
`operators, robots, and setup stations) can be
`treated and represented as intelligent agents.
`They are connected through a local network
`(for example, an Ethernet). Unlike tradi-
`tional manufacturing scheduling systems
`using a centralized scheduler, an agent-
`based manufacturing scheduling system
`supports distributed scheduling such that
`each agent can locally handle the schedule
`of its machine, operator, robot, or station.
`However, the participating agents can col-
`lectively perform global scheduling through
`some negotiation mechanism and protocol
`(for example, a contract net protocol or an
`auction protocol, which I describe later).
`Agent-based approaches have several
`potential advantages for manufacturing
`scheduling:3,4
`
`• The agent paradigm uses parallel com-
`putation through a large number of
`processors, which could provide high
`efficiency and robustness.
`• The agent paradigm makes integrating
`process planning and manufacturing
`scheduling easy, so as to realize the
`simultaneous optimization of manufac-
`turing process planning and scheduling.
`• You can connect resource agents directly
`to their represented physical devices, so as
`to realize real-time dynamic rescheduling.
`This could provide high fault tolerance.
`• Agents can develop schedules using the
`same mechanisms that businesses use
`(negotiation rather than simple search) in
`the manufacturing supply chain. Thus,
`you can directly connect the manufactur-
`ing capabilities of different manufactur-
`ing enterprises. This will make optimiza-
`
`tion possible at the supply chain level, in
`addition to the shop floor level and the
`enterprise level.
`• Individual resources can trade off local
`performance to improve global perfor-
`mance, leading to cooperative scheduling.
`• You can combine other techniques with
`agent-based approaches at certain levels
`for learning and decision-making (I dis-
`cuss this in more detail later).
`
`Majors issues of agent-based
`manufacturing scheduling
`Anyone developing an agent-based man-
`ufacturing scheduling system must deal
`with four main issues among others: agent
`encapsulation, coordination and negotia-
`tion protocols, system architectures, and
`decision schemes for individual agents.
`
`Encapsulation
`Among the different approaches for agent
`encapsulation in manufacturing scheduling
`systems, two are distinct: functional decom-
`position and physical decomposition. Func-
`tional decomposition uses agents to encap-
`sulate modules assigned to functions such as
`order acquisition, planning, scheduling,
`material handling, transportation manage-
`ment, and product distribution. No explicit
`relationship exists between agents and phys-
`ical entities. Physical decomposition uses
`agents to represent entities in the physical
`world, such as operators, machines, tools,
`products, parts, and operations. An explicit
`relationship exists between an agent and a
`physical entity. Both approaches have dis-
`tributed (not centralized) implementations.
`Functional decomposition tends to share
`many state variables across different func-
`tional agents. This can lead to inconsistency
`and unintended interactions. Physical de-
`composition naturally defines distinct sets
`of state variables that individual agents
`with limited interactions can manage effi-
`ciently. However, it needs a large number
`of resource-related agents, which can lead
`to other problems (such as communication
`overhead) and complex agent management.
`However, functional decomposition is
`useful in integrating existing systems (for
`example, CAD tools, materials requirements
`planning systems, and databases), so as to
`resolve legacy problems.
`Corresponding to these two agent encap-
`sulation approaches are two types of dis-
`tributed manufacturing scheduling systems.
`
`JANUARY/FEBRUARY 2002
`
`computer.org/intelligent
`
`89
`
`Authorized licensed use limited to: Don Zhe Nan Wang. Downloaded on July 10,2021 at 01:31:05 UTC from IEEE Xplore. Restrictions apply.
`
`Applied Materials, Inc. Ex. 1014
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 2 of 7
`
`

`

`(a)
`
`(b)
`
`(c)
`
`Figure 1. System architectures for agent-based scheduling: (a) hierarchical,
`(b) federated, and (c) autonomous agent.
`
`In the first, scheduling is an incremental
`search process that can involve backtrack-
`ing.5–7 Agents, responsible for scheduling
`orders, perform local incremental searches
`for their orders and might consider multiple
`resources. The system merges the local
`schedules to produce a global schedule.
`This is similar to centralized scheduling.
`In the second system, an agent represents
`a single real-world resource (for example, a
`work cell, a machine, a tool, or an operator)
`and maintains this resource’s schedule. This
`agent might negotiate with other agents to
`carry out overall scheduling. Most agent-
`based manufacturing scheduling systems
`use this approach.
`
`Coordination and negotiation protocols
`Systems that use functional decomposi-
`tion are similar to traditional integrated
`systems; they usually use a predefined
`coordination mechanism. So, this section
`primarily discusses systems using physical
`decomposition.
`Most agent-based manufacturing sched-
`uling systems use negotiation protocols for
`resource allocation. The contract net proto-
`col8 or its modified versions are the most
`common, although some systems use other
`protocols such as Kenneth Fordyce and
`Gerald Sullivan’s voting protocol.7
`Reid Smith first proposed the CNP and
`demonstrated it on a distributed sensing
`system.8 To summarize, each agent (man-
`ager) having work to subcontract broad-
`casts an offer and waits for other agents
`(contractors) to send their bids. After some
`delay, the manager retains the best offers
`and allocates its contracts to one or more
`contractors, which then process the sub-
`task. The CNP coordinates task allocation,
`providing dynamic allocation and natural
`load balancing.
`The basic CNP is quite simple and can be
`efficient. However, when the number of
`
`nodes (agents) is large, the number of mes-
`sages on the network increases. This increase
`can lead to a situation where agents spend
`more time processing messages than doing
`the actual work or, worse, where the system
`stops because messages have flooded it. To
`avoid these problems, researchers have pro-
`posed various improvements to the basic
`CNP, such as
`
`• sending offers to a limited number of
`nodes (agents) instead of broadcasting
`them;
`• anticipating offers; that is, contractors
`send bids in advance;
`• varying the time when commitment is
`decided;
`• allowing decommitment (breaking com-
`mitments);
`• allowing several agents to answer as a
`group (coalition formation); and
`• introducing priorities for solving tasks.
`
`The negotiation protocol’s bidding mech-
`anism can be part-oriented,9 resource-
`oriented,10,11 or bidirectional.12
`The basic CNP selects a contractor by
`comparing bids corresponding to a particu-
`lar offer using predefined criteria. More
`complex versions introduce penalties, thus
`bringing the CNP nearer to a market-based
`approach. Several recent agent-based sched-
`uling systems have used such approaches,9,11
`which are becoming increasingly popular.
`Market-based protocols use a bargaining or
`auction process, which is simple and easy
`to use. Some agent-based manufacturing
`scheduling systems have implemented dif-
`ferent auction techniques from real market-
`places.
`Katia Sycara and her colleagues pro-
`posed a different approach using texture
`measures, where all agents share a com-
`mon information base, called a coordina-
`tion agent.5 Each agent computes its own
`
`texture measure and submits it to the coor-
`dination agent, then reads the integrated
`texture measure to make a decision. After
`individual agents make their decisions,
`they submit their solutions to the coordina-
`tion agent, which in turn regulates the pos-
`sible conflicts. While this approach could
`help agents predict possible conflicts, it
`would not eliminate conflicts.
`Some authors have also realized the
`game-like nature of independent schedul-
`ing decisions and have tried to use game
`theory to make their agents smarter.13
`Another solution is to combine the agent-
`based approach with traditional approaches.
`I look at this in more detail later.
`
`Architectures
`Agent system architectures provide the
`frameworks within which agents are de-
`signed and constructed. Architectures for
`agent-based manufacturing scheduling
`systems fall into three categories: hierar-
`chical, federated, and autonomous agent
`(see Figure 1).
`
`Hierarchical. A typical manufacturing
`enterprise consists of a number of physi-
`cally distributed, semiautonomous units,
`each with some control over local re-
`sources and with different information
`requirements. In this situation, a number of
`practical agent-based industrial applica-
`tions still use the hierarchical architecture,
`although critics often complain about its
`centralized character. In fact, agent-based
`distributed manufacturing scheduling sys-
`tems using functional decomposition usu-
`ally have a hierarchical architecture be-
`cause each agent represents a function or a
`department in a traditional manufacturing
`system. Examples of such systems include
`Distributed Asynchronous Scheduling,6 the
`Logistics Management System,7 the Archi-
`tecture for Distributed Dynamic Manufac-
`turing Scheduling,10 and Holonic Manufac-
`turing Systems.14 I describe these in the
`section “The research literature.”
`
`Federated. Because hierarchical archi-
`tectures suffer serious problems due to
`centralization, federated multiagent archi-
`tectures increasingly are considered a com-
`promise solution for industrial agent-based
`applications, especially for large-scale engi-
`neering applications. A fully federated
`agent-based system has no explicit shared
`facility for storing active data. Rather, the
`
`90
`
`computer.org/intelligent
`
`IEEE INTELLIGENT SYSTEMS
`
`Authorized licensed use limited to: Don Zhe Nan Wang. Downloaded on July 10,2021 at 01:31:05 UTC from IEEE Xplore. Restrictions apply.
`
`Applied Materials, Inc. Ex. 1014
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 3 of 7
`
`

`

`Broker 1
`
`Broker 2
`
`Agent
`
`Matchmaker
`
`Client agents
`
`Broker 3
`
`Service agents
`(resource agents)
`
`Broker agents
`
`Agent
`
`Agent
`
`Agents
`Facilitators
`Messages between facilitators
`
`(a)
`
`(b)
`
`(c)
`
`Figure 2. Federated architectures: (a) facilitator, (b) broker, and (c) matchmaker.
`
`system stores all data in local databases and
`handles updates and changes through mes-
`sage passing.
`For agent-based manufacturing systems,
`four types of federated architectures domi-
`nate: facilitators, brokers, matchmakers,
`and mediators. Facilitators (see Figure 2a)
`combine several related agents into a group.
`Communication between agents takes
`place through an interface also called a
`facilitator. Each facilitator provides an
`intermediary between a local collection of
`agents and remote agents. It usually does
`this by providing two main services: rout-
`ing outgoing messages to the appropriate
`destinations and translating incoming mes-
`sages for consumption by its agents. Many
`agent-based collaborative design systems
`have used this approach.4
`Brokers (see Figure 2b), also called bro-
`ker agents, are similar to facilitators, with
`additional functions such as monitoring
`and notification. The functional difference
`between a facilitator and a broker is that a
`facilitator is responsible for only a desig-
`nated group of agents, whereas any agent
`can contact any broker in the same system
`for finding service agents to complete a
`special task.
`The matchmaker architecture (see Figure
`2c) is a superset of the broker architecture,
`because it uses the brokering mechanism to
`match agents. The Foundation for Intelli-
`gent Physical Agents (www.fipa.org) has
`proposed yellow-pages agents and direc-
`tory facilitators, which are similar to
`matchmakers.
`Besides functioning as a facilitator and a
`matchmaker, mediators assume the role of
`system coordinator by promoting cooperation
`among intelligent agents and learning
`from the agents’ behavior.3,4 This archi-
`
`tecture imposes a static or dynamic hier-
`archy for every specific task, which pro-
`vides computational simplicity and man-
`ageability. It is suitable for developing
`distributed manufacturing scheduling
`systems that are complex and dynamic
`and that comprise many resource agents.
`Federated multiagent architectures can
`coordinate multiagent activity through facil-
`itation or mediation to reduce overhead,
`ensure stability, and provide scalability. They
`promise to be a good foundation on which to
`develop open, scalable multiagent systems.
`
`Autonomous agent. Different definitions of
`autonomous agents exist; however, an au-
`tonomous agent usually
`
`• is not controlled or managed by any
`other software agent or human being,
`• can communicate and interact directly
`with other agents in the system and with
`other external systems,
`• has knowledge about other agents and its
`environment, and
`• has its own goals and an associated set of
`motivations.
`
`The autonomous agent architecture is well
`suited for developing distributed manufac-
`turing systems consisting of a small num-
`ber of agents. I describe two such systems
`in the section “The research literature.”
`
`Hybrid. MetaMorph II3 combines the ap-
`proaches I’ve described to develop more
`flexible, modular, scalable, and dynamic
`manufacturing systems. By combining the
`mediator and autonomous agent approaches,
`MetaMorph II’s hybrid architecture lets an
`agent in one subsystem communicate di-
`rectly with other subsystems or agents
`
`in other subsystems, thereby mitigating
`bottlenecks.
`
`Decision schemes
`Here I address what kind of decision
`scheme an individual agent should have to
`realize effective agent-based cooperative
`scheduling. As in the section on coordina-
`tion and negotiation, I focus on systems
`using physical decomposition.
`In most agent-based manufacturing
`scheduling systems using market-based and
`bidding-based protocols, individual agents
`need to reply to all kinds of offers. They
`also sometimes need to compete, negotiate,
`or bargain with other agents. Rich knowl-
`edge and powerful learning and reasoning
`mechanisms are important. Each agent
`should have at least knowledge about the
`capability, availability, and cost of the phys-
`ical resource (for example, a machine) that
`it represents. A more sophisticated agent
`can have knowledge about other agents in
`its system, knowledge of the products to be
`manufactured, a knowledge base of previ-
`ously successful cases, and so on.
`An agent’s decision scheme depends
`primarily on two aspects: the coordination
`or negotiation mechanisms that the multia-
`gent system uses and the agent’s local
`decision-making mechanisms with avail-
`able knowledge. For example, a CNP
`needs each agent to reply to an offer with
`requested information such as cost, start
`time, processing time, and so on. A game
`theory-based multiagent system needs
`agents to follow game rules.13 A multia-
`gent system implemented with a conversa-
`tion scheme needs each agent to follow the
`conversation policies.4 Local decision
`making might use different kinds of mech-
`anisms, such as rule- or case-based reason-
`
`JANUARY/FEBRUARY 2002
`
`computer.org/intelligent
`
`91
`
`Authorized licensed use limited to: Don Zhe Nan Wang. Downloaded on July 10,2021 at 01:31:05 UTC from IEEE Xplore. Restrictions apply.
`
`Applied Materials, Inc. Ex. 1014
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 4 of 7
`
`

`

`ing mechanisms, according to the agent’s
`knowledge. Updating an agent’s knowl-
`edge requires a learning mechanism,
`which can range from being case-based to
`neural network- or fuzzy logic-based.
`
`The research literature
`Over the past two decades, a number of
`researchers have used agent technology in
`attempts to resolve the manufacturing sched-
`uling problem. The following paragraphs
`provide a short research literature review.
`
`Early attempts
`Michael Shaw might have been the first
`to suggest using agents in manufacturing
`scheduling and factory control. He proposed
`that a manufacturing cell could subcontract
`work to other cells through a bidding mech-
`anism.15 YAMS (Yet Another Manufacturing
`System), another early agent-based manu-
`facturing system, represented each factory
`and factory component as an agent.16 Each
`agent had a collection of plans, representing
`its capabilities. YAMS used the CNP for
`interagent negotiation.
`
`Methodologies and techniques
`CORTES used microopportunistic tech-
`niques to solve the scheduling problem
`through a two-agent system, where each
`agent schedules a set of jobs and monitors
`a set of resources.5 It was a typical schedul-
`ing system using functional decomposition.
`Albert Baker proposed a market-driven
`contract net for heterarchical agent-based
`scheduling.11 He introduced a market-based
`mechanism into the contract net-based nego-
`tiation and made the manufacturing schedul-
`ing system more like other business systems.
`The Logistics Management System applied
`integration decision technologies to sched-
`ule semiconductor manufacturing.7 LMS
`used functional agents, one for each pro-
`duction constraint, and a judge agent to
`combine the votes of four different critics.
`Each agent modeled those aspects of the
`environment needed to satisfy its objective.
`Its uniqueness was the voting protocol I
`mentioned earlier.
`Jyi Shane Liu and Katia Sycara proposed
`Constraint Partition and Coordinated Re-
`action, a coordination mechanism for job
`shop constraint satisfaction. CP&CR as-
`signed each resource to a resource agent
`and each job to a job agent.2 A resource
`agent enforced capacity constraints on the
`resource; a job agent enforced temporal
`
`precedence and release-date constraints
`within the job. CP&CR was a good exam-
`ple of integrating agent-based approaches
`with constraint satisfaction.
`AARIA (Autonomous Agents at Rock
`Island Arsenal) encapsulated the manufac-
`turing capabilities (for example, people,
`machines, and parts) as autonomous
`agents.17 Each agent seamlessly interoper-
`ated with other agents in and outside its
`factory. Agents communicate using sub-
`ject-based addressing; that is, messages
`are labeled by content rather than by
`recipient and are forwarded to all agents
`subscribing to the specified content area.
`
`The increasing use of bidding- or
`market-based negotiation
`protocols necessitates research
`and development of more
`sophisticated negotiation
`mechanisms and protocols.
`
`It was one of the few manufacturing
`scheduling systems that have used
`autonomous agents.
`Kazuo Miyashita proposed an integrated
`architecture for distributed planning and
`scheduling combining the repair-based
`methodology with the constraint-based
`mechanism of dynamic coalition formation
`among agents.1 He implemented the CAMPS
`(Case-Based Multiagent Planning/Schedul-
`ing) prototype system, another example of
`integrating agents with constraint satisfac-
`tion. In CAMPS, a set of intelligent agents
`tried to coordinate their actions for satisfy-
`ing planning and scheduling results by han-
`dling several intra-agent and interagent
`constraints.
`
`Approaches and architectures
`Peter Burke and Patrick Prosser’s Dis-
`tributed Asynchronous Scheduling archi-
`tecture consisted of three types of entities:
`knowledge resources, agents, and a con-
`straint maintenance system.6 The knowl-
`edge resources contained frame-based
`
`knowledge for resources, aggregate re-
`sources, operations, process plans, and
`what they called a strategic unit. A strate-
`gic unit is the root of a hierarchy (of all
`entities) and is concerned with the schedul-
`ing problem as a whole. Originally, the
`agents formed a multiagent heterarchy to
`represent only resources (O-agents). The
`final architecture had agents for different
`aggregations of resources (T-agents) and an
`agent for overseeing scheduling (S-agent).
`The S-agent assigned operations to T-
`agents, who assigned them to their respec-
`tive O-agents. The O-agents then scheduled
`these operations on their respective re-
`sources. DAS could make a correct sched-
`ule but had no method for optimizing that
`schedule.
`ADDYMS (Architecture for Distributed
`Dynamic Manufacturing Scheduling)
`decomposed scheduling into two levels.10
`The first assigned a manufacturing work
`cell to a task. The second determined local
`resources, such as operators and tools, that
`a number of work cells might share. Corre-
`sponding to these levels were site and
`resource agents. A site agent scheduled
`work at a particular work cell. A resource
`agent represented each local resource at a
`work cell. The system comprised several
`connected site agents, each of which in turn
`was connected with its subsite agents and
`some local resource agents.
`Grace Lin and James Solberg showed
`how to use a market-like control model for
`adaptive resource allocation and distrib-
`uted scheduling.9 They modeled the manu-
`facturing shop floor exactly like a market-
`place. Each task agent entered the market
`carrying certain “currency” and bargained
`with each resource agent on which it could
`be processed. At the same time, each re-
`source agent competed with other agents
`to get a more valuable job. They incorpo-
`rated the market mechanism, using multi-
`ple-way and multiple-step negotiation, to
`coordinate these autonomous agents in the
`shop floor.
`Khalid Kouiss and his colleagues pro-
`posed a multiagent architecture for dy-
`namic job shop scheduling.18 Each agent
`was dedicated to a work center and per-
`formed local dynamic scheduling by
`selecting an adequate dispatching rule. It
`selected the most suitable dispatching
`rules. Depending on local and global con-
`siderations, a new selection happened
`when a predefined event occurred. Opti-
`
`92
`
`computer.org/intelligent
`
`IEEE INTELLIGENT SYSTEMS
`
`Authorized licensed use limited to: Don Zhe Nan Wang. Downloaded on July 10,2021 at 01:31:05 UTC from IEEE Xplore. Restrictions apply.
`
`Applied Materials, Inc. Ex. 1014
`Applied v. Ocean, IPR Patent No. 6,968,248
`Page 5 of 7
`
`

`

`mizing the numerical thresholds used to
`detect symptoms (behaviors) improved the
`selection method. Agents could also coor-
`dinate their actions to perform global dy-
`namic scheduling. However, this required a
`global agent to detect the whole shop
`floor’s symptom.
`Paulo Sousa and Carlos Ramos proposed
`a dynamic-scheduling system architecture
`composed of holons representing tasks
`and holons representing manufacturing
`resources.14 A holon is a special type of
`agent that is characteristically autonomous,
`cooperative, and recursive and that populates
`a system that makes no high-level distinction
`between hardware and software. Sousa and
`Ramos adapted the CNP to handle temporal
`constraints and deal with conflicts.
`
`Testbeds and industrial applications
`Only a few testbeds and real industrial
`applications have been developed and
`reported. IBM has used LMS in commer-
`cial production.7 The National Center for
`Manufacturing Sciences’ Shop Floor
`Agents project applied agent-based systems
`for shop floor scheduling and machine con-
`trol.19 The prototype systems supported
`three industrial scenarios sponsored by
`three industrial project members (AMP,
`General Motors, and Rockwell Automa-
`tion/Allen-Bradley).
`
`Research opportunities and
`challenges
`Based on an extensive literature survey
`as well as my own research and develop-
`ment experience, I foresee many research
`opportunities and challenges.
`
`Negotiation mechanisms and protocols
`First, the increasing use of bidding- or
`market-based negotiation protocols neces-
`sitates research and development of more
`sophisticated negotiation mechanisms and
`protocols. Combinatorial market-based
`negotiation protocols are of much interest
`for the near future.
`
`Integrating planning, scheduling, and
`control
`Agent-based approaches provide a natural
`way to integrate manufacturing process
`planning, scheduling, and execution control.
`As I mentioned before, they also provide the
`possibility of simultaneous optimization of
`process planning and manufacturing sched-
`uling. However, they significantly increase
`
`the problem’s complexity. This topic re-
`quires much more research, including for-
`mal modeling of such integration.
`
`Integrating agent-based and traditional
`approaches
`Because bidding- or market-based ap-
`proaches emphasize flexibility and respon-
`siveness, rather than the optimality of solu-
`tions, they are more suitable for dynamic
`rescheduling. Approaches to search such as
`GAs and simulated annealing focus more on
`the optimality of solutions, so they are more
`suitable for advance scheduling. Shop floors
`that require both advance and dynamic
`scheduling could combine some of these
`approaches. For example, Thouraya Daouas
`and her colleagues proposed combining
`agent-based negotiation with simulated
`annealing search.20 I have proposed combin-
`ing agent-based negotiation with GAs for
`scheduling optimization.21
`Also, integrating agent-based approaches
`with other traditional approaches (such as
`fuzzy logic- and artificial neural network-
`based learning, Petri net- or color Petri net-
`based coordination, or constraint satisfac-
`tion) will likely produce sophisticated
`manufacturing scheduling systems.
`
`Combining individual solving and
`coordination–negotiation
`Obviously, a trade-off exists between
`solving at the individual agent level and the
`coordination–negotiation scheme at the
`system level. The challenge is how to com-
`bine them using integration such as I men-
`tioned earlier.
`
`Benchmarks
`We need benchmarks to compare differ-
`ent agent