Method and apparatus for reducing scheduling conflicts for a resource

• US 7,069,097 B1
• Filed: 08/30/2002
• Issued: 06/27/2006
• Est. Priority Date: 08/30/2002
• Status: Active Grant

• Current Assignee: Globalfoundries US Incorporated (GlobalFoundries, Inc.)
• Original Assignee: Advanced Micro Devices, Inc.
• Inventors: Li, Yiwei, Parunak, H. Van Dyke, Barto, Larry D., Nettles, Steven C.
• Primary Examiner(s): RODRIGUEZ, PAUL L
• Application Number:
  US10/231,561
• Time in Patent Office: 1,397 Days
• Field of Search: 700/28, 700/36, 700/95, 700/96, 700 99-104, 700/121, 705/8, 705/9
• US Class Current: 700/100
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling

Abstract

A method includes providing a schedule of engagements for a resource. Each engagement has a working window and an associated engagement density function. The engagement density functions of the scheduled engagements are combined to generate a committed capacity function for the resource. A region of violation in the committed capacity function is identified where the committed capacity of the resource exceeds a capacity threshold. An area of a region of overlap between the working window of a selected one of the engagements and the region of violation is determined. An area reduction amount for the selected engagement is determined based on a portion of the area of the region of overlap. The working window of the selected engagement is changed based on the area reduction amount.

Claims

1. A method, comprising:

providing a schedule of engagements for a resource, each engagement having a working window and an associated engagement density function;

combining the engagement density functions of the scheduled engagements to generate a committed capacity function for the resource;

identifying a region of violation in the committed capacity function where the committed capacity of the resource exceeds a capacity threshold;

determining an area of a region of overlap between the working window of a selected engagement and the region of violation;

determining an area reduction amount for the selected engagement based on a portion of the area of the region of overlap less than the total area of the region of overlap; and

changing the working window of the selected engagement based on the area reduction amount.

2. The method of claim 1, wherein changing the working window of the selected engagement further comprises shifting the working window of the selected engagement.

3. The method of claim 1, wherein changing the working window oft the selected engagement further comprises shrinking the working window of the selected engagement.

4. The method of claim 1, further comprising:

determining a plurality of candidate area reduction amounts, each candidate area reduction amount comprising a different portion of area of the region of overlap;

determining a candidate change to the working window for each of the candidate area reductions;

determining a cost associated with each candidate change; and

selecting the candidate change having the lowest cost per unit of area reduction.

5. The method of claim 4, further comprising:

identifying a plurality of engagements having working windows overlapping the region of violation;

generating a plurality of candidate changes for each of the identified engagements; and

determining a cost associated with each of candidate changes for each of the identified engagements.

6. The method of claim 1, wherein the working window of the selected engagement comprises a start time, an end time, and a processing kernel, and changing the working window of the selected engagement based on the area reduction amount further comprises calculating a change to at least one of the start time and the end time.

7. The method of claim 6, wherein calculating the change to at least one of the start time and the end time further comprises calculating a time required to change one of the start time and the end time to reduce the region of overlap by the area reduction amount.

8. The method of claim 6, wherein calculating the change further comprises shifting the start time and the end time.

9. The method of claim 6, wherein calculating the change further comprises changing one of the start time and the end time without changing the other of the start time and the end time.

10. The method of claim 6, wherein calculating the change further comprises calculating a slack parameter based on the start time, the end time, and the processing kernel.

11. The method of claim 10, wherein the engagement density function of the selected engagement includes a plateau region, and the method further comprises determining a plateau height, a plateau start time, and a plateau end time of the plateau region based on the slack parameter, the start time, the end time, and the processing kernel.

12. The method of claim 6, wherein the engagement density function of the selected engagement includes a first ramp region, a plateau region, and a second ramp region and calculating the change to at least one of the start time and the end time further comprises determining which, if any, of the first ramp region, the plateau region, and the second ramp region intersects the region of violation at a starting point of the region of overlap.

13. The method of claim 11, wherein calculating the change to at least one of the start time and the end time further comprises calculating the change to one of the start time and the end time as a function of the area reduction amount, a starting point of the region of overlap, the start time, the end time, the plateau height, the slack parameter, the plateau start time, and the plateau end time.

14. The method of claim 1, further comprising calculating the capacity threshold based on a setup allowance.

15. The method of claim 14, further comprising generating the setup allowance based on a historical analysis of previous setup times for the resource.

16. The method of claim 15, wherein generating the setup allowance further comprises generating the setup allowance based on an exponentially weighted moving average of the previous setup times for the resource.

17. The method of claim 1, further comprising calculating the capacity threshold based on a safety allowance.

18. The method of claim 17, further comprising setting the safety allowance so the capacity threshold has a value less than a maximum capacity of the resource.

19. The method of claim 17, further comprising setting the safety allowance so the capacity threshold has a value greater than a maximum capacity of the resource to allow for overbooking of the resource.

20. The method of claim 1, further comprising calculating the capacity threshold based on a maximum number of workpieces the resource can process concurrently.

21. The method of claim 1, further comprising calculating the capacity threshold based on the maximum number of workpieces the resource can process concurrently less a setup allowance less a safety allowance.

22. The method of claim 5, wherein each engagement has an associated normalized budget, and the method further comprises:

determining if the candidate area reduction amount associated with the selected candidate change is less than a configurable percentage of a total area of the region of violation; and

canceling one of the engagements having the lowest associated normalized budget responsive to the candidate area reduction amount associated with the selected candidate change being less than the configurable percentage.

23. A system, comprising:

a resource for processing a workpiece; and

at least one scheduling agent configured to provide a schedule of engagements for a resource, each engagement having a working window and an associated engagement density function, combine the engagement density functions of the scheduled engagements to generate a committed capacity function for the resource, identify a region of violation in the committed capacity function where the committed capacity of the resource exceeds a capacity threshold, determine an area of a region of overlap between the working window of a selected engagement and the region of violation, determine an area reduction amount for the selected engagement based on a portion of the area of the region of overlap less than the total area of the region of overlap, and change the working window of the selected engagement based on the area reduction amount.

24. The system of claim 23, wherein the scheduling agent is further configured to shift the working window of the selected engagement.

25. The system of claim 23, wherein the scheduling agent is further configured to shrink the working window of the selected engagement.

26. The system of claim 23, wherein the scheduling agent is further configured to determine a plurality of candidate area reduction amounts, each candidate area reduction amount comprising a different portion of area of the region of overlap, determine a candidate change to the working window for each of the candidate area reductions, determine a cost associated with each candidate change, and select the candidate change having the lowest cost per unit of area reduction.

27. The system of claim 26, wherein the scheduling agent is further configured to identify a plurality of engagements having working windows overlapping the region of violation, generate a plurality of candidate changes for each of the identified engagements, and determine a cost associated with each of candidate changes for each of the identified engagements.

28. The system of claim 23, wherein the working window of the selected engagement comprises a start time, an end time, and a processing kernel, and the scheduling agent is further configured to calculate a change to at least one of the start time and the end time.

29. The system of claim 28, wherein the scheduling agent is further configured to calculate a time required to change one of the start time and the end time to reduce the region of overlap by the area reduction amount.

30. The system of claim 28, wherein the scheduling agent is further configured to shift the start time and the end time.

31. The system of claim 28, wherein the scheduling agent is further configured to change one of the start time and the end time without changing the other of the start time and the end time.

32. The system of claim 28, wherein the scheduling agent is further configured to calculate a slack parameter based on the start time, the end time, and the processing kernel.

33. The system of claim 32, wherein the engagement density function of the selected engagement includes a plateau region, and the scheduling agent is further configured to determine a plateau height, a plateau start time, and a plateau end time of the plateau region based on the slack parameter, the start time, the end time, and the processing kernel.

34. The system of claim 28, wherein the engagement density function of the selected engagement includes a first ramp region, a plateau region, and a second ramp, region and the scheduling agent is further configured to determine which, if any, of the first ramp region, the plateau region, and the second ramp region intersects the region of violation at a starting point of the region of overlap.

35. The system of claim 33, wherein the scheduling agent is further configured to calculate the change to one of the start time and the end time as a function of the area reduction amount, a starting point of the region of overlap, the start time, the end time, the plateau height, the slack parameter, the plateau start time, and the plateau end time.

36. The system of claim 23, wherein the scheduling agent is further configured to calculate the capacity threshold based on a setup allowance.

37. The system of claim 36, wherein the scheduling agent is further configured to generate the setup allowance based on a historical analysis of previous setup times for the resource.

38. The system of claim 37, wherein the scheduling agent is further configured to generate the setup allowance based on an exponentially weighted moving average of the previous setup times for the resource.

39. The system of claim 23, wherein the scheduling agent is further configured to calculate the capacity threshold based on a safety allowance.

40. The system of claim 39, wherein the scheduling agent is further configured to set the safety allowance so the capacity threshold has a value less than a maximum capacity of the resource.

41. The system of claim 39, the scheduling agent is further configured to set the safety allowance so the capacity threshold has a value greater than a maximum capacity of the resource to allow for overbooking of the resource.

42. The system of claim 23, wherein the scheduling agent is further configured to calculate the capacity threshold based on a maximum number of workpieces the resource can process concurrently.

43. The system of claim 23, the scheduling agent is further configured to calculate the capacity threshold based on the maximum number of workpieces the resource can process concurrently less a setup allowance less a safety allowance.

44. The system of claim 27, wherein each engagement has an associated normalized budget, and the scheduling agent is further configured to determine if the candidate area reduction amount associated with the selected candidate change is less than a configurable percentage of a total area of the region of violation and cancel one of the engagements having the lowest associated normalized budget responsive to the candidate area reduction amount associated with the selected candidate change being less than the configurable percentage.

45. A system, comprising:

means for providing a schedule of engagements for a resource, each engagement having a working window and an associated engagement density function;

means for combining the engagement density functions of the scheduled engagements to generate a committed capacity function for the resource;

means for identifying a region of violation in the committed capacity function where the committed capacity of the resource exceeds a capacity threshold;

means for determining an area of a region of overlap between the working window of a selected engagement and the region of violation;

means for determining an area reduction amount for the selected engagement based o n a portion of the area of the region of overlap less than the total area of the region of overlap; and

means for changing the working window of the selected engagement based on the area reduction amount.