Computers in Industry 46 (2001) 189±207
`
`A dynamic reactive scheduling mechanism for responding to
`changes of production orders and manufacturing resources
`
`J. Sun, D. Xue*
`Department of Mechanical and Manufacturing Engineering, University of Calgary, Calgary, Alberta, Canada T2N 1N4
`
`Received 24 July 2000; accepted 13 March 2001
`
`Abstract
`
`This research introduces a dynamic reactive production scheduling mechanism for modifying the originally created
`schedules when these schedules cannot be completed due to changes of production orders and manufacturing resources.
`Production order changes include removal of an order that is canceled by a customer and insertion of an order that has to be
`completed within a short period of time. Manufacturing resource changes include breakdowns of machines and sudden
`sickness of workers. Match-up and agent-based collaboration approaches are employed to modify only part of the originally
`created schedules for improving the reactive scheduling ef®ciency, while maintaining the scheduling quality. The dynamic
`reactive production scheduling system was implemented using Smalltalk, an object oriented programming language.
`# 2001 Elsevier Science B.V. All rights reserved.
`
`Keywords: Reactive scheduling; Predictive scheduling; Match-up approach; Multi-agents; Arti®cial intelligence
`
`1. Introduction
`
`Production scheduling aims at allocating available
`manufacturing resources for the required manufactur-
`ing tasks and identifying the sequence and timing
`parameter values to accomplish these tasks. Typical
`manufacturing resources include facilities, persons,
`materials, and so on. Competitiveness of products
`can be improved by identifying the optimal production
`schedule that needs the minimum production efforts.
`The research on production scheduling was started
`by developing algorithms for generating the optimal
`sequence to complete the required tasks considering
`either only one processor (machine) or multiple pro-
`cessors (machines) [1]. In each of these scheduling
`
`* Corresponding author. Tel.: ‡1-403-220-4168;
`fax: ‡1-403-282-8406.
`E-mail address: xue@enme.ucalgary.ca (D. Xue).
`
`methods, an objective function, such as the minimum
`total make-span to complete all the selected tasks, or
`the minimum mean ¯ow of these selected tasks, is
`selected for identifying the optimal schedule.
`Most of the earlier developed scheduling methods
`have dif®culty for solving actual industrial problems,
`due to the complexity of real-life manufacturing con-
`straints. First, the industrial scheduling problems are
`dynamic in nature, i.e. new orders are received con-
`tinuously during the production process. Second, the
`created schedule may be changed to re¯ect
`the
`changes of production orders and manufacturing con-
`ditions during production process. Production order
`changes include removal of an order that is canceled
`by a customer and insertion of an order that has to be
`completed within a short period of time. Manufactur-
`ing condition changes include disturbance events of
`resources such as breakdowns of machines and sick-
`ness of workers.
`
`0166-3615/01/$ ± see front matter # 2001 Elsevier Science B.V. All rights reserved.
`PII: S 0 1 6 6 - 3 6 1 5 ( 0 1 ) 0 0 1 1 9 - 1
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1016, IPR2022-00681, Pg. 1
`
`

`

`190
`
`J. Sun, D. Xue / Computers in Industry 46 (2001) 189±207
`
`With the advances in computer technologies, many
`new methods and systems considering industrial con-
`straints were developed for two different types of
`production scheduling: predictive scheduling and
`reactive scheduling [2,3]. Predictive scheduling cre-
`ates the optimal schedule based on given requirements
`and constraints prior to the production process. Most
`of the scheduling algorithms and systems were devel-
`oped for predictive scheduling. Reactive scheduling,
`on the other hand, is a process to modify the created
`schedule during the manufacturing process to adapt
`changes in production environment. Reactive schedul-
`ing is also called rescheduling.
`The intelligent system approaches have been proved
`effective for conducting both predictive scheduling and
`reactive scheduling [2,4,5]. For predictive scheduling,
`generally intelligent approaches aim at identifying the
`optimal schedule through iterative search process. For
`reactive scheduling, most approaches attempt to revise
`only part of the originally created schedule for respond-
`ing to the production environment changes without
`rescheduling all the required tasks [6±9]. Because a
`large number of tasks are usually considered in pre-
`dictive scheduling and reactive scheduling, the optimal
`schedules created using these developed methods are
`not the true global optimal schedules. Quality of sche-
`duling result can be improved by employing stochastic
`computing methods, such as genetic algorithm and
`simulated annealing, to prevent the result from falling
`into the local optimal points [2].
`Despite the progress, many problems have to be
`solved for predictive scheduling and reactive schedul-
`ing. These problems are summarized as follows.
`
`1. In the presently developed scheduling systems,
`manufacturing requirements are usually modeled
`directly based upon customer requirements. The
`manufacturing requirements, together with manu-
`facturing resource descriptions, are used as
`constraints for production scheduling. Product
`design descriptions and constraints, however, are
`not considered in these systems. Because many
`new designs are created using existing modules as
`their components, modeling of the manufacturing
`requirements of these component modules and
`identi®cation of the manufacturing tasks of these
`designs by considering constraints among these
`components are required.
`
`2. The production scheduling mechanisms in these
`systems were primarily developed based on
`centralized computing architecture, in which all
`the knowledge bases and databases were modeled
`at the same location. This control architecture has
`dif®culty in handling complex manufacturing
`systems that require knowledge and data to be
`distributed at different locations. Therefore, devel-
`opment of distributed production scheduling
`systems is required.
`
`In our previous research, an intelligent predictive
`scheduling system has been developed to solve these
`two problems [10,11]. In this system, product descrip-
`tions and design constraints are represented using a
`feature-based modeling approach. Manufacturing
`requirements for producing the products, including
`tasks and sequential constraints for accomplishing
`these tasks, are represented as part of the product
`feature descriptions. Manufacturing resources, includ-
`ing facilities and persons, are modeled as distributed
`agents that are coordinated by two mediators. The
`optimal production schedule and its timing parameter
`values are identi®ed using constraint-based search and
`agent-based collaboration approaches. This project
`was initiated from the requirements of a building
`product manufacturing company Ð Gienow Building
`Products Ltd., where production tasks are created from
`customer orders.
`The research presented in this paper is a further
`development of this intelligent production scheduling
`system by introducing a reactive scheduling mechan-
`ism for responding to changes of production orders
`and manufacturing resources. Changes of production
`orders include cancellation of previously scheduled
`orders and insertion of urgent orders. Changes of
`manufacturing resource conditions include break-
`downs of machines and sickness of persons. Match-
`up and agent-based collaboration approaches are
`employed for rescheduling the tasks and identifying
`the optimal timing parameter values of these tasks, for
`improving the scheduling ef®ciency while maintain-
`ing the scheduling quality.
`The remaining of this paper is organized as follows.
`Section 2 introduces the previously developed pre-
`dictive scheduling mechanism. Section 3 proposes the
`architecture of the intelligent production scheduling
`system that supports both the predictive scheduling
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1016, IPR2022-00681, Pg. 2
`
`

`

`J. Sun, D. Xue / Computers in Industry 46 (2001) 189±207
`
`191
`
`function and the reactive scheduling function. Section
`4 presents the reactive scheduling algorithms and
`examples for responding to changes of orders and
`resources. Section 5 gives a number of case study
`examples to show the effectiveness of the introduced
`approach. Section 6 summarizes this research.
`
`2. Review of a previously developed predictive
`scheduling mechanism
`
`The previously developed predictive scheduling
`mechanism is composed of three sub-systems: product
`modeling sub-system, resource management sub-sys-
`tem, and scheduling sub-system.
`
`2.1. Product modeling sub-system
`
`In the product modeling sub-system, a product is
`modeled by primitives called features [12,13]. Fea-
`tures are described at two different levels, class level
`and instance level, corresponding to standard product
`libraries and special product data,
`respectively.
`Instance features are generated using class features
`as their templates. A feature is composed of element
`features, attributes, qualitative relations among fea-
`
`tures, and quantitative relations among attributes. For
`instance, Fig. 1 shows a product modeled by three
`instance features. The top-level instance feature, c, is
`generated from a class feature WindowCenter
`that is composed of two element features: ?Left
`and ?Right. When the class feature, Window-
`Center, is used to generate its instance feature, c,
`the two element features are also generated as instance
`features, cl and cr, respectively.
`The manufacturing requirements for producing
`each feature are de®ned by a graph of tasks, represent-
`ing the sequential constraints to accomplish these
`tasks. For instance, the right component, cr, shown
`in Fig. 1 can be produced by six tasks, including
`cutting, C, framing, F, assemblies, A1, A2, and
`A3, and glazing, G. A task in an instance feature is
`carried out in production only when all the tasks in this
`feature's element features have been completed. Each
`task is de®ned by its type, requirements of resources
`including facilities and persons, and time period to
`carry out this process.
`
`2.2. Resource management sub-system
`
`In the resource management sub-system, the faci-
`lity resources and person resources are modeled as
`
`Fig. 1. Feature-based product and manufacturing requirement representation.
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1016, IPR2022-00681, Pg. 3
`
`

`

`192
`
`J. Sun, D. Xue / Computers in Industry 46 (2001) 189±207
`
`agents, which are coordinated by a facility mediator
`and a personnel mediator during the predictive sche-
`duling process. The idea to model resources using
`agents comes from the distributed modeling approach
`for improving ¯exibility of manufacturing systems
`[14±19]. A facility resource agent is de®ned by its
`type, manufacturing functions, and time constraints
`including available periods and unavailable periods. A
`person resource agent is de®ned by the facilities that
`the person is responsible for, and time constraints
`including available periods, regular schedule, and
`unavailable periods.
`
`2.3. Scheduling sub-system
`
`The scheduling sub-system aims at identifying the
`optimal schedule for the orders received from custo-
`mers. When an order is received, an order agent is then
`created to represent the customer requirements. The
`order agents negotiate with the resource agents using
`the corresponding design constraints and manufactur-
`ing requirements, which are preserved in the instance
`
`features, to identify the optimal production schedule.
`Constraint-based search and agent-based collabora-
`tion approaches are employed for identifying the
`optimal schedule, as shown in Fig. 2.
`
`2.3.1. Constraint-based search
`The optimal sequence of tasks for a customer order
`is identi®ed using best-®rst search [20], as shown in
`Fig. 2. Each node in the search tree represents a partial
`schedule developed so far. A start node describes an
`empty schedule, while a goal node describes the
`schedule in which all the tasks of the customer order
`have been allocated with required resources and tim-
`ing parameter values. In predictive scheduling, each
`time the best node is selected for generating its sub-
`nodes. When a sub-node is generated, an unscheduled
`task is then selected for resource allocation and timing
`parameter value instantiation through collaboration
`among relevant agents. Evaluation to this node is
`conducted using a heuristic function. This process
`is conducted continuously until the selected best-node
`is the goal node. The scheduling results are described
`
`Fig. 2. Predictive scheduling using constraint-based search and agent-based collaboration.
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1016, IPR2022-00681, Pg. 4
`
`

`

`J. Sun, D. Xue / Computers in Industry 46 (2001) 189±207
`
`193
`
`by sequences of tasks that are preserved in order
`agents and resource agents, as shown in Fig. 2. In
`predictive scheduling, the created schedule should
`satisfy the following temporal constraints: (1) a task
`in an instance feature can be carried out in production
`only when all
`the tasks in this feature's element
`features have been completed. (2) A task can be
`carried out only when all its ancestor tasks have been
`completed.
`Two heuristic functions have been developed in this
`research: (1) Fmax Ð the latest task ®nish time con-
`sidering all the scheduled tasks of an order and (2) Smin
`Ð the earliest task start time considering all the
`scheduled tasks of an order. Two search strategies
`for predictive scheduling have also been developed
`based upon the two heuristic functions: (1) earliest-
`delivery-time-based scheduling strategy Ð to provide
`the product to the customer as early as possible by
`selecting the node with the minimum value of the Fmax
`as the best node, and (2) due-time-based scheduling
`strategy Ð to start the product manufacturing as late
`as possible to reduce the space for storing the pro-
`duced product by selecting the node with the max-
`imum value of the Smin as the best node.
`
`2.3.2. Agent-based collaboration
`Allocation of
`resources and instantiation of
`timing parameter values for the required tasks are
`
`conducted based upon agent-based collaboration
`using the contract net protocol [21]. Two timing
`parameters of tasks, start time and ®nish time, are
`considered in scheduling. The agent-based collabora-
`tion in predictive scheduling is conducted at two
`different
`levels: order-facility collaboration level
`and facility-person collaboration level, as shown in
`Fig. 2. When the facility mediator receives a to-
`be-scheduled task from the order agent, this mediator
`sends messages to all the relevant facility agents it
`knows. Each facility agent then starts negotiation with
`the relevant person agents through the personnel
`mediator and sends a bid (with the proposed start
`time, ®nish time, and person) to the facility mediator.
`The facility mediator selects the facility that provides
`the best bid, such as the one with the earliest product
`manufacturing completion time for
`the earliest-
`delivery-time-based scheduling, or the one with the
`latest product manufacturing releasing time for the
`due-time-based scheduling.
`
`3. Architecture of an intelligent production
`scheduling system
`
`The dynamic reactive scheduling mechanism
`introduced in this research was developed as a
`
`Fig. 3. Architecture of the intelligent production scheduling system.
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1016, IPR2022-00681, Pg. 5
`
`

`

`194
`
`J. Sun, D. Xue / Computers in Industry 46 (2001) 189±207
`
`function block added to the scheduling module
`of the previously developed intelligent production
`scheduling system. Architecture of the whole intelli-
`gent production scheduling system with both predic-
`tive scheduling function and reactive scheduling
`function is shown in Fig. 3. The system is composed
`of three sub-systems: product modeling sub-system,
`resource management sub-system, and scheduling
`sub-system.
`Predictive scheduling is conducted to allocate
`resources and their timing parameter values for pro-
`ducing the products ordered by customers prior to the
`production process. Reactive scheduling, on the other
`hand, is conducted to modify the created schedule for
`responding to the changes of customer orders (such as
`cancellation of orders or insertion of urgent orders)
`and manufacturing conditions (such as machine break-
`downs and persons' sudden sickness) during the pro-
`duction process.
`The intelligent predictive/reactive production sche-
`duling system was implemented using Smalltalk, an
`object oriented programming language [22]. Smalltalk
`was used due to its good user interface environment
`and large class library. Details of the developed
`dynamic reactive scheduling mechanism will be
`described in the next section.
`
`4. A dynamic reactive scheduling mechanism
`
`In this research, two reactive scheduling algorithms
`have been developed for responding to the changes of
`customer orders and manufacturing resource condi-
`tions, respectively, by partially modifying the origin-
`ally created schedule. Changes of customer orders
`include cancellation of scheduled orders and insertion
`of urgent orders. Changes of manufacturing resource
`conditions include breakdowns of machines and sud-
`den sickness of persons.
`In both algorithms, the previously scheduled tasks
`are modi®ed. The objective of this research is to
`develop a reactive scheduling method to minimize
`the schedule changes for improving the ef®ciency of
`reactive scheduling, while maintaining the quality of
`reactive scheduling. Since the revised schedule can
`maximally match up with the original schedule, this
`reactive scheduling approach is also called a match-up
`reactive scheduling approach.
`
`4.1. Reactive scheduling for customer
`order changes
`
`Changes of customer orders are of two cases: (1)
`cancellation of scheduled orders and (2) insertion of
`urgent orders. When a previously scheduled order is
`canceled by its customer, all the resource time slots
`assigned to the tasks of this order should be released.
`To improve the quality of the overall schedule con-
`sidering all
`the other ordered products,
`the tasks
`scheduled using the due-time-based scheduling strat-
`egy could be moved forward towards their due-time
`measures, while the tasks scheduled using the earliest-
`delivery-time-based scheduling strategy could be
`moved backward towards their ordering time mea-
`sures. When a feasible schedule cannot be identi®ed
`for an order using the predictive scheduling strategy
`due to its urgent due-time requirement, some of the
`previously scheduled tasks can be temporarily released
`for inserting the tasks in the urgent order to the
`schedule. The released tasks should be rescheduled
`to satisfy the product and manufacturing constraints.
`Since one of the objectives in this research is to
`integrate production scheduling with product design,
`when design parameters are changed, the manufactur-
`ing requirements are then updated automatically.
`When these manufacturing requirements cannot be
`satis®ed by the currently created schedule, change of
`the production schedule can be conducted simply by
`canceling the original order and inserting the modi®ed
`order.
`To minimize the schedule change, while maintain-
`ing the quality of the overall schedule, the following
`rules have been employed in reactive scheduling for
`customer order changes.
`
`1. The customer orders previously scheduled using
`the due-time-based scheduling strategy are re-
`scheduled prior to the revision of the customer
`orders previously scheduled using the earliest-
`delivery-time-based scheduling strategy.
`2. In the revised schedule, the sequence of tasks for
`each to-be-rescheduled order remains the same as
`the sequence in the original schedule to satisfy the
`task precedence constraints and improve the
`rescheduling ef®ciency.
`3. In the revised schedule, each rescheduled task
`is still allocated with the facility resource and
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1016, IPR2022-00681, Pg. 6
`
`

`

`J. Sun, D. Xue / Computers in Industry 46 (2001) 189±207
`
`195
`
`person resource that were originally allocated to
`this task.
`
`Reactive scheduling algorithm responding to cus-
`tomer order changes is formulated as the following
`three steps.
`
`1. Step 1: Initialize for rescheduling.
`Generate a copy of the original schedules that
`are preserved in the resource agents. Consider all
`the orders that have not been manufactured so far
`as the to-be-rescheduled orders and remove their
`original schedules from the resource agents. In
`case of canceling an order, the canceled order
`should not considered in further
`rescheduling
`process. In case of inserting an order, this order
`is scheduled ®rst using the due-time-based pre-
`dictive scheduling approach.
`2. Step 2: Reschedule the to-be-rescheduled orders
`that were previously scheduled using the due-
`time-based scheduling strategy.
`2.1. For these to-be-rescheduled orders, identify
`the to-be-rescheduled tasks from the copy of
`the original schedules. In case of canceling
`an order, the tasks that precede the tasks of
`the canceled order in the original schedules
`should be considered as the to-be-resched-
`uled tasks. In case of inserting an order, the
`tasks whose original schedules are in con¯ict
`with the schedule of the inserted order should
`be considered as the to-be-rescheduled tasks.
`Sort the list of the to-be-rescheduled tasks
`according to the ®nish time values of these
`tasks. The to-be-rescheduled task with the
`largest ®nish time value is placed at
`the
`beginning of the list.
`from the to-be-
`2.2. Select
`the ®rst element
`rescheduled task list as the current to-be-
`rescheduled task. Recover schedules of the
`tasks that are in the to-be-rescheduled orders
`and will start after the ®nish time of the
`current
`to-be-rescheduled task. Reassign
`timing parameter values to the current to-
`be-rescheduled task using agent-based colla-
`boration mechanism. The current
`to-be-
`rescheduled task should be removed from
`the list of the to-be-rescheduled tasks.
`2.3. Check if the reassigned timing parameter
`values are the same as those in the copy of the
`
`original schedules. If they are not the same,
`the following tasks belonging to the to-be-
`rescheduled orders should be added to the list
`of the to-be-rescheduled tasks: (1) the tasks
`preceding the current to-be-rescheduled task
`in the copy of the original schedules pre-
`served in the relevant facility agent and per-
`son agent that were allocated for the current
`to-be-rescheduled task, (2) the task preceding
`the current to-be-rescheduled task in the task
`sequence of the corresponding customer order,
`and (3) the tasks whose original schedules are
`in con¯ict with the revised schedule for the
`current to-be-rescheduled task.
`2.4. Check if the list of the to-be-rescheduled
`tasks is empty. If the list is not empty, go to
`Step 2 (2.1).
`2.5. Recover all the tasks of the to-be-rescheduled
`orders that are preserved in the copy of the
`original schedules and have not been re-
`scheduled so far in the reactive scheduling
`process.
`3. Step 3: Reschedule the to-be-rescheduled orders
`that were previously scheduled using the earliest-
`delivery-time-based scheduling strategy.
`3.1. For these orders, identify the to-be-resched-
`uled tasks from the copy of the original
`schedules. The tasks whose original sche-
`dules are in con¯ict with the revised
`schedules are considered as the to-be-re-
`scheduled tasks. In case of canceling an
`order, the tasks that follow the tasks of the
`canceled order
`in the original schedules
`should also be considered as the to-be-
`rescheduled tasks. Sort the list of the to-be-
`rescheduled tasks according to the start time
`values of these tasks. The to-be-rescheduled
`task with the smallest start
`time value is
`placed at the beginning of the list.
`3.2. Select the ®rst element from the to-be-resched-
`uled task list as the current to-be-rescheduled
`task. Recover schedules of the tasks that are in
`the to-be-rescheduled orders and will be
`completed before the start time of the current
`to-be-rescheduled task. Reassign timing para-
`meter values to the current to-be-rescheduled
`task using the agent-based collaboration
`mechanism. The current
`to-be-rescheduled
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1016, IPR2022-00681, Pg. 7
`
`

`

`196
`
`J. Sun, D. Xue / Computers in Industry 46 (2001) 189±207
`
`task should be removed from the list of the
`to-be-rescheduled tasks.
`3.3. Check if the reassigned timing parameter
`values are the same as those in the copy of
`the original schedules. If they are not the
`same, the following tasks belonging to the to-
`be-rescheduled orders should be added to the
`list of the to-be-rescheduled tasks: (1) the
`tasks following the current to-be-rescheduled
`task in the copy of the original schedules
`preserved in the relevant facility agent and
`person agent
`that were allocated for
`the
`current to-be-rescheduled task, (2) the task
`following the current to-be-rescheduled task
`in the task sequence of the corresponding
`customer order, and (3) the tasks whose
`original schedules are in con¯ict with the
`revised schedule for
`the current
`to-be-
`rescheduled task.
`3.4. Check if the list of the to-be-rescheduled
`tasks is empty. If the list is not empty, go to
`Step 3 (3.2).
`3.5. Recover all the tasks of the to-be-rescheduled
`orders that are preserved in the copy of the
`original schedules and have not been re-
`scheduled so far in the reactive scheduling
`process.
`
`An example is given in Fig. 4 to illustrate the
`reactive scheduling algorithm for responding to cus-
`tomer order change. In this example, an urgent order E
`needs to be inserted in the original schedule, which is
`shown in Fig. 4a. The orders A and B were scheduled
`using the earliest-delivery-time-based scheduling
`strategy, and the orders C and D were scheduled using
`the
`due-time-based
`scheduling
`strategy. The
`sequences of tasks for the orders A, B, C, and D in
`the original schedule are:
`Order A : A1 ! A2 ! A3
`Order B : B1 ! B2 ! B3 ! B4
`Order C : C1 ! C2 ! C3
`Order D : D1 ! D2 ! D3
`In Step 1, as shown in Fig. 4b, orders A, B, C, and D
`are identi®ed as the to-be-rescheduled orders and
`removed from the original schedule temporally. Then,
`order E is scheduled using the due-time-based sche-
`duling strategy.
`
`In Step 2, as shown in Fig. 4c, the orders C and D
`that were scheduled previously using the due-time-
`based scheduling strategy are rescheduled. The tasks
`D1 and D2 are identi®ed as the to-be-rescheduled
`tasks at the beginning, due to their con¯ict with the
`tasks E1 and E2. Based on the ®nish time values, D2
`is selected as the ®rst current to-be-rescheduled task.
`Task D3 that is to be started after the ®nish time of D2
`is recovered in the revised schedule. Then D2 is
`assigned with new timing parameter values. Since
`the timing parameter values of D2 are changed in
`the revised schedule, two tasks are identi®ed as the
`new to-be-rescheduled tasks: C2 that precedes D2 in
`the original schedule considering facility F2 and D1
`that precedes D2 in the task sequence of the original
`schedule for order D. Only C2 is added to the to-be-
`rescheduled tasks, since D1 has been already identi-
`®ed as a to-be-rescheduled task at the beginning of this
`step. Next, D1 is selected as the current to-be-resched-
`uled task and assigned with new timing parameter
`values. Although the new timing parameter values of
`D1 are different from the original ones, no to-be-
`rescheduled tasks are further identi®ed. Then task C2
`is selected as the current to-be-rescheduled task. Task
`C3 that is to be started after the ®nish time of C2 is
`recovered in the revised schedule. The task C2 is
`rescheduled with the same timing parameter values.
`After task C2 is rescheduled, the to-be-rescheduled
`task list becomes an empty one. Task C1 is recovered
`with its original schedule.
`In Step 3, as shown in Fig. 4d, the orders A and B
`that were scheduled previously using the earliest-
`delivery-time-based scheduling strategy are resched-
`uled. The original schedule of B4 is in con¯ict with
`the revised schedule of D2, thus, B4 is identi®ed as
`the to-be-rescheduled task at the beginning. Next, B4
`is selected as the current to-be-rescheduled task and
`the tasks A1, A2, A3, B1, B2, and B3, whose ®nish
`time values precede the start time of B4 in the original
`schedule, are recovered in the revised schedule. Then,
`B4 is assigned with new timing parameter values.
`Since no additional tasks can be identi®ed as the to-be-
`rescheduled tasks, the reactive scheduling process is
`terminated.
`In this example, among the 13 tasks in the four
`orders, only 3 tasks are revised during the reschedul-
`ing process for responding to the change of customer
`order.
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1016, IPR2022-00681, Pg. 8
`
`

`

`J. Sun, D. Xue / Computers in Industry 46 (2001) 189±207
`
`197
`
`Fig. 4. Reactive scheduling for customer order change.
`
`In the rescheduling process, reassignment of timing
`parameter values to the to-be-rescheduled tasks is
`conducted based upon agent-based collaboration
`among resource agents through coordination of the
`two mediators in the resource management sub-sys-
`tem. Two task timing parameters, start time and ®nish
`time, are considered in this research.
`An example is shown in Fig. 5 to illustrate the
`process of reassigning timing parameter values to a
`to-be-rescheduled task of an order, which was ori-
`ginally scheduled using the earliest-delivery-time-
`based scheduling strategy. During the rescheduling
`process, the current to-be-rescheduled task A needs
`to be reassigned with new timing parameter values.
`
`The resources, facility agent F1 and person agent
`P1, were originally allocated for this task. The ear-
`liest possible start time is Tes that was determined
`based on task precedence constraints and feature
`relations using the previously developed predictive
`scheduling method. First, the facility mediator reas-
`signs this task to the facility agent F1. Upon receiving
`the facility agent F1 identi®es the
`this message,
`related person agent P1 through the personnel med-
`iator. Then the facility agent F1 negotiates with the
`person agent P1 to determine the proper time slot for
`the task A. The time slot should provide the mini-
`mum value of the task start time in the earliest-
`delivery-time-based scheduling, while
`satisfying
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1016, IPR2022-00681, Pg. 9
`
`

`

`198
`
`J. Sun, D. Xue / Computers in Industry 46 (2001) 189±207
`
`Fig. 5. An example of rescheduling timing parameter values through agent-based collaboration.
`
`all the manufacturing requirement and resource con-
`straints.
`
`4.2. Reactive scheduling for manufacturing resource
`changes
`
`Manufacturing resources changes are of two cases:
`(1) facility breakdowns and (2) persons' sudden sick-
`ness. When such a disturbance occurs, the schedules of
`the affected tasks have to be revised. Match-up resche-
`duling approach is also employed to minimize the
`changes to the originally created schedules, while
`satisfying the product and manufacturing constraints.
`The following rules have been used for reactive sche-
`duling to respond to the changes of manufacturing
`resources.
`
`1. The reactive scheduling mechanism ®rst tries to
`move the tasks that are affected directly by the
`resource changes to other
`resources without
`changing the timing parameter values of these
`tasks.
`2. If the alternative resources can not be identi®ed
`for the affected tasks, match-up-based reschedul-
`ing is then conducted. The customer orders
`previously scheduled using the due-time-based
`
`scheduling strategy are rescheduled prior to the
`revision to the customer orders previously sched-
`uled using the earliest-delivery-time-based sche-
`duling strategy.
`3. If some orders, which were previously scheduled
`using the due-time-based scheduling strategy,
`cannot be rescheduled to satisfy the due-time
`constraints due to the changes of
`resource
`conditions,
`the directly affected orders will be
`rescheduled with modi®ed due-time values, after
`all other orders with due-time requirements have
`been rescheduled.
`4. In the revised schedule, the sequence of tasks for
`each to-be-rescheduled order remains the same as
`the sequence in the original schedule to satisfy the
`task precedence constraints while improving the
`rescheduling ef®ciency.
`5. In the revised schedule, if alternative resources
`cannot be identi®ed for the affected tasks, each
`rescheduled task is still allocated with the
`resources that were originally assigned to this
`task for improving the rescheduling ef®ciency.
`
`Reactive scheduling algorithm responding to man-
`ufacturing resource changes is formulated as the
`following ®ve steps.
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1016, IPR2022-00681, Pg. 10
`
`

`

`J. Sun, D. Xue / Computers in Industry 4