IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART C: APPLICATIONS AND REVIEWS, VOL. 36, NO. 4, JULY 2006
`
`563
`
`Agent-Based Distributed Manufacturing Process
`Planning and Scheduling: A State-of-the-Art Survey
`
`Weiming Shen, Senior Member, IEEE, Lihui Wang, and Qi Hao
`
`Abstract—Manufacturing process planning is the process of se-
`lecting and sequencing manufacturing processes such that they
`achieve one or more goals and satisfy a set of domain constraints.
`Manufacturing scheduling is the process of selecting a process plan
`and assigning manufacturing resources for specific time periods to
`the set of manufacturing processes in the plan. It is, in fact, an op-
`timization process by which limited manufacturing resources are
`allocated over time among parallel and sequential activities. Manu-
`facturing process planning and scheduling are usually considered
`to be two separate and distinct phases. Traditional optimization
`approaches to these problems do not consider the constraints of
`both domains simultaneously and result in suboptimal solutions.
`Without considering real-time machine workloads and shop floor
`dynamics, process plans may become suboptimal or even invalid
`at the time of execution. Therefore, there is a need for the integra-
`tion of manufacturing process-planning and scheduling systems for
`generating more realistic and effective plans. After describing the
`complexity of the manufacturing process-planning and scheduling
`problems, this paper reviews the research literature on manufac-
`turing process planning, scheduling as well as their integration,
`particularly on agent-based approaches to these difficult problems.
`Major issues in these research areas are discussed, and research
`opportunities and challenges are identified.
`
`Index Terms—Agents, distributed manufacturing systems, man-
`ufacturing scheduling, multiagent systems, process planning.
`
`ingly important for manufacturing enterprises to increase their
`productivity and profitability through greater shop floor agility
`to survive in a globally competitive market [98].
`This paper describes the complexity of manufacturing
`process-planning and scheduling problems (Section II), and re-
`views the research literature in manufacturing process planning
`(Section III), manufacturing scheduling (Section IV), and the
`integration of process planning and scheduling (Section V),
`particularly focusing on agent-based approaches in these areas.
`Major issues in these research areas are discussed (Section VI),
`research opportunities and challenges addressed (Section VII),
`and a brief conclusion stated (Section VIII).
`The objective of this paper is not to provide an extensive sur-
`vey of general manufacturing process-planning and scheduling
`systems, but to focus on the agent-based approaches and their
`applications in manufacturing process planning and scheduling.
`An earlier survey of multiagent systems for intelligent manu-
`facturing systems, including agent-based manufacturing process
`planning, scheduling, and control, can be found in [92]. More
`discussions on the applications of agent technology to collabo-
`rative design and manufacturing can be found in [94].
`
`I. INTRODUCTION
`
`M ANUFACTURING process planning and scheduling are
`
`usually considered to be two separate activities in man-
`ufacturing. Manufacturing process planning determines how a
`product will be manufactured. It is the process of selecting and
`sequencing manufacturing processes and parameters so that they
`achieve one or more goals (e.g., lower cost, shorter processing
`time, etc.) and satisfy a set of domain constraints. Manufactur-
`ing scheduling, on the other hand, is the process of assigning
`manufacturing resources over time to the set of manufacturing
`processes in the process plan. It determines the most appropriate
`time to execute each operation, taking into account the temporal
`relationships between manufacturing processes and the capac-
`ity limitations of the shared manufacturing resources. The as-
`signments also affect the optimality of a schedule with respect
`to criteria such as cost, tardiness, or throughput. In summary,
`scheduling is an optimization process where limited resources
`are allocated over time among both parallel and sequential activ-
`ities [136]. Such an optimization process is becoming increas-
`
`Manuscript received December 5, 2003; revised February 3, 2005 and June
`29, 2005. This paper was recommended by Associate Editor V. Marik.
`The authors are with Integrated Manufacturing Technologies Institute, Na-
`tional Research Council Canada, London, ON, Canada (e-mail: weiming.shen@
`nrc.gc.ca; lihui.wang@nrc.gc.ca; qi.hao@nrc.gc.ca).
`Digital Object Identifier 10.1109/TSMCC.2006.874022
`
`II. PROBLEM COMPLEXITY
`
`The problem of manufacturing process planning and schedul-
`ing has been introduced in Section I. This section discusses the
`complexity of the problem and the difficulty in solving it.
`The scheduling problem exists not only in manufacturing
`enterprises, but also in organizations like publishing houses,
`universities, hospitals, airports, and transportation companies.
`It is typically NP-hard, i.e., it is impossible to find an optimal
`solution without the use of an essentially enumerative algorithm,
`with computation time increasing exponentially with problem
`size. However, the manufacturing scheduling problem is one
`of the most difficult of all scheduling problems. More detailed
`discussions and analyses of scheduling problems can be found
`in [5], [29].
`A well-known manufacturing scheduling problem is the clas-
`sical job shop scheduling where a set of jobs and a set of ma-
`chines are given. Each machine can handle at most one job at a
`time. Each job consists of a chain of operations, each of which
`needs to be processed during an uninterrupted time period of
`given length on a given machine. The purpose is to find the best
`schedule, i.e., an allocation of the operations to time intervals
`on the machines, that has the minimum total duration required
`to complete all jobs. The total number of possible solutions
`for a classical job shop scheduling problem with n jobs and m
`machines is (n!)m [5].
`
`1094-6977/$20.00 © 2006 Canadian Crown Copyright
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1013, IPR2022-00681, Pg. 1
`
`

`

`564
`
`IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART C: APPLICATIONS AND REVIEWS, VOL. 36, NO. 4, JULY 2006
`
`The problem becomes even more complex in the following
`situations.
`1) When other manufacturing resources, such as operators
`and tools, are also considered during the scheduling pro-
`cess. For a classical job shop scheduling problem with n
`jobs, m machines, and k operators, the total number of
`possible solutions could be ((n!)m )k .
`2) When both process planning and manufacturing schedul-
`ing are to be done at the same time. Traditional approaches
`that treat process planning and manufacturing scheduling
`separately can result in suboptimal solutions for the two
`phases. Integrating the two phases into one optimization
`problem, by considering the constraints of both domains
`simultaneously, can theoretically result in a global optimal
`solution, but it increases the solution space significantly.
`3) When unforeseen dynamic situations are considered. In a
`job shop manufacturing environment, rarely do things go
`as expected. The system may be asked to include addi-
`tional tasks that are not anticipated, or to adapt to changes
`to several tasks, or to neglect certain tasks. The resources
`available for performing tasks are subject to changes. Cer-
`tain resources can become unavailable, and additional re-
`sources can be introduced. The beginning time and the
`processing time of a task are also subject to variations. A
`task can take more or less time than anticipated, and tasks
`can arrive early or late. Other uncertainties include power
`system failures, machine failures, operator absence, and
`unavailability of tools and materials. An optimal schedule,
`generated after considerable effort, may rapidly become
`unacceptable because of unforeseen dynamic situations
`on the shop floor and a new schedule may have to be gen-
`erated. This kind of rescheduling problem is also called
`dynamic scheduling or real-time scheduling.
`
`III. APPROACHES TO MANUFACTURING PROCESS PLANNING
`
`A. Traditional Approaches
`
`Traditionally, manufacturing process planning is a task that
`transforms design information into manufacturing processes and
`determines the sequence of operations [15]. Maintaining the
`consistency of process plans and keeps them optimized is a
`difficult task. Since 1965, when Nieble [74] reported the first
`computer-aided process planning (CAPP) system, numerous re-
`search efforts have been reported in this area.
`Generally, CAPP approaches can be classified into two cat-
`egories: variant and generative. The success of the variant ap-
`proach depends on group technology and computerized database
`retrieval. When a new part enters a factory, a previous similar
`process plan is retrieved from the database and modified to suit
`the new part. This method is especially suitable for compa-
`nies with few, and relatively fixed, product families and a large
`number of parts per family. Most of the earlier CAPP systems
`can be categorized under the variant approach [2]. The genera-
`tive approach, on the other hand, can be used to automatically
`generate an optimal process plan according to the part’s fea-
`tures and manufacturing requirements. Most of the generative
`systems in the literature are knowledge-based systems utilizing
`
`artificial intelligence techniques. They are oriented toward the
`needs of large companies, especially those producing products
`with large variety and small batch sizes. However, a truly gen-
`erative process-planning system that can meet industrial needs
`and provide an appropriate generic framework, knowledge rep-
`resentation methods, and inference mechanisms has not been
`developed so far [134].
`Various approaches to CAPP have been proposed in the
`literature [2], [25]. Research studies on process planning in-
`clude object-oriented approaches [105], [132], GA-based ap-
`proaches [70], [131], neural-network-based approaches [21],
`[69], Petri net-based approaches [53], feature recognition or
`feature-driven approaches [114], [119], and knowledge-based
`approaches [108], [118]. These approaches and their combina-
`tions have been applied to some specific problem domains, such
`as tool selection [24], [56], tool path planning [7], [45], machin-
`ing parameters selection [3], [37], process sequencing [129],
`and setup planning [75], [125].
`Recently, the research focus on process planning has shifted
`toward solving problems in distributed manufacturing environ-
`ments. Tu et al. [115] introduced a method called incremental
`process planning (IPP) for one-of-a-kind production (OKP) in
`such environments. The IPP is used to extend or modify a prim-
`itive plan (a skeletal process plan) incrementally according to
`new features that are identified from a product design until no
`more new features can be found. A complete process plan gen-
`erated by the IPP may include alternative processes.
`
`B. Agent-Based Approaches
`
`Apart from centralized AI approaches [e.g., genetic algo-
`rithms (GAs), neural networks, fuzzy logic, and expert systems],
`agent technology is emerging as a solution for distributed AI that
`has attracted a wide attention. Instead of being one large expert
`system, cooperative intelligent agents are being used in devel-
`oping distributed CAPP systems. The agent-based approach is
`also being recognized as an effective way to realize adaptive-
`ness and dynamism of process planning. The following are some
`examples of agent-based process-planning systems.
`1) Shih and Srihari [99] proposed a distributed AI-based
`framework for process planning. Their approach decom-
`poses the entire production control task into several sub-
`tasks, each of which is implemented by an intelligent
`agent. By working collaboratively, the agents can reach
`a solution for the problem.
`2) CoCAPP [133], [134] was proposed to distribute com-
`plex process-planning activities to multiple specialized
`problem solvers and to coordinate them to solve com-
`plex problems. The CoCAPP attempts to satisfy five
`major requirements: autonomy, flexibility, interoperabil-
`ity, modularity, and scalability. It builds cooperation and
`coordination mechanisms into distributed agents using
`knowledge-based techniques. Each agent in the system
`deals with a relatively independent functional domain in
`process planning.
`3) Zhang et al.
`[132] proposed an agent-based adap-
`tive process-planning (AAPP) system on top of an
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1013, IPR2022-00681, Pg. 2
`
`

`

`SHEN et al.: AGENT-BASED DISTRIBUTED MANUFACTURING PROCESS PLANNING AND SCHEDULING
`
`565
`
`resources modeling
`object-oriented manufacturing
`(OOMRM) framework. The OOMRM describes man-
`ufacturing resources’ capability and capacity in an
`object-oriented manner, while the AAPP is implemented
`as an integrated process-planning platform. Instead of
`automating process-planning tasks completely, the AAPP
`system provides an interactive mode to enable experienced
`manufacturing engineers to make decisions at crucial
`points. Five agents are used in the AAPP to carry out
`part information classification, manufacturing resources
`mapping, process planning, human planning, and ma-
`chining parameter retrieval. A contract net-based scheme
`is utilized as the coordination protocol between agents.
`4) Sluga et al. [102] introduced a virtual work system (VWS)
`as the essential building block for in a distributed man-
`ufacturing environment. The VWS represents a manu-
`facturing work system in the information space, and is
`structured as an autonomous agent. It is a constituent
`entity of an agent network in which dynamic clusters
`of cooperating agents are solving manufacturing tasks.
`The decision-making in process planning is based on
`a market mechanism consisting of bidding–negotiation–
`contracting phases. The VWS approach aims at enabling
`dynamic decision-making based on the actual state of the
`manufacturing environment.
`5) CyberCut [103] is a research project that aims at devel-
`oping a networked manufacturing service for rapid part
`design and fabrication on the Internet. A critical part
`of this service is an automated process-planning mod-
`ule that is capable of generating process plans to sat-
`isfy the desired geometries and specified requirements.
`Three types of agents are designed to facilitate CyberCut:
`primary process-planning agent, environmental planning
`agent, and burr minimization tool path planning agent [22].
`The multiagent planning module incorporates conven-
`tional and specialized planning agents for environmental
`consideration and burr minimization. However, the inter-
`actions between agents are based on human decisions.
`6) IDCPPS [14] was reported to be an integrated, distributed,
`and cooperative process-planning system. The process-
`planning tasks are broken into three levels, namely, initial
`planning, decision-making, and detail planning. The initial
`planning deals with the manufacturability evaluation of a
`design and the generation of alternative processing routes
`based on feature reasoning. The decision-making level
`takes place when the orders have been released for produc-
`tion on the shop floor. The result of this step is a ranked list
`of near-optimal alternative plans that considers the avail-
`ability of shop floor resources. The detail planning is exe-
`cuted just before manufacturing begins. This step finishes
`the final selection of machines, tools, cutting parameters,
`and the calculation of machining cost and time. Different
`functional modules are grouped into different agents, in-
`cluding the three process-planning agents dealing with the
`above three-level planning, plus the task agents, resource
`agents, and coordination agents (CAD/Process coordina-
`tion agent and Process/Production coordination agent).
`
`However, the whole framework seems to have been de-
`signed at a high level. No practical systems were reported.
`7) Similarly, Lim and Zhang [55] introduced an APPSS sys-
`tem, which is made up of a number of agents and functional
`modules. This system is mainly used for the dynamic re-
`configuration and optimization of resource utilization in
`manufacturing shop floors by considering the real-time
`process-planning and scheduling issues.
`8) Kornienko et al. [50] considered process planning as a
`typical constraint satisfaction problem to generate an op-
`timized plan in a distributed way satisfying all restrictions
`in the presence of different disturbances. An agent plays
`different “roles” and has a primary algorithm (determined
`by interactive pattern) and a set of emergency states to
`handle local emergencies or global emergencies. In case
`an agent is in emergency state recognized by the activity
`guard agent, it could either resolve the emergency by itself
`or request a rescue agent to handle it.
`In addition to the above systems, there are also other simi-
`lar research efforts toward agent-based process planning [78],
`[110]. All these systems tend to solve the process-planning prob-
`lem by cooperation and negotiation among intelligent agents.
`The agents making up the systems usually use the function de-
`composition approach as described in Section VI.
`
`IV. APPROACHES TO MANUFACTURING SCHEDULING
`
`A. Traditional Approaches
`
`Because of its highly combinatorial aspects (NP-complete),
`dynamic nature, and practical usefulness for industrial applica-
`tions, the scheduling problem has been widely studied in the
`literature by various methods: heuristics, constraint propagation
`techniques, constraint satisfaction problem formalisms, Tabu
`search, simulated annealing, GAs, neural networks, fuzzy logic,
`etc. [136].
`As direct methods are not available for complex scheduling
`problems, search methods are usually adopted to solve these
`problems. However, the simplest generate-and-test search strat-
`egy is not a reasonable approach for large complex problems.
`Many local search algorithms are more appropriate. These al-
`gorithms require a cost function, a neighborhood function, and
`an efficient method for exploring the neighborhood.
`A variety of neighborhood search methods have been cre-
`ated including climbing, simulated annealing, etc. These meth-
`ods offer heuristic refinements to the generate-and-test. Heuris-
`tic approaches try to replace the exhaustive search strategies
`with some sophisticated experience. With the aid of heuristics
`in searching strategies, good solutions (though possibly non-
`optimal) to hard problems can be found within greatly reduced
`computation time.
`The Petri Net approach and its variants, due to its graphical
`representation and mathematical analysis of the control logic
`of a manufacturing system, provide a powerful approach to
`model, control, and schedule an automated system, in both
`its information flows and its material flows. Colored timed
`object-oriented Petri Nets (CTOPN) [123] further incorporates
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1013, IPR2022-00681, Pg. 3
`
`

`

`566
`
`IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART C: APPLICATIONS AND REVIEWS, VOL. 36, NO. 4, JULY 2006
`
`structured, reusable, and easily maintainable control/decision
`knowledge that can be used in scheduling/dispatching.
`Constraint satisfaction is another search procedure that oper-
`ates in the space of constraint sets rather than in the solution set
`space [59], [60], [68].
`The objective of multisite scheduling [86] is to support the
`scheduling activities of a global scheduler or schedulers in dis-
`tributed production plants in a cooperative way. A schedule
`generated on a global level must be translated into detailed
`schedules as part of the local scheduling process. In the case of
`a disturbance, feedback between the local and global levels is
`essential. Global-level data are derived from aggregated local
`data, and are normally imprecise or estimated.
`Several approaches take advantages of search strategies in
`which even cost-deteriorating neighbors are accepted. Simu-
`lated annealing uses an analogy with the physical process of
`annealing, in which a pure lattice structure of a solid is made
`by heating up the solid in a heat bath until it melts, then cool-
`ing it down slowly until it solidifies into a low-energy state.
`As designed, simulated annealing is a randomized neighbor-
`hood search algorithm and it has been successfully applied to
`solve many single-objective scheduling problems. Tabu search
`combines deterministic iterative improvements with the pos-
`sibility of accepting cost-increasing solutions occasionally—
`to direct the search away from local minimum [32]. In GAs,
`learning occurs through a solution selection process. GAs dis-
`cover superior solutions to global optimization problems adap-
`tively (akin to the evolution of organisms in the natural world)
`by searching for small, local improvements rather than big
`jumps in a solution space. Fuzzy logic-based scheduling is used
`to support the scheduling activities in a multisite scheduling
`scenario [86]. In this system, a global scheduler or sched-
`ulers in distributed production plants work in a cooperative
`way, based on adequate modeling and processing of imprecise
`data. A robust prescription is created for the local scheduling
`systems.
`All the traditional scheduling methods, whether analytical,
`heuristic, or metaheuristic (including GAs, Tabu search, sim-
`ulated annealing, artificial neural networks, fuzzy logics), en-
`counter great difficulties when they are applied to real-world
`situations. This is because they use simplified theoretical mod-
`els and are essentially centralized in the sense that all computa-
`tions are carried out in a central computing unit. The intelligent
`agent technologies, on the other hand, suggest an innovative,
`lightweight approach to scheduling problems. This essentially
`distributed approach is more flexible, efficient, and adaptable to
`real-world dynamic manufacturing environments.
`
`B. Agent-Based Approaches
`
`Within the past decade, a number of researchers have applied
`agent technology in attempts to resolve scheduling problems.
`Applications include manufacturing flow shop scheduling [18],
`[113] and job shop scheduling [49], [59], [60], transportation
`scheduling [27], power distribution scheduling [44], computing
`resource scheduling [31], meeting scheduling [100], medical
`test scheduling [38], and project management [54], [127]. An
`
`extensive bibliography on multiagent scheduling in manufac-
`turing systems is compiled by Schiegg [88].
`Agent-based approaches have several potential advantages
`for distributed manufacturing scheduling [95].
`a) These approaches use parallel computation through a large
`number of processors, which may provide scheduling sys-
`tems with high efficiency and robustness.
`b) They can facilitate the integration of manufacturing pro-
`cess planning and scheduling.
`c) They make it possible for individual resources to trade off
`local performance to improve global performance, leading
`to cooperative scheduling.
`d) Resource agents may be connected directly to physical
`devices they represented for so as to realize real-time dy-
`namic rescheduling (of course, not immediate reschedul-
`ing after any change in the working environment for the
`sake of system stability). It may therefore provide the man-
`ufacturing system with higher reliability and device fault
`tolerance.
`e) Schedules are achieved by using mechanisms similar to
`those being used in manufacturing supply chains (i.e.,
`negotiation rather than search). In this way, the manufac-
`turing capabilities of manufacturers can be directly con-
`nected to each other and optimization is possible at the
`supply chain level, in addition to the shop floor level and
`the enterprise level.
`f) Other techniques may be adopted at certain levels for
`decision-making, e.g., simulated annealing [48] and GAs
`[33], [96].
`
`C. Research Literature on Agent-Based
`Manufacturing Scheduling
`
`Research in agent-based manufacturing scheduling has been
`more active and has a richer literature base than that in agent-
`based manufacturing process planning. This section provides a
`detailed review in a structured way.
`1) Earlier Attempts: Shaw may be the first person who pro-
`posed using agents in manufacturing scheduling and factory
`control. He suggested that a manufacturing cell could subcon-
`tract work to other cells through a bidding mechanism [89], [90].
`Yet Another Manufacturing System (YAMS) [80] is another ex-
`ample of an early agent-based manufacturing system, wherein
`each factory and factory component is represented as an agent.
`Each individual agent has a collection of plans as well as knowl-
`edge about its own capabilities. The Contact Net protocol [104]
`is used for interagent negotiation.
`2) Methodologies and Techniques: Different methodologies
`and techniques have been proposed, developed, and used in the
`literature for agent-based manufacturing scheduling.
`a) CORTES [84], [111] uses micro-opportunistic techniques
`for solving the scheduling problem through a two-agent
`system, where each agent is responsible for scheduling a
`set of jobs and for monitoring a set of resources.
`b) Baker [6] proposed a market-driven contract net for heter-
`archical agent-based scheduling. This agent architecture
`performs a type of forward/backward scheduling.
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1013, IPR2022-00681, Pg. 4
`
`

`

`SHEN et al.: AGENT-BASED DISTRIBUTED MANUFACTURING PROCESS PLANNING AND SCHEDULING
`
`567
`
`c) Logistics Management System (LMS) [28] applies inte-
`gration decision technologies to dispatch-scheduling in
`semiconductor manufacturing. It uses functional agents,
`one for each production constraint, and a judge agent to
`combine the votes of all the perspectives. Each agent par-
`tially models those aspects of the environment that are
`needed to satisfy its objective. Its uniqueness is a voting
`protocol for communication among agents.
`d) Liu and Sycara [59] proposed a coordination mecha-
`nism called Constraint Partition and Coordinated Reac-
`tion (CP&CR) for job shop constraint satisfaction. This
`system assigns each resource to a resource agent respon-
`sible for enforcing capacity constraints on the resource,
`and each job to a job agent responsible for enforcing
`temporal precedence and release-date constraints within
`each job. Moreover, a coordination mechanism called An-
`chor&Ascend is proposed for distributed constraint op-
`timization. Anchor&Ascend employs an anchor agent to
`conduct local optimization of its subsolution and inter-
`acts with other agents that perform constraint satisfaction
`through CP&CR to achieve global optimization [60].
`e) In AARIA [79], the manufacturing capabilities (e.g., peo-
`ple, machines, and parts) are encapsulated as autonomous
`agents. Each agent seamlessly interoperates with other
`agents in and outside the factory boundary. AARIA
`used a mixture of heuristic scheduling techniques: for-
`ward/backward scheduling, simulation scheduling, and
`intelligent scheduling. Scheduling is performed by job,
`resource, and operation.
`f) Miyashita [68] proposed an integrated architecture for dis-
`tributed planning and scheduling using the repair-based
`methodology together with the constraint-based mecha-
`nism of dynamic coalition formation among agents. A
`prototype system called CAMPS is implemented, in which
`a set of intelligent agents try to coordinate their actions for
`satisfying planning/scheduling results by handling several
`intra- and interagent constraints.
`g) Usher [116] presented an experimental approach for per-
`formance analysis of a multiagent system for job routing
`in job-shop settings: i) under various information levels for
`constructing and evaluating bids, and ii) under actual real-
`time process data for the negotiation process. Some simple
`but practical mechanisms are proposed and implemented.
`h) Lu and Yih [61] proposed a framework that utilizes au-
`tonomous agents and weighted functions for distributed
`decision-making in elevator manufacturing and assem-
`bly. This system dynamically adjusts the priorities of sub-
`assemblies in the queue buffer of a cell by considering the
`real-time status of all subassemblies in the same order.
`i) In [4], an agent-based scheduling system, incorporating
`game theoretic based agent cooperation, is presented to
`solve the n-job three-stage flexible flow shop scheduling
`problem. With scheduling task represented by a series of
`digraphs, MIP (mixed integer programming, minimizing
`makespan) is used by individual agents to schedule their
`jobs, and the final solution is reached by agent cooperation
`using game theory.
`
`3) Approaches and Architectures: To satisfy the require-
`ments for next-generation manufacturing systems, researchers
`have proposed and developed a number of approaches and archi-
`tectures for agent-based manufacturing scheduling and control.
`a) Burke and Prosser [10] described a distributed asyn-
`chronous scheduling (DAS) system. The DAS architec-
`ture consists of three types of entities: knowledge re-
`sources, agents, and a constraint maintenance system. The
`agents were originally developed as a multiagent heterar-
`chy to represent only resources (O-agents). The final de-
`velopment includes agents for aggregations of resources
`(T-agents) and an agent for overseeing the whole schedul-
`ing process (S-agent). This final scheduling system orga-
`nizes agents into a hierarchical architecture, in which the
`S-agent assigns operations to the T-agents and the T-agents
`assign these operations further to O-agents, respectively.
`While DAS is able to make a correct schedule, however,
`it has no method for optimizing that schedule.
`b) Scheduling in architecture for distributed dynamic manu-
`facturing scheduling (ADDYMS) is decomposed into two
`levels [12]: the first level involves the assignment of a
`manufacturing work cell to a task, and the second consists
`of the determination of a local resource as well as other
`aspects, such as workers and tools, which may possibly be
`shared among a number of work cells. Corresponding to
`these two levels, there are two kinds of agents: site agents
`and resource agents. The system is composed of several
`connected site agents, each of which is in turn connected
`with its subsite agents and some local resource agents.
`c) Lin and Solberg [58] showed how a market-like control
`model could be used for adaptive resource allocation and
`distributed scheduling. They modeled the manufacturing
`shop floor exactly like a market place, where each task
`agent enters the market carrying certain “currency” and
`bargains with each resource agent on which it can be
`proposed. At the same time, each resource agent com-
`petes with other agents to get a more “valuable” job. The
`market mechanism, using multiple-way and multiple-step
`negotiation, is incorporated to coordinate different agents,
`including part agents, resource agents, database agents,
`and communication agents.
`d) Interrante and Rochowiak [43] proposed using active
`scheduling in the development of a multiagent architecture
`for dynamic manufacturing scheduling.
`e) Murthy et al. [72] described an agent-based scheduling
`system based on the A-team architecture, in which func-
`tional agents generate, evaluate, improve, and prune a pool
`of candidate solutions. This system can be considered to
`be a blackboard system.
`f) Kouiss et al. [49] proposed a multiagent architecture for
`dynamic job shop scheduling. Each agent represents a
`work center and performs a local dynamic scheduling by
`applying an adaptive dispatching rule. Depending on local
`and global considerations, a new selection of dispatching
`rule is carried out when a predefined event occurs. The
`selection method is improved through the optimization of
`the thresholds used to detect symptoms (events). Agents
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1013, IPR2022-00681, Pg. 5
`
`

`

`568
`
`IEEE TRANSACTIONS ON SYSTEMS, MAN, AND CYBERNETICS—PART C: APPLICATIONS AND REVIEWS, VOL. 36, NO. 4, JULY 2006
`
`can also coordinate their actions to perform a global dy-
`namic scheduling. However, a global agent is needed to
`detect the symptom of the shop floor.
`g) Sousa and Ramos [106] proposed a dynamic scheduling
`system architecture composed of the holons representing
`tasks together with the holons representing manufacturing
`resources. The Contract Net protocol is adapted to handle
`temporal constraints and deal with conflicts. Sousa et al.
`[107] further proposed an extended Contract Net Protocol
`with constraints propagation for explicit representation of
`the precedence relationships between the operations of a
`task (with a cooperation phase between service providers).
`It shows some novelty compared with other variants of the
`Contract Net Protocol.
`h) van Brussel et al. [117] proposed t