Method and apparatus for scheduling based on state estimation uncertainties

• US 6,738,682 B1
• Filed: 07/31/2002
• Issued: 05/18/2004
• Est. Priority Date: 09/13/2001
• Status: Expired due to Term

• Current Assignee: Globalfoundries US Incorporated (GlobalFoundries, Inc.)
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Pasadyn, Alexander J.
• Primary Examiner(s): Picard, Leo
• Assistant Examiner(s): RODRIGUEZ, PAUL L
• Application Number:
  US10/210,753
• Time in Patent Office: 657 Days
• Field of Search: 700/28-30, 700/44, 700/51, 700/52, 700/96, 700/97, 700/103, 700/100, 705/8, 705/9, 706/48
• US Class Current: 700/100
• CPC Class Codes: G05B 13/04 involving the use of models or simulators
• CPC Class Codes: G05B 19/41865 characterised by job scheduling, process planning, material flow
• CPC Class Codes: G05B 2219/32297 Adaptive scheduling, feedback of actual proces progress to adapt schedule
• CPC Class Codes: G06Q 10/06311 Scheduling, planning or task assignment for a person or group
• CPC Class Codes: Y02P 80/10 Efficient use of energy, e.g. using compressed air or pressurized fluid as energy carrier
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]

Abstract

A method for scheduling activities in a manufacturing system includes defining a plurality of observed states associated with the manufacturing system. State estimates are generated for the observed states. Uncertainty values for the state estimates are generated. A plurality of candidate schedules for performing activities in the manufacturing system is identified. Changes to the uncertainty values are predicted based on the candidate schedules. One of the candidate schedules is selected based on the predicted changes to the uncertainty values.

Claims

1. A method for scheduling activities in a manufacturing system, comprising:

defining a plurality of observed states associated with the manufacturing system;

generating state estimates for the observed slates;

generating uncertainty values for the state estimates;

identifying a plurality of candidate schedules for performing activities in the manufacturing system;

predicting changes to the uncertainty values based on the candidate schedules; and

selecting one of the candidate schedules based on the predicted changes to the uncertainty values.

2. The method of claim 1, further comprising generating a state estimate matrix including the state estimates.

3. The method of claim 2, further comprising generating a covariance matrix associated with the state estimate matrix for each of the candidate schedules, the covariance matrix including the uncertainty values.

4. The method of claim 3, Wherein each candidate schedule includes a plurality of steps and selecting one of the candidate schedules based on the predicted uncertainty values further comprises:

calculating a trace value of the covariance matrix associated with each of the candidate schedules for each step in the candidate schedule;

determining an average trace value for each candidate schedule based on the trace values for the steps in the candidate schedule; and

selecting the candidate schedule having the lowest average trace value.

5. The method of claim of claim 3, wherein generating the covariance matrix further comprises generating the covariance matrix including the uncertainty values as diagonal terms.

6. The method of claim of claim 4, wherein generating the covariance matrix further comprises generating the covariance matrix including off-diagonal terns defining interdependency relationships amongst the observed states.

7. The method of claim 1, wherein identifying the plurality of candidate schedules further comprises:

scheduling a plurality of processing activities; and

scheduling a plurality of metrology activities associated with a subset of the processing activities, each candidate schedule having a different subset of the processing activities.

8. The method of claim 1, wherein identifying the plurality of candidate schedules further comprises scheduling a plurality of processing activities, each candidate schedule having a different order for the processing activities.

9. The method of claim 1, wherein identifying the plurality of candidate schedules further comprises:

identifying a plurality of processing activities;

identifying a plurality of process tools capable of performing the processing activities; and

generating each candidate schedule having different process tools selected for performing the processing activities.

10. The method of claim 1, further comprising;

generating an uncertainty metric associated with each of the candidate schedules based on the predicted changes to the uncertainty values; and

selecting the candidate schedule having the lowest uncertainty metric.

11. The method of claim 10, wherein each candidate schedule includes a plurality of steps and generating the uncertainty metric further comprises:

generating a covariance matrix associated with the state vector for each of the candidate schedules for each of the steps, the covariance matrix including the uncertainty values;

calculating a trace value of the covariance matrix associated with each of the candidate schedules for each step in the candidate schedule; and

determining an average trace value for each candidate schedule based on the trace values for the steps in the candidate schedule to generate the uncertainty metric.

12. The method of claim 1, wherein each candidate schedule includes a priority process activity, and selecting one of the candidate schedules based on the predicted changes to the uncertainty values further comprises selecting the one of the candidate schedules having the lowest uncertainty while performing the priority process activity.

13. A method for scheduling activities in a manufacturing system, comprising:

defining a plurality of observed states associated with the manufacturing system;

generating state estimates for the observed states;

generating uncertainty values for the state estimates;

identifying a plurality of candidate process activities in the manufacturing system;

predicting changes to the uncertainty values based on processing each of the candidate process activities first; and

selecting one of the candidate process activities for processing first based on the predicted uncertainty values.

14. The method of claim 13, further comprising:

removing the candidate process activity selected for first processing from the plurality of candidate process activities;

predicting changes to the uncertainty values based on processing each of the remaining candidate process activities second; and

selecting one of the remaining candidate process activities for processing second based on the predicted uncertainty values.

15. The method of claim 14, further comprising iteratively performing the removing, predicting, and selecting steps until a processing order is selected for each of the processing activities.

16. A method for scheduling activities in a manufacturing system, comprising:

defining a plurality of observed states associated with the manufacturing system;

generating state estimates for the observed states;

generating uncertainty values for the state estimates;

identifying a plurality of candidate process tools capable of performing a selected process activity;

predicting changes to the uncertainty values based on performing the selected process activity on each of the candidate process tools; and

selecting one of the candidate process tools for performing the selected process activity based on the predicted uncertainty values.

17. A system for scheduling activities in a manufacturing system, comprising:

a process controller configured to define a plurality of observed states associated with the manufacturing system, generate state estimates for the observed states, and generate uncertainty values for the state estimates; and

a scheduling controller configured to identity a plurality of candidate schedules for performing activities in the manufacturing system, predict changes to the uncertainty values based on the candidate schedules, and select one of the candidate schedules based on the predicted changes to the uncertainty values.

18. The system of claim 17, wherein the process controller is further configured to generate a state estimate matrix including the state estimates.

19. The system of claim 18, wherein the process controller is further configured to generate a covariance matrix associated with the state estimate matrix for each of the candidate schedule, the covariance matrix including the uncertainty values.

20. The system of claim 19, wherein each candidate schedule includes a plurality of steps and the scheduling controller is further configured to calculate a trace value of the covariance matrix associated with each of the candidate schedules for each step in the candidate schedule, determine an average trace value for each candidate schedule based on the trace values for the steps in the candidate schedule, and select the candidate schedule having the lowest average trace value.

21. The system of claim of claim 19, wherein the scheduling controller is further configured to generate the covariance matrix including the uncertainty values as diagonal terms.

22. The system of claim of claim 20, wherein the scheduling controller is further configured to generate the covariance matrix including off-diagonal terms defining interdependency relationships amongst the observed states.

23. The system of claim 17, wherein the scheduling controller is further configured to schedule a plurality of processing activities and schedule a plurality of metrology activities associated with a subset of the processing activities, each candidate schedule having a different subset of the processing activities.

24. The system of claim 17, wherein the scheduling controller is further configured to schedule a plurality of processing activities, each candidate schedule having a different order for the processing activities.

25. The system of claim 17, wherein the scheduling controller is further configured to identify a plurality of processing activities, identify a plurality of process tools capable of performing the processing activities, and generate each candidate schedule having different process tools selected for performing the processing activities.

26. The system of claim 17, wherein the scheduling controller is further configured to generate an uncertainty metric associated with each of the candidate schedules based on the predicted changes to the uncertainty values and select the candidate schedule having the lowest uncertainty metric.

27. The system of claim 26, wherein each candidate schedule includes a plurality of steps, and the scheduling controller is further configured to generate a covariance matrix associated with the state estimate matrix for each of the candidate schedules for each of the steps, the covariance matrix including the uncertainty values, calculate a trace value of the covariance matrix associated with each of the candidate schedules for each step in the candidate, schedule, and determine an average trace value for each candidate schedule based on the trace values for the steps in the candidate schedule to generate the uncertainty metric.

28. The system of claim 17, wherein each candidate schedule includes a priority process activity, and the scheduling controller is further configured to select the one of the candidate schedules having the lowest uncertainty while performing the priority process activity.

29. The system of claim 17, wherein the process controller and the scheduling controller are integrated into a single unit.

30. A system for scheduling activities in a manufacturing system, comprising:

a process controller configured to define a plurality of observed states associated with the manufacturing system, generate state estimates for the observed slates, and generate uncertainty values for the state estimates; and

a scheduling controller configured to identify a plurality of candidate process activities in the manufacturing system, predict changes to the uncertainty values based on processing each of the candidate process activities first, and select one of the candidate process activities for processing first based on the predicted uncertainty values.

31. The system of claim 30, the scheduling controller is further configured to remove the candidate process activity selected for first processing from the plurality of candidate process activities, predict changes to the uncertainty values based on processing each of the remaining candidate process activities second, and select one of the remaining candidate process activities for processing second based on the predicted uncertainty values.

32. The system of claim 31, the scheduling controller is further configured to iteratively performing the removing, predicting, and selecting steps until a processing order is selected for each of the processing activities.

33. The system of claim 30, wherein the process controller and the scheduling controller are integrated into a single unit.

34. A system for scheduling activities in a manufacturing system, comprising:

a process controller configured to define a plurality of observed states associated with the manufacturing system, generate state estimates for the observed states, and generate uncertainty values for the state estimates; and

a scheduling controller configured to identify a plurality of candidate process tools capable of performing a selected process activity, predict changes to the uncertainty values based on performing the selected process activity on each of the candidate process tools, and select one of the candidate process tools for performing the selected process activity based on the predicted uncertainty values.

35. The system of claim 34, wherein the process controller and the scheduling controller are Integrated into a single unit.

36. A system for scheduling activities in a manufacturing system, comprising:

means for defining a plurality of observed states associated with the manufacturing system;

means for generating state estimates for the observed states;

means for generating uncertainty values for the state estimates;

means for identifying a plurality of candidate schedules for performing activities in the manufacturing system;

means for predicting changes to the uncertainty values based on the candidate schedules; and

means for selecting one of the candidate schedules based on the predicted changes to the uncertainty values.