Back to results
US 6,782,302 B1Granted
Method and apparatus for scheduling workpieces with compatible processing requirements
AssigneeAdvanced Micro Devices, Inc.
InventorsLarry D. Barto, Yiwei Li, Steven C. Nettles, H. Van Dyke Parunak
Life of this patent
Estimating the term…
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.
Claims47
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 more elements
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.
2 more elements
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.
4 more elements
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.
2 more elements
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.
4 more elements
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.
2 more elements
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.
2 more elements
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.
2 more elements
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.
2 more elements
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.
8 more elements
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.
6 more elements
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.
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.
3 more elements
Dependencies are inferred from the claim text.