Method and apparatus for scheduling workpieces with compatible processing requirements

• US 6,782,302 B1
• Filed: 08/30/2002
• Issued: 08/24/2004
• Est. Priority Date: 08/30/2002
• Status: Active Grant

• Current Assignee: Advanced Micro Devices, Inc.
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Barto, Larry D., Li, Yiwei, Nettles, Steven C., Parunak, H. Van Dyke
• Primary Examiner(s): Picard, Leo
• Assistant Examiner(s): RODRIGUEZ, PAUL L
• Application Number:
  US10/232,145
• Time in Patent Office: 725 Days
• Field of Search: 700/28, 700/36, 700/95, 700/96, 700/99, 700/100-104, 700/121, 705/8, 705/9
• US Class Current: 700/101
• CPC Class Codes: G05B 19/41865 characterised by job scheduling, process planning, material flow
• CPC Class Codes: G05B 2219/32263 Afo products, their components to be manufactured, lot selective
• CPC Class Codes: G05B 2219/32266 Priority orders
• CPC Class Codes: G05B 2219/45031 Manufacturing semiconductor wafers
• 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 processing workpieces using a resource includes generating a plurality of engagements for processing the workpieces by the resource. Each engagement is associated with one of the workpieces and has associated processing requirements. A first one of the plurality of engagements is designated as a seed engagement. A set of candidate engagements from the plurality of engagements having associated processing requirements compatible with the processing requirements of the seed engagement is identified. A combined engagement is generated including the seed engagement and at least one of the candidate engagements.

Claims

1. A method for processing workpieces using a resource, comprising:

generating a plurality of engagements for processing the workpieces by the resource, each engagement being associated with one of the workpieces and having associated processing requirements;

designating a first one of the plurality of engagements as a seed engagement;

identifying a set of candidate engagements from the plurality of engagements having associated processing requirements compatible with the processing requirements of the seed engagement, wherein the associated processing requirements comprise batch requirements compatible with batch requirements of the seed engagement; and

generating a combined engagement including the seed engagement and at least one of the candidate engagements, the combined engagement representing a batch process for simultaneously processing the combined engagement.

2. The method of claim 1, wherein each engagement has an associated working window and identifying the set of candidate engagements further comprises identifying the set of candidate engagements having working windows within a predetermined time interval of the working window of the seed engagement.

3. The method of claim 1, wherein each engagement has an associated working window and identifying the set of candidate engagements further comprises identifying the set of candidate engagements having working windows within a dynamic time interval of the working window of the seed engagement.

4. The method of claim 1, wherein each engagement has an associated working window and identifying the set of candidate engagements further comprises identifying the set of candidate engagements having working windows that overlap the working window of the seed engagement.

5. The method of claim 1, wherein the processing requirements associated with the engagements define a plurality of batch types, and the method further comprises:

selecting one of the batch types;

designating one of the engagements having the selected batch type as the seed engagement; and

identifying the set of candidate engagements from other engagements having the selected batch type.

6. The method of claim 5, wherein selecting the one of the batch types further comprises:

determining a batch priority for each of the batch types; and

designation the batch type having the highest batch priority as the selected batch type.

7. The method of claim 6, wherein determining the batch priority further comprises determining a committed capacity of the resource for each of the batch types and determining the batch priority based on at least the determined committed capacities.

8. The method of claim 7, wherein each engagement has an associated budget and determining the batch priority further comprises determining the batch priority based on the determined committed capacity and the budgets of the workpieces having a common batch type.

9. The method of claim 8, wherein each engagement has an associated processing kernel, the workpieces having a common batch type have processing kernels with the same duration, and determining the batch priority further comprises:

determining an average budget of the workpieces having a common batch type;

normalizing the average budget to generate an average budget per unit time by dividing by the duration of the processing kernel of the workpieces having a common batch type;

multiplying the committed capacity of the workpieces having a common batch type by the normalized average budget to generate the batch priority.

10. The method of claim 6, wherein each engagement has an associated budget and determining the batch priority flier comprises determining the batch priority based on the budgets of the workpieces having a common batch type.

11. The method of claim 6, further comprising:

defining a fixed time horizon interval; and

determining the batch type having the highest batch priority over the fixed horizon time interval.

12. The method of claim 6, wherein each engagement has an associated budget and designating the first one of the plurality of engagements as the seed engagement further comprises:

selecting a seed time;

identifying a set of potential seed engagements having the selected batch type and having associated working windows that encompass the seed time; and

selecting the one of the potential seed engagements having the highest budget as the seed engagement.

13. The method of claim 6, wherein designating the first one of the plurality of engagements as the seed engagement further comprises:

selecting a seed time;

identifying a set of potential seed engagements having the selected batch type and having associated working windows that encompass the seed time; and

selecting the seed engagement based on a characteristic of the working windows associated with the potential seed engagements.

14. The method of claim 13, wherein each working window has a start time and selecting the seed engagement based on the characteristic of the working windows further comprises selecting the one of the potential seed engagements having the earliest start time as the seed engagement.

15. The method of claim 13, wherein each working window has a duration and selecting the seed engagement based on the characteristic of the working windows further comprises selecting the one of the potential seed engagements having the least duration as the seed engagement.

16. The method of claim 13, wherein each working window has a duration and selecting the seed engagement based on the characteristic of the working windows further comprises selecting the one of the potential seed engagements having the greatest duration as the seed engagement.

17. The method of claim 6, wherein each engagement has an associated budget and a working window having a start time and a duration, and designating the first one of the plurality of engagements as the seed engagement further comprises:

selecting a seed time;

identifying a set of potential seed engagements having the selected batch type and having associated working windows that encompass the seed time; and

selecting the seed engagement from the potential seed engagements based on a weighted combination of the budget, the start time, and the duration associated with the potential seed engagements.

18. The method of claim 6, wherein each engagement has an associated processing kernel with a duration, and the method further comprises:

defining a first seed time corresponding to a time at which the resource is expected to be available;

identifying a first batch type having the highest batch priority at the seed time;

defining a first interval to extend from the first seed time to the first seed time plus a duration of the processing kernel associated with engagements having the first batch type;

designating the batch type having the highest batch priority within the first interval as the selected batch type.

19. The method of claim 18, further comprising designating a time at which the batch priority of the selected batch type is greatest over the first interval as a selected seed time.

20. The method of claim 18, wherein defining the first interval further comprises defining the first interval to extend from the first seed time to the first seed time plus a setup time interval plus the duration of the processing kernel associated with engagements having the first batch type.

21. The method of claim 1, wherein each engagement as an associated working window and generating the combined engagement further comprises selecting one of the candidate engagements having a working window that most overlaps with the working window of the seed engagement for adding to the combined engagement.

22. The method of claim 1, wherein each engagement has an associated working window including a start time and generating the combined engagement further comprises selecting one of the candidate engagements having the earliest start time for adding to the combined engagement.

23. A method for processing workpieces using a resource, comprising:

generating a plurality of engagements for processing the workpieces by the resource, each engagement being associated with one of the workpieces and having associated processing requirements, wherein each of the plurality of engagements has an associated working window including a start time, an end time, and a processing kernel;

designating a first one of the plurality of engagements as a seed engagement;

identifying a set of candidate engagements from the plurality of engagements having associated processing requirements compatible with the processing requirements of the seed engagement and working windows that overlap the working window of the seed engagement by determining if the minimum of the seed engagement end time and the candidate engagement end time, minus the maximum of the seed engagement start time and the candidate engagement start time, is greater than or equal to a duration of the candidate engagement processing kernel duration; and

generating a combined engagement including the seed engagement and at least one of the candidate engagements.

24. A method for processing workpieces using a resource, comprising:

generating a plurality of engagements for processing the workpieces by the resource, each engagement being associated with one of the workpieces and having associated processing requirements;

designating a first one of the plurality of engagements as a seed engagement;

identifying a set of candidate engagements from the plurality of engagements having associated processing requirements compatible with the processing requirements of the seed engagement, wherein each engagement includes an associated processing kernel having a duration; and

generating a combined engagement including the seed engagement and at least one of the candidate engagements, the seed engagement and the candidate engagement included in the combined engagement each having a processing kernel having the same duration; and

setting a duration of the processing kernel of the combined engagement equal to the duration of the processing kernel of one of the seed engagement and the candidate engagement included in the combined engagement.

25. The method of claim 24, wherein each engagement has a working window including a start time and an end time, and the generating the combined engagement further comprises:

determining a start time for the combined engagement, the start time being the maximum of the start time of the seed engagement and the start time of the candidate engagement included in the combined engagement; and

;

determining an end time of the combined engagement, the end time being the minimum of the end time of the seed engagement and the end time of the candidate engagement included in the combined engagement.

26. A method for processing workpieces using a resource, comprising:

generating a plurality of engagements for processing the workpieces by the resource, each engagement being associated with one of the workpieces and having associated setup requirements and a processing kernel;

designating a first one of the plurality of engagements as a seed engagement;

identifying a set of candidate engagements from the plurality of engagements having setup requirements compatible with the setup requirements of the seed engagement; and

generating a combined engagement including the seed engagement and at least one of the candidate engagements by concatenating the processing kernel of the at least one candidate engagement with the processing kernel of the seed engagement to generate a setup chain and concatenating a setup kernel representing a setup period for the resource to the front of the setup chain.

27. The method of claim 26, wherein each engagement has a working window including an associated start time, an end time, and a processing kernel having a duration, and identifying the set of candidate engagements further comprises:

including one of the engagements having setup requirements compatible with setup requirements of the seed engagement in the set of candidate engagements if the end time of the selected candidate engagement minus the start time of the seed engagement is greater than or equal to the setup period plus the durations of the processing kernel of the seed engagement and the processing kernel of the selected candidate engagement.

28. The method of claim 27, further comprising determining a maximum idle time for the resource, and wherein identifying the set of candidate engagements further comprises determining if the end time of the seed engagement plus the maximum idle time is greater than the start time of the selected candidate engagement.

29. The method of claim 28, further comprising:

determining a start time for the combined engagement; and

including one of the engagements having setup requirements compatible with setup requirements of the seed engagement in the set of candidate engagements if the start time of the combined engagement is greater than or equal to the start time of the selected candidate engagement minus the sum of the setup period, the processing kernel duration of the seed engagement, and the maximum idle time.

30. The method of claim 29, further comprising setting the start time of the combined engagement to the start time of the selected candidate engagement minus the sum of the setup period, the processing kernel duration of the seed engagement, and the maximum idle time.

31. The method of claim 29, further comprising:

determining an end time for the combined engagement; and

including one of the engagements having setup requirements compatible with setup requirements of the seed engagement in the set of candidate engagements if the end time of the combined engagement is less than or equal to the sum of the end time of the seed engagement, the processing kernel duration of the selected candidate engagement, and the maximum idle time.

32. The method of claim 31, further comprising setting the end time for the combined engagement to the combined engagement to the sum of the end time of the seed engagement, the processing kernel duration of the selected candidate engagement, and the maximum idle time.

33. The method of claim 27, wherein the first seed engagement has associated batch requirements and identifying the first set of candidate engagements further comprises identifying the first set of candidate engagements having batch requirements compatible with the batch requirements of the first seed engagement.

34. The method of claim 26, wherein each engagement has a working window including an associated start time, an end time, and a processing kernel having a duration, and the method further comprises:

determining a maximum idle time for the resource; and

placing the processing kernel of the candidate engagement after the processing kernel of the seed engagement responsive to;

the start time of the selected candidate engagement being less than or equal to the start time of the seed engagement plus the sum of the processing kernel duration of the seed engagement, the maximum idle time, and the setup period; and

the end time of the selected candidate engagement being greater than or equal to the end time of the seed engagement plus the processing kernel duration of the selected candidate engagement.

35. The method of claim 34, wherein the combined engagement has an associated working window including a start time, an end time, and a processing kernel having a duration, and generating the combined engagement further comprises:

setting the start time of the combined engagement to the start time of the selected candidate engagement minus the processing kernel duration of the seed engagement minus the setup period;

setting the end time of the combined engagement to the end time of the seed engagement plus the processing kernel duration of the selected candidate engagement; and

setting the processing kernel duration of the combined engagement to the sum of the processing kernel durations of the seed engagement and the selected candidate engagement.

36. The method of claim 26, wherein each engagement has a working window including an associated start time, an end time, and a processing kernel having a duration, and the method further comprises:

determining a maximum idle time for the resource; and

placing the processing kernel of the candidate engagement before the processing kernel of the seed engagement responsive to;

the start time of the selected candidate engagement being less than or equal to the start time of the seed engagement minus the processing kernel duration of the selected candidate engagement; and

the end time of the selected candidate engagement being greater than or equal to the start time of the seed engagement minus the maximum idle time.

37. The method of claim 36, wherein the combined engagement has an associated working window including a start time, an end time, and a processing kernel having a duration, and generating the combined engagement further comprises:

setting the start time of the combined engagement to the start time of the seed engagement minus the processing kernel duration of the selected candidate engagement;

setting the end time of the combined engagement to the end time of the seed engagement; and

setting the processing kernel duration of the combined engagement to the sum of the processing kernel durations of the seed engagement and the selected candidate engagement.

38. A method for processing workpieces using a resource, comprising:

generating a plurality of engagements for processing the workpieces by the resource, each engagement being associated with one of the workpieces and having associated setup requirements and a processing kernel;

designating a first one of the plurality of engagements as a seed engagement;

identifying a set of candidate engagements from the plurality of engagements having setup requirements compatible with the setup requirements of the seed engagement;

generating a combined engagement including the seed engagement and at least one of the candidate engagements by concatenating the processing kernel of the at least one candidate engagement with the processing kernel of the seed engagement to generate a setup chain;

adding other candidate engagements to the setup chain; and

terminating the adding of other candidate engagements if addition of a subsequent candidate engagement would result in a late condition for one of the plurality of engagements not having setup requirements compatible with setup requirements of the seed engagement.

39. A method for processing workpieces using a resource, comprising:

generating a plurality of engagements for processing the workpieces by the resource, each engagement being associated with one of the workpieces and having associated setup requirements, an associated processing kernel, and a budget;

designating a first one of the plurality of engagements as a seed engagement;

identifying a set of candidate engagements from the plurality of engagements having setup requirements compatible with the setup requirements of the seed engagement; and

generating a combined engagement including the seed engagement and at least one of the candidate engagements by concatenating the processing kernel of the at least one candidate engagement with the processing kernel of the seed engagement to generate a setup chain by normalizing the budget for each of the candidate engagements by dividing the budget by a duration of the processing kernel and selecting the one of the candidate engagements having the highest normalized budget for adding to the combined engagement.

40. A method for processing workpieces using a resource, comprising:

generating a plurality of engagements for processing the workpieces by the resource, each engagement being associated with one of the workpieces and having associated setup requirements, a processing kernel, and an associated working window including a start time;

designating a first one of the plurality of engagements as a seed engagement;

identifying a set of candidate engagements from the plurality of engagements having setup requirements compatible with the setup requirements of the seed engagement; and

generating a combined engagement including the seed engagement and at least one of the candidate engagements by concatenating the processing kernel of the at least one candidate engagement with the processing kernel of the seed engagement to generate a setup chain and selecting one of the candidate engagements having the earliest start time for adding to the combined engagement.

41. A method for processing workpieces using a resource, comprising:

generating a plurality of engagements for processing the workpieces by the resource, each engagement being associated with one of the workpieces and having associated setup requirements, a processing kernel, and an associated working window including an end time;

designating a first one of the plurality of engagements as a seed engagement;

identifying a set of candidate engagements from the plurality of engagements having setup requirements compatible with the setup requirements of the seed engagement; and

generating a combined engagement including the seed engagement and at least one of the candidate engagements by concatenating the processing kernel of the at least one candidate engagement with the processing kernel of the seed engagement to generate a setup chain and selecting one of the candidate engagements having the earliest end time for adding to the combined engagement.

42. A method for processing workpieces using a resource, comprising:

generating a plurality of engagements for processing the workpieces by the resource, each engagement being associated with one of the workpieces and having associated setup requirements, a processing kernel, and an associated processing kernel;

designating a first one of the plurality of engagements as a seed engagement;

identifying a set of candidate engagements from the plurality of engagements having setup requirements compatible with the setup requirements of the seed engagement; and

generating a combined engagement including the seed engagement and at least one of the candidate engagements by concatenating the processing kernel of the at least one candidate engagement with the processing kernel of the seed engagement to generate a setup chain and selecting one of the candidate engagements having a largest kernel duration for adding to the combined engagement.

43. A method for processing workpieces using a resource, comprising:

generating a plurality of engagements for processing the workpieces by tho resource, each engagement being associated with one of the workpieces and having associated setup requirements and a processing kernel;

designating a first one of the plurality of engagements as a seed engagement;

identifying a set of candidate engagements from the plurality of engagements having setup requirements compatible with the setup requirements of the seed engagement; and

generating a combined engagement including the seed engagement and at least one of the candidate engagements by concatenating the processing kernel of the at least one candidate engagement with the processing kernel of the seed engagement to generate a setup chain;

adding other candidate engagements to the setup chain;

determining if the addition of a subsequent candidate engagement would result in a late condition for one of the plurality of engagements not having setup requirements compatible with setup requirements of the seed engagement;

determining a first cost associated with delaying the one of the plurality of engagements not having setup requirements compatible with setup requirements of the seed engagement;

determining a second cost associated with a setup for the subsequent candidate engagement; and

adding the subsequent engagement responsive to the second cost being greater than the first cost.

44. A method for processing workpieces using a resource, comprising;

generating a plurality of engagements for processing the workpieces by the resource, each engagement being associated with one of the workpieces and having associated processing requirements;

designating a first one of the plurality of engagements as a first seed engagement;

identifying a first set of candidate engagements from the plurality of engagements having associated processing requirements compatible with the processing requirements of the seed engagement;

generating first a combined engagement including the seed engagement and at least one of the candidate engagements;

designating the combined engagement as a second seed engagement; and

repeating the identifying step to generate a second set of candidate engagements; and

generating a second combined engagement including the second seed engagement and at least one of the candidate engagements in the second set.

45. The method of claim 44, wherein the first combined engagement has associated setup requirements and repeating the identifying step further comprises generating the second set of candidate engagements having setup requirements compatible with the setup requirements of the first combined engagement.

46. A system, comprising:

a resource for processing workpieces; and

at least one scheduling agent configured to generate a plurality of engagements for processing the workpieces by the resource, each engagement being associated with one of the workpieces and having associated batch requirements, designate a first one of the plurality of engagements as a seed engagement, identify a set of candidate engagements from the plurality of engagements having associated batch requirements compatible with the batch requirements of the seed engagement, and generate a combined engagement including the seed engagement and at least one of the candidate engagements, the combined engagement representing a batch process for simultaneously processing the combined engagement.

47. A system, comprising:

means for processing workpieces;

means for generating a plurality of engagements for processing the workpieces by a resource, each engagement being associated with one of the workpieces and having associated batch requirements;

means for designating a first one of the plurality of engagements as a seed engagement;

means for identifying a set of candidate engagements from the plurality of engagements having associated batch requirements compatible with the batch requirements of the seed engagement; and

means for generating a combined engagement including the seed engagement and at least one of the candidate engagements, the combined engagement representing a batch process for simultaneously processing the combined engagement.