Method and apparatus for generating a multi-dimensional cost function

• US 6,904,329 B1
• Filed: 08/30/2002
• Issued: 06/07/2005
• Est. Priority Date: 08/30/2002
• Status: Active Grant

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Li, Yiwei, Parunak, H. Van Dyke, Barto, Larry D., Nettles, Steven C.
• Primary Examiner(s): Von Buhr, Maria N.
• Application Number:
  US10/233,197
• Time in Patent Office: 1,012 Days
• Field of Search: 700 28- 32, 700/36, 700 99-102, 700/106, 700/107, 705 7- 9, 705/35, 705/37
• US Class Current: 700/99
• CPC Class Codes: G05B 19/41865 characterised by job scheduling, process planning, material flow
• CPC Class Codes: G05B 2219/32234 Maintenance planning
• CPC Class Codes: G05B 2219/45031 Manufacturing semiconductor wafers
• CPC Class Codes: G05B 2219/49068 Minimum cost adaptive
• CPC Class Codes: G06Q 30/06 Buying, selling or leasing transactions
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]
• CPC Class Codes: Y02P 90/80 Management or planning

Abstract

A method for generating a cost function for processing a candidate workpiece using a resource includes identifying processing requirements for the candidate workpiece. A first committed capacity of the resource is determined based on a schedule of engagements associated with other workpieces having processing requirements compatible with the processing requirements of the candidate workpiece. A second committed capacity of the resource is determined based on a schedule of engagements associated with other workpieces having processing requirements not compatible with the processing requirements of the candidate workpiece. The cost function is generated based on the first and second committed capacities. A system includes a resource for processing a candidate workpiece and at least one scheduling agent. The scheduling agent is configured to identify processing requirements for the candidate workpiece, determine a first committed capacity of the resource based on a schedule of engagements associated with other workpieces having processing requirements compatible with the processing requirements of the candidate workpiece, determine a second committed capacity of the resource based on a schedule of engagements associated with other workpieces having processing requirements not compatible with the processing requirements of the candidate workpiece, and generate the cost function based on the first and second committed capacities.

Claims

1. A computer-implemented method for generating a cost function for pressing a candidate workpiece using a resource:

identifying processing requirements for the candidate workpiece;

determining a first committed capacity of the resource based on a schedule of engagements associated with other workpieces having processing requirements compatible with the processing requirements of the candidate workpiece;

determining a second committed capacity of the resource based on a schedule of engagements associated with other workpieces having processing requirements not compatible with the processing requirements of the candidate workpiece; and

generating the cost function based on the first and second committed capacities.

2. The computer-implemented method of claim 1, further comprising:

identifying a commitment window for processing the workpiece; and

generating a cost for processing the workpiece based on the cost function and the commitment window.

3. The computer-implemented method of claim 1, wherein the processing requirements of the candidate workpiece include batch requirements, determining the first committed capacity further comprises determining the first committed capacity based on the schedule of engagements associated with other workpieces having batch requirements compatible with the batch requirements of the candidate workpiece, and determining the second committed capacity further comprises determining the second committed capacity of the resource based on the schedule of engagements associated with other workpieces having batch requirements not compatible with the batch requirements of the candidate workpiece.

4. The computer implemented method of claim 1, wherein the processing requirements of the candidate workpiece include setup requirements, determining the first committed capacity further comprises determining the first committed capacity based on the schedule of engagements associated with other workpieces having setup requirements compatible with the setup requirements of the candidate workpiece, and determining the second committed capacity further comprises determining the second committed capacity of the resource based on the schedule of engagements associated with other workpieces having setup requirements not compatible with the setup requirements of the candidate workpiece.

5. The computer-implemented method of claim 1, further comprising adding the first and second committed capacities to generate a third committed capacity, and wherein generating the cost function further comprises generating the cost function based on the first, second, and third committed capacities.

6. The computer-implemented method of claim 1, wherein the processing requirements of the candidate workpiece include batch requirements and setup requirements, determining the first committed capacity further comprises determining the first committed capacity based on the schedule of engagements associated with other workpieces having setup requirements compatible with the setup requirements of the candidate workpiece, determining the second committed capacity further comprises determining the second committed capacity of the resource based on the schedule of engagements associated with other workpieces having setup requirements not compatible with the setup requirements of the candidate workpiece, and the method further comprises;

determining a third committed capacity of the resource based on a schedule of engagements associated with other workpieces having batch requirements compatible with the batch requirements of the candidate workpiece; and

determining a fourth committed capacity of the resource based on a schedule of engagements associated with other workpieces having batch requirements not compatible with the batch requirements of the candidate workpiece.

7. The computer-implemented method of claim 6, wherein generating the cost function further comprises generating the cost function based on the first, second, third, and fourth committed capacities.

8. The computer implemented method of claim 7, further comprising determining an overall committed capacity of the resource, and wherein generating the cost function further comprises generating the coat function based on the first, second, third, fourth, and overall committed capacities.

9. The computer-implemented method of claim 8, wherein determining the overall committed capacity further comprises adding the first and second committed capacities.

10. The computer-implemented method of claim 8, wherein determining the overall committed capacity further comprises adding the third and fourth committed capacities.

11. The computer implemented method of claim 1, wherein generating the cost function further comprises:

providing a rate per time unit (RTU) function specifying a rate for using the resource; and

evaluating the RTU function based on the first and second committed capacities.

12. The computer-implemented method of claim 1, wherein the RTU fiction includes a first component specifying the rate as a function of the first committed capacity and a second component specifying the rate as a function of the second committed capacity, and generating the cost function further comprises;

generating a first component of the cost function based on the fist committed capacity and the first component of the RTU function; and

generating a second component of the cost function based on the second committed capacity and the second component of the RTU function.

13. The computer-implemented method of claim 12, wherein providing the RTU function further comprises providing a decreasing convex function as the first component of the RTU function.

14. The computer-implemented method of claim 12, wherein providing the RTU function further comprises providing an increasing convex function as the second component of the RTU function.

15. The computer-implemented method of claim 12, wherein the RTU function includes a third component specifying the rate as a function of an overall committed capacity of the resource and generating the cost function further comprises:

adding the first and second committed capacities to generate the overall committed capacity of the resource; and

generating a third component of the cost function based on the overall committed capacity and the third component of the RTU function.

16. The computer-implemented method of claim 15, wherein providing the RTU function further comprises providing an increasing convex function as the third component of the RTU function.

17. The computer implemented method of claim 6, wherein generating the cost function further comprises:

providing a rate per time unit (RTU) function specifying a rate for using the resource, the RTU function including a first component specifying the rate as a function of the first committed capacity, a second component specifying the rate as a function of the second committed capacity, a third component specifying the rate as a function of the third committed capacity, and a fourth component specifying the rate as a function of the fourth committed capacity;

generating a first component of the cost function based on the first committed capacity and the first component of the RTU function

generating a second component of the cost function based on the second committed capacity and the second component of the RTU function;

generating a third component of the cost function based on the third committed capacity and the third component of the RT function; and

generating a fourth component of the cost function based on the four committed capacity and the fourth component of the RTU function.

18. The computer-implemented method of claim 17, wherein providing the RTU function further comprises:

providing a first decreasing convex function as the fist component of the RTU function;

providing a first increasing convex function as the second component of the RTU function;

providing a second decreasing convex function as the third component of the RTU function; and

providing a second increasing convex function as the fourth component of the RTU function.

19. The computer-implemented method of claim 17, wherein the RTU function includes a fifth component specifying the rate as a function of an overall committed capacity of the resource and generating the cost function further comprises:

determining an overall committed capacity of the resource; and

evaluating the RTU function based on the first, second, third, fourth, and overall committed capacities.

20. The computer-implemented method of claim 19, wherein providing the RTU function further comprises providing an increasing convex function as the fifth component of the RTU function.

21. The computer-implemented method of claim 19, wherein determining the overall committed capacity further comprises adding the first and second committed capacities.

22. The computer-implemented method of claim 19, wherein deter the overall committed capacity further comprises adding the third and fourth committed capacities.

23. The computer-implemented method of claim 11, wherein the RTU function includes a first component comprising a decreasing convex Action having a first steepness parameter and a second decreasing convex function having a second steepness parameter greater than the first steepness parameter, and generating the cost function further comprises:

generating a first component of the cost function based on the first committed capacity and the first component of the RTU function;

generating a second component of the cost function based on the first committed capacity and the second component of the RTU function; and

summing the first and second components of the cost function.

24. The computer-implemented method of claim 12, wherein generating the cost function comprises:

specifying a desired minimum value and a desired maximum value for the sum of the first and second cost function components;

determining an observed minimum value and an observed maximum value for the sum of the first and second cost function component; and

scaling the sum of the first and second components based on the observed maximum and minimum values and the desired maximum and minimum values.

25. A system, comprising:

a resource for processing a candidate workpiece; and

at least one scheduling agent configured to identify processing requirements for the candidate workpiece, determine a first committed capacity of the resource based on a schedule of engagements associated with other workpieces having processing requirements compatible with the processing requirements of the candidate workpiece, determining a second committed capacity of the resource based on a schedule of engagements associated with other workpieces having processing requirements not compatible with the processing requirements of the candidate workpiece, and generate a cost function based on the first and second committed capacities.

26. The system of claim 25, wherein the scheduling agent is further configured to identify a commitment window for processing the workpiece and generate a cost for processing the workpiece based on the cost function and the commitment window.

27. The system of claim 25, wherein the processing requirements of the candidate workpiece include batch requirements, and the scheduling agent is further configured to determine the first committed capacity based on the schedule of engagements associated with other workpieces having batch requirements compatible with the batch requirements of the candidate workpiece and determine the second committed capacity of the resource based on the schedule of engagements associated with other workpieces having batch requirements not compatible with the batch requirements of the candidate workpiece.

28. The system of claim 25, wherein the processing requirements of the candidate workpiece include setup requirements, and the scheduling agent is further configured to determine the first committed capacity based on the schedule of engagements associated with other workpieces having setup requirements compatible with the setup requirements of the candidate workpiece, and determine the second committed capacity of the resource based on the schedule of engagements associated with other workpieces having setup requirements not compatible with the setup requirements of the candidate workpiece.

29. The system of claim 25, wherein the scheduling agent is further configured to add the first and second committed capacities to generate a third committed capacity and generate the cost function based on the first, second, and third committed capacities.

30. The system of claim 25, wherein the processing requirements of the candidate workpiece include batch requirements and setup requirements, and the scheduling agent is further configured to determine the first committed capacity based on the schedule of engagements associated with other workpieces having setup requirements compatible with the setup requirements of the candidate workpiece, determine the second committed capacity of the resource based on the schedule of engagements associated with other workpieces having setup requirements not compatible with the setup requirements of the candidate workpiece, determine a third committed capacity of the resource based on a schedule of engagements associated with other workpieces having batch requirements compatible with the batch requirements of the candidate workpiece, and determine a fourth committed capacity of the resource based on a schedule of engagements associated with other workpieces having batch requirements not compatible with the batch requirements of the candidate workpiece.

31. The system of claim 30, wherein the scheduling agent is further configured to generate the cost function based on the first, second, third, and fourth committed capacities.

32. The system of claim 31, wherein the scheduling agent is further configured to determine an overall committed capacity of the resource and generate the cost function based on the first, second, third, fourth, and overall committed capacities.

33. The system of claim 32, wherein the scheduling agent is further configured to determine the overall committed capacity by adding the first and second committed capacities.

34. The system of claim 32, wherein the scheduling agent is further configured to determine the overall committed capacity by adding the third and fourth committed capacities.

35. The system of claim 25, wherein the scheduling agent is further configured to provide a rate per time unit (RTU) function specifying a rate for using the resource and evaluate the RTU function based on the first and second committed capacities to generate the cost function.

36. The system of claim 35, wherein the RTU fiction includes a first component specifying the rate as a function of the first committed capacity and a second component specifying the rate as a function of the second committed capacity, the scheduling agent is further configured to generate a first component of the cost unction based on the first committed capacity and the first component of the RTU function and generate a second component of the cost function based on the second committed capacity and the second component of the RTU function.

37. The system of claim 36, wherein the first component of the RTU function comprises a decreasing convex function.

38. The system of claim 36, wherein the second component of the RTU function comprises an increasing convex function.

39. The system of claim 36, wherein the RTU unction includes a third component specifying the rate as a function of an overall committed capacity of the resource and the scheduling agent is further configured to add the first and second committed capacities to generate the overall committed capacity of the resource and generate a third component of the cost function based on the overall committed capacity and the third component of the RTU fiction.

40. The system of claim 39, wherein the third component of the RTU function comprises an increasing convex function.

41. The system of claim 40, wherein the scheduling agent is further configured to provide a rate per lime unit (RTU) function specifying a rate for using the resource, the RTU function including a first component specifying the rate as a function of the first committed capacity, a second component specifying the rate as a function of the second committed capacity, a third component specifying the rate as a function of the third committed capacity, and a fourth component specifying the rate as a function of a fourth committed capacity, generate a first component of the cost function based on the first committed capacity and the first component of the RTU function, generate a second component of the cost function based on the second committed capacity and the second component of the RTU function, generate a third component of the cost function based on the third committed capacity and the third component of the RTU function, and generate a fourth component of the cost function based on the fourth committed capacity and the fourth component of the RTU function.

42. The system of claim 41, wherein the first component of the RTU function comprises a first decreasing convex function, the second component of the RTU function comprises a first increasing convex function, the third component of the RTU unction comprises a second decreasing convex function, and the fourth component of the RTU function comprises a second increasing convex function.

43. The system of claim 41, wherein the RTU function includes a fifth component specifying the rate as a function of an overall committed capacity of the resource and the scheduling agent is further configured to determine an overall committed capacity of the resource and evaluate the RTU function based on the first, second, third, fourth, and overall committed capacities.

44. The system of claim 43, wherein the fifth component of the RTU function comprises an increasing convex function.

45. The system of claim 43, wherein the scheduling agent is further configured to determine the overall committed capacity by adding the first and second committed capacities.

46. The system of claim 43, wherein the scheduling agent is further configured to determine the overall committed capacity by adding the third fourth committed capacities.

47. The system of claim 35, wherein the RTU function includes a first component comprising a decreasing convex function having a first steepness parameter and a second decreasing convex function having a second steepness parameter greater than the first steepness parameter, and the scheduling agent is further configured to generate a first component of the cost function based on the first committed capacity and the first component of the RTU function, generate a second component of the cost function based on the first committed capacity and the second component of the RTU function, and sum the first and second components of the cost function.

48. The system of claim 36, wherein the scheduling agent is further configured to specify a desired minimum value and a desired maximum value for the sum of the first and second cost function components, determine an observed minimum value and an observed maximum value for the gum of the first and second cost function components, and scale the sum of the first and second components based on the observed maximum and minimum values and the desired maximum and minimum values.

49. A system, comprising:

means for processing a candidate workpiece;

means for identifying processing requirements for the candidate workpiece;

means for determining a first committed capacity of the resource based on a schedule of engagements associated with other workpieces having processing requirements compatible with the processing requirements of the candidate workpiece;

means for determining a second committed capacity of the resource based on a schedule of engagements associated with other workpieces having processing requirements not compatible with the processing requirements of the candidate workpiece; and

means for generating a cost function based on the first and second committed capacities.