Method and apparatus for evaluating bids for scheduling a resource Number:6,801,819 from the United States Patent and Trademark Office (PTO) owispatent

Title: Method and apparatus for evaluating bids for scheduling a resource

Abstract: A method for scheduling a resource for processing a workpiece includes defining a commitment window having a kernel specifying a time period required for processing the workpiece. A plurality of candidate bids having candidate commitment windows within the commitment window with varying start times, end times and candidate commitment window sizes is generated. A cost for each of the plurality of candidate bids is determined. A flexibility discount is applied to the cost of the candidate bid. Each candidate bid is evaluated in accordance with an objective function. A candidate bid is selected for scheduling the resource based on the objective function evaluation. A system includes a resource for processing a workpiece and at least one scheduling agent. The scheduling agent is configured to define a commitment window having a kernel specifying a time period required for processing the workpiece, generate a plurality of candidate bids having candidate commitment windows within the commitment window with varying start times, end times and candidate commitment window sizes, determine a cost for each of the plurality of candidate bids, apply a flexibility discount to the cost of the candidate bid, evaluate each candidate bid in accordance with an objective function, and select a candidate bid for scheduling the resource based on the objective function evaluation.

Patent Number: 6,801,819 Issued on 10/05/2004 to Barto,   et al.

---

Inventors:	Barto; Larry D. (Austin, TX), Li; Yiwei (Austin, TX), Nettles; Steven C. (Johnson City, TX), Parunak; H. Van Dyke (Ann Arbor, MI)
Assignee:	Advanced Micro Devices, Inc. (Austin, TX)
Appl. No.:	10/231,930
Filed:	August 30, 2002

---

Current U.S. Class:	700/99 ; 700/121
Current International Class:	G06Q 10/00 (20060101)
Field of Search:	700/95,96,99,100,101-104,121

---

References Cited [Referenced By]

---

U.S. Patent Documents

	4796194		January 1989		Atherton
	5093794		March 1992		Howie et al.
	5369570		November 1994		Parad
	5375061		December 1994		Hara et al.
	5444632		August 1995		Kline et al.
	5446671		August 1995		Weaver et al.
	5548535		August 1996		Zvonar
	5586021		December 1996		Fargher et al.
	5835688		November 1998		Fromherz
	5890134		March 1999		Fox
	5953229		September 1999		Clark et al.
	6038539		March 2000		Maruyama et al.
	6088626		July 2000		Lilly et al.
	6091998		July 2000		Vasko et al.
	6128542		October 2000		Kristoff et al.
	6148239		November 2000		Funk et al.
	6202062		March 2001		Cameron et al.
	6263255		July 2001		Tan et al.
	6356797		March 2002		Hsieh et al.
	6374144		April 2002		Viviani et al.
	6400999		June 2002		Kashiyama et al.
	6434443		August 2002		Lin
	6584369		June 2003		Patel et al.

Other References

International Search Report dated Sep. 30, 2003 (PCT.US02/41777; TT4739-PCT). . U.S. patent application Ser. No. 10/331,715, Nettles et al., filed Dec. 30, 2002. . U.S. patent application Ser. No. 10/331,598, Barto et al., filed Dec. 30, 2002. . U.S. patent application Ser. No. 10/331,596, Barto et al., filed Dec. 30, 2002. . U.S. patent application Ser. No. 10/284,705, Nettles et al., filed Oct. 31, 2002. . U.S. patent application Ser. No. 10/233,197, Barto et al., filed Aug. 30, 2002. . U.S. patent application Ser. No. 10/232,145, Barto et al., filed AUg. 30, 2002. . U.S. patent application Ser. No. 10/231,930, Barto et al., filed Aug. 30, 2002. . U.S. patent application Ser. No. 10/231,888, Barto et al., filed Aug. 30, 2002. . U.S. patent application Ser. No. 10/231,849, Barto et al., filed AUg. 30, 2002. . U.S. patent application Ser. No. 10/231,648, Barto et al., filed Aug. 30, 2002. . U.S. patent application Ser. No. 10/231,561, Barto et al., filed Aug. 30, 2002. . U.S. patent application Ser. No. 10/190,194, Li et al., filed Jul. 3, 2002. . U.S. patent application Ser. No. 10/160,990, Mata et al., filed May 31, 2002. . U.S. patent application Ser. No. 10/160,956, Li et al., filed May 31, 2002. . U.S. patent application Ser. No. 10/135,145, Mata et al., filed Apr. 30, 2002. . Resende, "Shop Floor Scheduling of Semiconductor Wafer Manufacturing," University of California, Berkeley (1987). . Glassey et al., "Closed-Loop Job Release Control for VLSI Circuit Manufacturing," IEEE Transactions on Semiconductor Manufacturing 1:36-46 (1988). . "Agent-Enhanced Manufacturing System Initiative," Technologies for the Integration of Manufacturing Applications (TIMA) (Oct. 1997). . "Factory Integration," The National Technology Roadmap for Semiconductors: Technology Needs (1997) 114-132. . SALSA Enhancements for next Swarm Release (Apr. 22. 1999). . SALSA Exceptions--Minutes from May 11, 1999. . Starvation Avoidance Lot Start Agent (SALSA) (Overview: Apr. 15, 1999). . Starvation Avoidance Lot Start Agent, Fab25 AEMSI/SALSA Review Meeting (May 26, 1999). . Starvation Avoidance Lot Start Agents, Iteration I Requirements Kickoff (May 3, 1999). . Van Parunak, "Review of Axtell and Epstein" (Jun. 23, 1999). . Baumgartel et al., "Combining Multi-Agent Systems and Constraint Techniques in Production Logistics" (1996). . Bonvik et al., "Improving a Kanban Controlled Production Line Through Rapid Information Dissemination" (Jul. 10, 1995). . Butler et al., "ADDYMS: Architecture for Distributed Dynamic Manufacturing Scheduling," pp. 199-213. . Fordyce et al., "Intergrating Decision Technologies for Dispatch Scheduling in Semiconductor Manufacturing," Logistics Management System (LM), pp. 473-516. . Hynynen, "BOSS: An Artifically Intelligent System for Distributed Factory Scheduling," Computer Applications in Production and Engineering, pp. 667-677 (1989). . Li et al., "Minimum Inventory Variability Schedule with Applications in Semiconductor Fabrication," IEEE Transactions on Semconductor Manufacturing 9:145-149 (1996). . Lin et al., "Integrated Shop Floor Control Using Autonomous Agents," IIE Transactions 24:57-71 (1992). . Lu et al., "Efficient Scheduling Policies to Reduce Mean and Variance of Cycle-Time in Semiconductor Manufacturing Plants," IEEE Transactions Semiconductor Manufacutring 7:374-388 (1994). . Martin-Vega et al., "Applying Just-In-Time in a Wafer Fab: A Case Study," IEEE Transactions on Semicodnuctor Manufacturing 2:16-22 (1989). . Murthy et al., "Agent Based Cooperative Scheduling," pp. 112-117. . Van Parunak et al., "Agents Do It In Time--Experiences with Agent-Based Manufacturing Scheduling" (1999). . Hollister, "Schedule Paper #17 Summary" (Jun. 23, 1999). . Hollister, "Schedule Paper #19 Summary" (Jun. 23, 1999). . Hollister, "Schedule Paper #23 Summary" (Jun. 23, 1999). . Hollister, "Scheduale Paper #32 Summary" (Jun. 23, 1999). . Vaario et al., "An Emergent Modelling Method for Dynamic Scheduling," Journal of Intelligent Manufacturing 9:129-140 (1998). . Wellman et al., "Auction Protocls for Decentralized Scheduling" (May 22, 1998). . Weber, "Material Traceability--The Missing Link in TAP Systems," Test, Assembly and Packaging Automation and Integration '99 Conference. . "ObjectSapce Fab Solutions Semiconductor Product Development Overview" (presented at SEMICON Southwest 1998). . "Agent ENhanced Manufacturing Systems Initiative (AEMSI) Project" (presneted by Dan Radin, ERIM CEC Nov. 12-13, 1998). . Weber, "APC Framework: Raising the Standard for Fab Automation and Integration," Equipment Automation Conference 1.sup.st European Symposium on Semiconductor Manufacturing (Apr. 14, 1999). . Wein, "Scheduling Semiconductor Wafer Fabrication," IEEE Transactions on Semiconductor Manufacturing 1:115-130 (1988). . Bonvik, "Performance Analysis of Manufacturing Systems Under Hybrid Control Policies" (Sep. 22, 1995). . Bonvik, "Performance Analysis of Manufacturing Systems Under Hybrid Control Policies" (Oct. 3, 1995). . Sikora et al., "Coordination Mechanisms for Multi-Agent Manufacturing Systems: Applications to Integrated Manufacturing Scheduling," IEEE Transactions on Engineering Management 44:175-187 (1997). . Sousa et al., "A Dynamic Scheduling Holon for Manufacuting Orders," Journal of Intelligent Manufacturing 9:107-112 (1998). . Upton et al., "Architectures and Auctions in Manufacturing," Int. J. Computer Integrated Manufacturing 4:23-33 (1991). . Gere, "Heuristics in Job Shop Scheduling," Management Science 13:167-190 (1966). . Ehteshami et al., "Trade-Offs in Cycle Time Management: Hot Lots," IEEE Transactions on Semiconductor Manufacturing 5:101-106 (1992). . Axtell et al., "Distributed Computation of Economic Equilibria via Bilateral Exchange" (Mar. 1997)..

Primary Examiner: Paladini; Albert W.
Assistant Examiner: Cabrera; Zoila
Attorney, Agent or Firm: Williams, Morgan & Amerson, P.C.

---

Government Interests

---

The United States Government has a paid-up license in this invention and the right in limited circumstances to require the patent owner to license others on reasonable terms as provided for by the terms of Cooperative Agreement No. 70NANB7H3041 awarded by the United States Department of Commerce, National Institute of Standards and Technology ("NIST", Advanced Technology Program ("ATP").

---

Claims

---

What is claimed:

1. A method for scheduling a resource for processing a workpiece, comprising: defining a commitment window having a kernel specifying a time period required for processing the workpiece; generating a plurality of candidate bids having candidate commitment windows within the commitment window with varying start times, end times and candidate commitment window sizes; determining a cost for each of the plurality of candidate bids; applying a flexibility discount to the cost of the candidate bid; evaluating each candidate bid in accordance with an objective function; and selecting a candidate bid for scheduling the resource based on the objective function evaluation.

2. The method of claim 1, further comprising confirming the selected candidate bid with the resource.

3. The method of claim 1, wherein determining the cost of each candidate bid further comprises: determining a committed capacity of the resource; determining a rate function for the resource as a function of the committed capacity; determining an increase in the committed capacity of the resource due to the candidate bid; determining a change in the rate function due to the increased committed capacity corresponding to the candidate bid; determining a cost change for the candidate bid due to the change in the rate function and the candidate commitment window size of the candidate bid; and determining the cost of the candidate bid as a function of the rate function and committed capacity of the resource without the candidate bid, the increase in committed capacity due to the candidate bid, and the cost change for the candidate bid.

4. The method of claim 1, wherein applying the flexibility discount further comprises: determining a ratio between the time period of the kernel and the candidate window size; and determining the flexibility discount as a function of the ratio.

5. The method of claim 4, wherein determining the flexibility discount further comprises determining the flexibility discount as an increasing convex function of the ratio.

6. The method of claim 3, wherein determining the increase in the committed capacity further comprises determining a ratio between the time period of the kernel and the candidate window size.

7. The method of claim 3, further comprising generating a modified rate function based on the committed capacity, wherein determining the change in the rate function further comprises determining a difference between the modified rate function evaluated with the increased committed capacity of the candidate bid and the modified rate function evaluated without the increased committed capacity of the candidate bid.

8. The method of claim 3, wherein determining the committed capacity of the resource further comprises determining the committed capacity based on a plurality of engagements scheduled for the resource, and the method further comprises: determining an average committed capacity of engagements within the candidate commitment window non-compatible with the candidate bid; and fixing a parameter of the rate function specifying a committed capacity of non-compatible engagements at the average committed capacity of non-compatible engagements within the candidate commitment window to generate a modified rate function.

9. The method of claim 8, wherein determining the change in the rate function further comprises: determining an average committed capacity of engagements within the candidate commitment window compatible with the candidate bid; summing the average committed capacity of compatible engagements and the increase in committed capacity due to the candidate bid; evaluating the modified rate function based on the sum to generate a first resultant; evaluating the modified rate function based on the average committed capacity of compatible engagements to generate a second resultant; and subtracting the first and second resultants to generate the change in the rate function.

10. The method of claim 3, wherein determining the cost change for the candidate bid further comprises multiplying the candidate commitment window size by the change in the rate function.

11. The method of claim 3, wherein determining the cost of the candidate bid further comprises determining a basic cost function as a function of the rate function and committed capacity of the resource excluding the candidate bid.

12. The method of claim 11, wherein C.sub.delta represents the cost change, h represents the increase in committed capacity, BCF represents the basic cost function, TS represents the start time of the candidate window, TE represents the end time of the candidate window, t represents time, and determining the cost of the candidate bid, C.sub.e, further comprises determining the cost using the formula ##EQU35##

13. The method of claim 12, further comprising multiplying a flexibility discount to the cost of the candidate bid.

14. The method of claim 1, wherein evaluating each candidate bid in accordance with the objective function further comprises: determining a cost of lateness as a function of the end time of the candidate bid; and generating a total cost as a function of the cost of lateness and the cost determined for the candidate bid.

15. The method of claim 14, wherein evaluating each candidate bid in accordance with the objective function further comprises: multiplying the cost of lateness by one of a configurable cost of lateness adjustment factor and a budget for purchasing the processing from the resource; and adding the cost determined for the candidate bid to generate the total cost.

16. The method of claim 15, wherein determining the cost of lateness further comprises: calculating a critical ratio based on the end time of the candidate commitment window; and determining the cost of lateness using a decreasing convex function of the critical ratio.

17. The method of claim 14, wherein selecting the candidate bid further comprises selecting the candidate bid having a minimum total cost.

18. The method of claim 17, further comprising confirming the selected candidate bid with the resource responsive to a budget for purchasing the processing from the resource being greater than or equal to an actual cost determined for the candidate bid based on a committed capacity of the resource at the time the bid is confirmed.

19. A system, comprising: a resource for processing a workpiece; and at least one scheduling agent configured to define a commitment window having a kernel specifying a time period required for processing the workpiece, generate a plurality of candidate bids having candidate commitment windows within the commitment window with varying start times, end times and candidate commitment window sizes, determine a cost for each of the plurality of candidate bids, apply a flexibility discount to the cost of the candidate bid, evaluate each candidate bid in accordance with an objective function, and select a candidate bid for scheduling the resource based on the objective function evaluation.

20. The system of claim 19, wherein the scheduling agent is further configured to confirm the selected candidate bid with the resource.

21. The system of claim 19, wherein the scheduling agent is further configured to determine a committed capacity of the resource, determine a rate function for the resource as a function of the committed capacity, determine an increase in the committed capacity of the resource due to the candidate bid, determine a change in the rate function due to the increased committed capacity corresponding to the candidate bid, determine a cost change for the candidate bid due to the change in the rate function and the candidate commitment window size of the candidate bid, and determine the cost of the candidate bid as a function of the rate function and committed capacity of the resource without the candidate bid, the increase in committed capacity due to the candidate bid, and the cost change for the candidate bid.

22. The system of claim 21, wherein the scheduling agent is further configured to determine a ratio between the time period of the kernel and the candidate window size, and determine the flexibility discount as a function of the ratio.

23. The system of claim 22, wherein the scheduling agent is further configured to determine the flexibility discount as an increasing convex function of the ratio.

24. The system of claim 21, wherein the scheduling agent is further configured to determine the increase in the committed capacity by determining a ratio between the time period of the kernel and the candidate window size.

25. The system of claim 21, wherein the scheduling agent is further configured to generate a modified rate function based on the committed capacity, wherein determining the change in the rate function further comprises determining a difference between the modified rate function evaluated with the increased committed capacity of the candidate bid and the modified rate function evaluated without the increased committed capacity of the candidate bid.

26. The system of claim 21, wherein the scheduling agent is further configured to determine the committed capacity based on a plurality of engagements scheduled for the resource, determine an average committed capacity of engagements within the candidate commitment window non-compatible with the candidate bid, and fix a parameter of the rate function specifying a committed capacity of non-compatible engagements at the average committed capacity of non-compatible engagements within the candidate commitment window to generate a modified rate function.

27. The system of claim 26, wherein the scheduling agent is further configured to determine an average committed capacity of engagements within the candidate commitment window compatible with the candidate bid, sum the average committed capacity of compatible engagements and the increase in committed capacity due to the candidate bid, evaluate the modified rate function based on the sum to generate a first resultant, evaluate the modified rate function based on the average committed capacity of compatible engagements to generate a second resultant, and subtract the first and second resultants to generate the change in the rate function.

28. The system of claim 21, wherein the scheduling agent is further configured to multiply the candidate commitment window size by the change in the rate function to determine the cost change for the candidate bid.

29. The system of claim 21, wherein the scheduling agent is further configured to determine a basic cost function as a function of the rate function and committed capacity of the resource excluding the candidate bid.

30. The system of claim 29, wherein C.sub.delta represents the cost change, h represents the increase in committed capacity, BCF represents the basic cost function, TS represents the start time of the candidate window, TE represents the end time of the candidate window, t represents time, and the scheduling agent is further configured to determine the cost of the candidate bid, C.sub.e, using the formula ##EQU36##

31. The system of claim 30, wherein the scheduling agent is further configured to multiply a flexibility discount to the cost of the candidate bid.

32. The system of claim 19, wherein the scheduling agent is further configured to determine a cost of lateness as a function of the end time of the candidate bid, and generate a total cost as a function of the cost of lateness and the cost determined for the candidate bid.

33. The system of claim 32, wherein the scheduling agent is further configured to multiply the cost of lateness by one of a configurable cost of lateness adjustment factor and a budget for purchasing the processing from the resource and add the cost determined for the candidate bid to generate the total cost.

34. The system of claim 33, wherein the scheduling agent is further configured to calculate a critical ratio based on the end time of the candidate commitment window and determine the cost of lateness using a decreasing convex function of the critical ratio.

35. The system of claim 32, wherein the scheduling agent is further configured to select the candidate bid having a minimum total cost.

36. The system of claim 35, wherein the scheduling agent is further configured to confirm the selected candidate bid with the resource responsive to a budget for purchasing the processing from the resource being greater than or equal to an actual cost determined for the candidate bid based on a committed capacity of the resource at the time the bid is confirmed.

37. A system, comprising: means for defining a commitment window having a kernel specifying a time period required for processing a workpiece; means for generating a plurality of candidate bids having candidate commitment windows within the commitment window with varying start times, end times and candidate commitment window sizes; means for determining a cost for each of the plurality of candidate bids; means for applying a flexibility discount to the cost of the candidate bid; means for evaluating each candidate bid in accordance with an objective function; and means for selecting a candidate bid for scheduling the resource based on the objective function evaluation.

---

Description

---

BACKGROUND OF THE INVENTION

1. Field of the Invention

This invention pertains to automated manufacturing environments, such as semiconductor manufacturing, and, more particularly, to a method and apparatus for evaluating bids for scheduling a resource.

2. Description of the Related Art

Growing technological requirements and the worldwide acceptance of sophisticated electronic devices have created an unprecedented demand for large-scale, complex, integrated circuits. Competition in the semiconductor industry requires that products be designed, manufactured, and marketed in the most efficient manner possible. This requires improvements in fabrication technology to keep pace with the rapid improvements in the electronics industry. Meeting these demands spawns many technological advances in materials and processing equipment and significantly increases the number of integrated circuit designs. These improvements also require effective utilization of computing resources and other highly sophisticated equipment to aid, not only design and fabrication, but also the scheduling, control, and automation of the manufacturing process.

Turning first to fabrication, integrated circuits, or microchips, are manufactured from modern semiconductor devices containing numerous structures or features, typically the size of a few micrometers. The features are placed in localized areas of a semiconducting substrate, and are either conductive, non-conductive, or semi-conductive (i.e., rendered conductive in defined areas with dopants). The fabrication process generally involves processing a number of wafers through a series of fabrication tools. Each fabrication tool performs one or more of four basic operations discussed more fully below. The four basic operations are performed in accordance with an overall process to finally produce the finished semiconductor devices.

Integrated circuits are manufactured from wafers of a semiconducting substrate material. Layers of materials are added, removed, and/or treated during fabrication to create the integrated, electrical circuits that make up the device. The fabrication essentially comprises the following four basic operations: layering, or adding thin layers of various materials to a wafer from which a semiconductor is produced; patterning, or removing selected portions of added layers; doping, or placing specific amounts of dopants in selected portions of the wafer through openings in the added layers; and heat treating, or heating and cooling the materials to produce desired effects in the processed wafer.

Although there are only four basic operations, they can be combined in hundreds of different ways, depending upon the particular fabrication process. See, e.g., Peter Van Zant, Microchip Fabrication A Practical Guide to Semiconductor Processing (3d Ed. 1997 McGraw-Hill Companies, Inc.) (ISBN 0-07-067250-4).

Efficient management of a facility for manufacturing products, such as semiconductor chips, requires monitoring of various aspects of the manufacturing process. For example, it is typically desirable to track the amount of raw materials on hand, the status of work-in-process and the status and availability of machines and tools at every step in the process. One of the most important decisions in controlling the manufacturing process is selecting which lot should nm on each process tool at any given time. Additionally, most machines used in the manufacturing process require scheduling of routine preventative maintenance (PM) procedures and equipment qualification (Qual) procedures, as well as other diagnostic and reconditioning procedures that must be performed on a regular basis, such that the performance of the procedures does not impede the manufacturing process itself.

One approach to this issue implements an automated "Manufacturing Execution System" (MES). An automated MES enables a user to view and manipulate, to a limited extent, the status of machines and tools, or "entities," in a manufacturing environment. In addition, an MES enables the dispatching and tracking of lots or work-in-process through the manufacturing process to enable resources to be managed in the most efficient manner. Specifically, in response to MES prompts, a user inputs requested information regarding work-in-process and entity status. For example, when a user performs a PM on a particular entity, the operator logs the performance of the PM (an "event") into an MES screen to update the information stored in the database with respect to the status of that entity. Alternatively, if an entity is to be taken down for repair or maintenance, the operator logs this information into the MES database, which then prevents use of the entity until it is subsequently logged back up to a production ready state.

Although MES systems are sufficient for tracking lots and machines, such systems suffer several deficiencies, the most obvious of which are their passive nature, lack of advance scheduling, and inability to support highly automated factory operations. Current MES systems largely depend on manufacturing personnel for monitoring factory state and initiating activities at the correct time. For example, a lot does not begin processing until a wafer fab technician (WFT) issues the appropriate MES command. And, prior to processing, a WFT must issue an MES command to retrieve the lot from the automated material handling system (AMHS) with sufficient advance planning that the lot is available at the process tool when the process tool becomes available. If the WFT does not retrieve the lot soon enough, or neglects to initiate processing at the earliest available time, the process tool becomes idle and production is adversely impacted.

These types of deficiencies in the typical automated MES emphasize the importance of the wafer fabrication technician (WFT) in the efficient operation of the manufacturing process. WETs perform many vital functions. For instance, WFTs initiate dispatching, transport, and processing as their attention and time permits. The make scheduling decisions such as whether to run an incomplete lot, as opposed to waiting for an approaching lots, or performing PM or qualification instead of processing lots. However, the presence of WFTs also inevitably introduces some inefficiencies. Typically, there may be a significant difference between the performance of the best WFT and the performance of the worst WFT. A WFT typically simultaneously monitors the processing of many tools, making it difficult to focus on an individual lot or tool. Furthermore, the size and complexity of the modern fabrication process flows makes it exceedingly difficult for a WFT to foresee and prevent downstream bottlenecks or shortages arising from upstream bottlenecks. Shift changes, rest breaks, and days off for the WFT also create inefficiencies or downtime that adversely impact the manufacturing process flow. Just as the importance of the WFT is magnified by the deficiencies of the automated MES, so are the inefficiencies of the WFT magnified by his importance.

Thus, factory control systems utilized in today's wafer fabs are passive and do not enable a high degree of automation. These systems are very dependent on wafer fab technicians and other factory staff to monitor the state of the factory, to instantaneously react to constant change, to make rapid logistical decisions and to initiate and coordinate factory control activity in a timely manner. These wafer fab technicians are agents, providing the active "glue" that is lacking in factory control systems. As a result, factory effectiveness in the highly competitive semiconductor industry is quite dependent on the availability, productivity, skill level and consistency of these human agents. Wafer fab technicians must monitor and operate a number of tools located in various bays in a fab. They are forced to multiplex across tools, bays, material handling systems and a variety of factory control systems. As a fab's production ramps and more complex processes are introduced, it is difficult to achieve the scalability required to meet the increased complexity. Wafer fab tech visibility of upstream and downstream operations, tool state, work-in-process and resource availability is limited.

However, key logistical decisions are frequently based on this limited and dated information, which is only partially provided by factory control systems. Wafer fab techs spend an inordinate amount of time interacting with systems, performing non-value added functions. Shift changes disrupt the operation of the fab as the technicians are temporarily unable to provide required monitoring and coordination. Despite the best efforts of the technicians, utilization of tools suffers, adversely impacting other key factory metrics including cycle time, inventory levels, factory output and mix. With the need for intrabay material handling to transport 12-inch wafers in new 300 mm wafer fabs, significant additional complexity is introduced. Factory control systems are not capable of providing this level of detailed scheduling and execution control.

The present invention is directed to overcoming, or at least reducing the effects of, one or more of the problems set forth above.

SUMMARY OF THE INVENTION

One aspect of the present invention is seen in a method for scheduling a resource for processing a workpiece. The method includes defining a commitment window having a kernel specifying a time period required for processing the workpiece. A plurality of candidate bids having candidate commitment windows within the commitment window with varying start times, end times and candidate commitment window sizes is generated. A cost for each of the plurality of candidate bids is determined. A flexibility discount is applied to the cost of the candidate bid. Each candidate bid is evaluated in accordance with an objective function. A candidate bid is selected for scheduling the resource based on the objective function evaluation.

Another aspect of the present invention is seen in a system including a resource for processing a workpiece and at least one scheduling agent. The scheduling agent is configured to define a commitment window having a kernel specifying a time period required for processing the workpiece, generate a plurality of candidate bids having candidate commitment windows within the commitment window with varying start times, end times and candidate commitment window sizes, determine a cost for each of the plurality of candidate bids, apply a flexibility discount to the cost of the candidate bid, evaluate each candidate bid in accordance with an objective function, and select a candidate bid for scheduling the resource based on the objective function evaluation.

BRIEF DESCRIPTION OF THE DRAWINGS

The invention may be understood by reference to the following description taken in conjunction with the accompanying drawings, in which like reference numerals identify like elements, and in which:

FIG. 1 is a diagram of a portion of one particular embodiment of a process flow constructed and operated in accordance with the present invention;

FIG. 2 is a partial block diagram illustrating selected portions of the hardware and software architectures of the computing devices in FIG. 1;

FIG. 3A is a simplified block diagram of a system including provider and consumer software agents in accordance with the present invention;

FIG. 3B is a simplified flow diagram of a method for scheduling resources that may be employed by the software agents of FIG. 3A;

FIG. 4 is a simplified block diagram illustrating interactions between specialized scheduling and processing agents adapted to schedule and control processing of workpieces, such as lots of semiconductors, through the process flow of FIG. 1;

FIGS. 5A through 5D illustrate parameterized exponential functions;

FIGS. 6A and 6B are a simplified flow diagram illustrating the overall negotiation strategy used by the lot scheduling agent of FIG. 4;

FIG. 7 is a graph of a penalty function;

FIGS. 8A-8C are graphs of exemplary engagement density curves;

FIG. 9 is a graph illustrating a rate per time unit function;

FIG. 10 is a graph illustrating a flexibility discount function;

FIG. 11 is a simplified flow diagram illustrating the computing of a basic cost function;

FIG. 12 is a diagram illustrating parameters for defining an engagement density curve;

FIG. 13 is a diagram of an engagement density curve for a process tool with multiple scheduled engagements that exceed the capacity of the process tool;

FIG. 14 is a diagram of a portion of an engagement density curve used to calculate an area under the curve;

FIGS. 15-18 illustrate the effects of shifting or changing the widths of engagements on representative engagement density curves;

FIGS. 19-21 illustrate the engagement density area that may be recovered by shrinking engagement windows;

FIG. 22 is a diagram illustrating the combining of engagements in a batching optimization; and

FIG. 23 is a diagram illustrating the combining of engagements in a setup chain optimization.

While the invention is susceptible to various modifications and alternative forms, specific embodiments thereof have been shown by way of example in the drawings and are herein described in detail. It should be understood, however, that the description herein of specific embodiments is not intended to limit the invention to the particular forms disclosed, but on the contrary, the intention is to cover all modifications, equivalents, and alternatives falling within the spirit and scope of the invention as defined by the appended claims.

DETAILED DESCRIPTION OF SPECIFIC EMBODIMENTS

Illustrative embodiments of the invention are described below. In the interest of clarity, not all features of an actual implementation are described in this specification. It will of course be appreciated that in the development of any such actual embodiment, numerous implementation-specific decisions must be made to achieve the developers' specific goals, such as compliance with system-related and business-related constraints, which may vary from one implementation to another. Moreover, it will be appreciated that such a development effort might be complex and time-consuming, but would nevertheless be a routine undertaking for those of ordinary skill in the art having the benefit of this disclosure.

FIG. 1 conceptually illustrates a portion of one particular embodiment of a process flow 100 constructed and operated in accordance with the present invention. The process flow 100 fabricates semiconductor devices. However, the invention may be applied to other types of manufacturing processes. Thus, in the process flow 100 discussed above, the lots 130 of wafers 135 may more generically referred to as "workpieces." The term workpiece may refer to one wafer or one lot of wafers. The process tools 115 and any process-operation performed thereon need not necessarily be related to the manufacture of semiconductor devices in all embodiments. However, for the sake of clarity and to further an understanding of the invention, the terminology pertaining to semiconductor fabrication shall be retained in disclosing the invention in the context of the illustrated embodiments.

The illustrated portion of the process flow 100 includes two stations 105, each station 105 including a computing device 110 communicating with a process tool 115. The stations 105 communicate with one another over communications links 120. In the illustrated embodiment, the computing devices 110 and the communications links 120 comprise a portion of a larger computing system, e.g., a network 125. The process tools 115 are shown in FIG. 1 processing lots 130 of wafers 135 that will eventually become integrated circuit devices. The process tool 115 may be adapted to process more than one of lots 130 simultaneously. Such a process tool 115 is referred to as a batching tool.

FIG. 2 depicts selected portions of the hardware and software architectures, respectively, of the computing devices 110 programmed and operated in accordance with the present invention. Some aspects of the hardware and software architecture (e.g., the individual cards, the basic input/output system (BIOS), input/output drivers, etc.) are not shown. These aspects are omitted for the sake of clarity, and so as not to obscure the present invention. As will be appreciated by those of ordinary skill in the art having the benefit of this disclosure, however, the software and hardware architectures of the computing devices 110 may include many such routine features.

In the illustrated embodiment, the computing device 110 is a workstation, employing a UNIX-based operating system 200, but the invention is not so limited. The computing device 110 may be implemented in virtually any type of electronic computing device such as a notebook computer, a desktop computer, a mini-computer, a mainframe computer, or a supercomputer. The computing device 110 may even be, in some alternative embodiments, a processor or controller embedded in the process tool 115. The invention also is not limited to UNIX-based operating systems. Alternative operating systems (e.g., Windows.TM.-based or disk operating system (DOS)-based) may also be employed. The invention is not limited by the particular implementation of the computing device 110.

The computing device 110 also includes a processor 205 communicating with storage 210 over a bus system 215. The storage 210 typically includes at least a hard disk (not shown) and random access memory (RAM) (not shown). The computing device 110 may also, in some embodiments, include removable storage such as an optical disk 230, a floppy electromagnetic disk 235, or some other form, such as a magnetic tape (not shown) or a zip disk (not shown). The computing device 110 includes a monitor 240, keyboard 245, and a mouse 250, which together, along with their associated user interface software 255 comprise a user interface 260. The user interface 260 in the illustrated embodiment is a graphical user interface (GUI), although this is not necessary to the practice of the invention.

The processor 205 may be any suitable processor known to the art. For instance, the processor may be a general purpose microprocessor or a digital signal processor (DSP). In the illustrated embodiment, the processor 205 is an Athlon.TM.32-bit processor commercially available from Advanced Micro Devices, Inc. (AMD), but the invention is not so limited. The 64-bit UltraSPARC.TM. or the 32-bit microSPARC.TM. from Sun Microsystems, or any of the Itanium.TM., Pentium.TM., or Alpha.TM.-class processors from Intel Corporation might alternatively be employed.

Each computing device 110 includes, in the illustrated embodiment, a software agent 265 residing in the storage 210. Note that the software agents 265 may reside in the process flow 100 in places other than the computing devices 110. The situs of the software agent 265 is not material to the practice of the invention. Note also that, since the situs of the software agents 265 is not material, some computing devices 110 may have multiple software agents 265 residing thereon while other computing devices 110 may not have any. An automated MES 270, such as WORKSTREAM.TM., resides on at least one computing device 110.

The computing devices 110 may also be part of a larger network 125 by a connection over the communications links 120. Exemplary computing systems in such an implementation include local area networks (LANs), wide area networks (WANs), system area networks (SANs), intranets, or even the Internet. The network 125 employs a networked client/server architecture, but alternative embodiments may employ a peer-to-peer architecture. Thus, in some alternative embodiments, the computing devices 110 may communicate directly with one another. The communications links 120 may be wireless, coaxial cable, optical fiber, or twisted wire pair links, for example. The network 125, in embodiments employing one, and the communications links 120 are implementation specific and may be implemented in any suitable manner known to the art. The network 125 may employ any suitable communications protocol known to the art, e.g. Transmission Control Protocol/Internet Protocol (TCP/IP).

Turning now to FIGS. 1 and 2, the software agents 265, collectively, are responsible for efficiently scheduling and controlling the lots 130 of wafers 135 through the fabrication process. Each process tool 115 represents a resource that may be employed for this purpose. For instance, the process tool 115 may be a fabrication tool used to fabricate some portion of the wafers 135, i.e., layer, pattern, dope, or heat treat the wafers 135. Or, the process tool 115 may be a metrology tool used to evaluate the performance of various parts of the process flow 100. Thus, the software agents 265 are capable of assessing a plurality of resources for subsequent processing of the lots 130 of wafers 135, allocating the resources represented by the process tools 115, and negotiating among themselves for the allocation of those resources for subsequent processing of the lot 130 of wafers 135.

In the illustrated embodiment, the software agents 265 are state aware, and are imbued with specific goals that they autonomously initiate behaviors to achieve. The software agents 265 are implemented as objects in an object oriented programming (OOP) environment, but the invention may be implemented using techniques that are not object oriented. Their behavior is relatively simple and is script or rules-based. The behavior is designed to achieve selected goals such as achieving an assigned lot due date, achieving a predefined level of quality, maximizing process tool utilization, and scheduling opportunistic preventive maintenance. In furtherance of these objectives, the software agents 265 interface with the MES 270 and are integrated with other existing factory control systems (not shown). As will be apparent to those skilled in the art having the benefit of this disclosure, the manner in which this interface and integration occurs is implementation specific, depending upon the particular makeup and configuration of the MES 270 and the factory control systems.

Collectively, the software agents 265 schedule ahead for each lot 130 one or more operations on a specific qualified process tool 115, including transports and required resources, as discussed further below. This includes making optimizing decisions such as running an incomplete batch, as opposed to waiting for an approaching lot 130, and scheduling opportunistic preventive maintenance or qualifications tests to meet specifications. The software agents 265 schedule activities such as initiating lot transport and processing, performing MES transactions, monitoring processing and transport, and reacting to deviations from scheduled activities or unscheduled activities. More particularly, the software agents 265 may, for instance:

schedule and initiate execution of interbay material transport required for a next lot processing engagement at a specified process tool 115;

monitor transport activity and react to deviations;

schedule and initiate automated material handling system (AMHS) intrabay transport to a reserved process tool port by a specified time;

detect process tool port carrier arrival via auto-identification or equipment event;

initiate loading, recipe download, processing, and unloading on a process tool 115 via an equipment interface;

perform MES transactions;

monitor processing activity and notify WFTs of abnormalities;

detect near completion of processing via an equipment event;

initiate AMHS intrabay transport to the nearest stocker or a nearby process tool 115;

detect carrier departure and release the port;

schedule preventive maintenance procedures and notify maintenance technicians (MTs) at the appropriate time; and

schedule qualification procedures and notify WFTs at the appropriate time.

Note that, depending on the level of implementation, a given embodiment may implement any or all of these functions, or even functions not listed above.

Referring now to FIG. 3A, in a general sense, the software agents 265 can typically be classed as "consumer agents" 305 and "provider agents" 310. Consumer agents 305 represent the interests of consumers 315, e.g., the PM procedures in performing preventative maintenance within the allowable windows or the lots 130 in advancing through the process flow 100 in a timely and efficient manner. Provider agents 310 represent the interests of providers 325, e.g., machines such as the process tool 115, in meeting the demands of consumers for processing resources in advancing the lots 130 through the process flow 100 in a timely and efficient manner. For instance, a software agent 265 representing a lot 130 of wafers 135 would be considered a "consumer" agent 305 and a software agent 265 representing a process tool 115 would be considered a "provider" agent because the process tool 115 is "providing" processing resources "consumed" by the lot 130. A software agent 265 may be classed as a provider agent 310 in one context and a consumer agent 305 in another context.

As noted above, the distinction between consumer agents 305 and provider agents 310 is particularly apt in the context of scheduling. The scheduling of actions initiated by the software agents 265 revolve around budgets, costs, and ratios associated with the processing. More particularly, to further the implementation of a negotiation protocol for allocating resources, a combination of budgets, costs, and ratios are used to implement a scheduling system. The combination is structured to encourage "desirable" behavior, e.g., meeting due dates, effective utilization of machines, etc.

Turning now to FIG. 3B, there is illustrated a method 330 practiced in accordance with the present invention. The method 330 may be practiced in a variety of embodiments and implementations, a particular one of which is disclosed below. The consumer software agents 305 and provider software agents 310 use a "contract net negotiation protocol" approach to schedule the consumers 315 for the providers 325. The consumer agents 305 negotiate with provider agents 310 to reserve access for the consumer 315 to the resources of the provider 325. This reserved access is referred to as an "engagement." In this particular embodiment, both the consumer agent 305 and the provider agent 310 schedule the engagement.

The method 330 begins by providing a budget for the consumer 315 for a particular process resource, e.g., process time on the process tool 215 it next wants to consume, as set forth in box 335. The budget can be structured to affect the operation of the process flow 300. For instance, consumers 315 having a higher priority for completing the process flow 300 may be afforded greater budgets to increase their chances of successfully acquiring the desired process resource. In general, the budget depends on the processing time of the process step, lot priority, lateness with respect to meeting its due date, and other factors. In some embodiments, a consumer 315 may provide a budget calculator to the provider 325. The budget calculator permits the provider 325 to determine the priority of the consumer 315 relative to other engagements previously booked by the provider 325.

The consumer 315 then issues, through its consumer software agent 305, a bid request for the consumer 315 to acquire the process resource, as set forth in box 340. In one implementation, the consumer software agent 305 requests bids from all eligible providers 310 on behalf of a consumer 315. When a consumer software agent 305 requests a bid, it gives the provider software agent 310 pertinent information such as: the earliest time to begin transport from the last machine; the process-operation to be scheduled; the latest completion time acceptable to the consumer 315; and the location from which the consumer 315 will be transported to the provider 310.

The provider 325 then, through its provider software agent 310, submits to the consumer 315 at least one bid responsive to the bid request, as set forth in box 345. The bid includes a cost function from which the consumer 315 may determine a cost to acquire the process resource from the provider 325. The provider 325 attempts to maximize its "profits" by adjusting the prices it offers in its bids.

An engagement includes a "commitment window" (CW), which is a time interval during which the provider 325 commits to meet the engagement. A "kernel" (k) is a time period representing the actual time required by the provider 325 to complete the task. A "working window" (WW) is a subset of the commitment window that the provider software agent 310 may use to constrain the engagement to accommodate other engagements and avoid overcommitting its resources. The provider software agent 310 may shift the edges of the working window such that it is smaller than the commitment window. If no shifting is required to accommodate other engagements, the working window remains the same size as the commitment window.

The consumer 315, through the consumer software agent 305, then selects a submitted bid in light of the end time of the candidate bid and the cost function of the provider 325, as set forth in box 350. The selection process is described in greater detail below with reference to FIGS. 6A and 6B. A particular consumer 315 might accept a more expensive bid to ensure a more timely delivery of the purchased resource.

The consumer 315 awards a contract to the provider 325 corresponding to the selected bid, as set forth in box 355, through the consumer software agent 305. However, the provider 325 typically is negotiating with several consumers 315. It is possible that the provider 325 scheduled another consumer 315 in such a manner that the cost to secure the submitted bid has increased. Thus, the provider 325, through its provider software agent 310, determines the actual cost of the bid (i.e., based on the current schedule of engagements) and accepts the contract if the consumer 315 can still afford the updated cost. The provider 325 then confirms the awarded contract, as set forth in box 360. If not, it notifies the consumer 315 who can then select a second bid or begin the bidding process all over again. The consumer 315 may maintain a schedule or calendar 320 of scheduled engagements and transport activities (i.e., to move it to the next process tool 115) to facilitate scheduling of engagements beyond the current process step.

Thus, decision-making in the process flow 300 is guided by economic forces of supply and demand. More particularly, consumer software agents 305 are designed to acquire resources more or less aggressively depending on selected factors, such as priority or lateness. Provider software agents 310 are designed to provide such resources more or less aggressively depending on a number of factors, such as the level of utilization ("congestion"). Note that these decisions can be manipulated externally though configurable curves supplied for costs and budgets on which the decisions are made. Working in concert, the consumer and provider software agents 305, 310 cooperate to advance the consumers 305 through the process flow 300 in a timely and efficient manner.

FIG. 4 depicts a portion of a semiconductor fabrication process flow 400 in which these concepts are further illustrated. The process flow 400 implements the contract net negotiation protocol discussed above relative to FIG. 3A and FIG. 3B in one particular embodiment thereof. More particularly, the process flow 400 includes:

a lot scheduling agent 405, which is a consumer software agent representing the lot 130 for scheduling purposes;

a machine scheduling agent 410, which is both a consumer and a provider software agent, depending on the context in which it is operating, representing the process tool 115 for scheduling purposes;

a machine processing agent 415, which is a provider software agent that takes actions to initiate activities scheduled by the machine scheduling agent 410; and

a resource scheduling agent 417, which is a provider software agent representing a resource 420 that may be needed by the process tool 115 to perform the scheduled activity.

The lot scheduling agent 405 tries to minimize costs while staying on schedule. The machine scheduling agent 410 tries to optimize tool utilization while maximizing profits.

The lot 130 and resource 420 may also have corresponding processing agents (not shown) to whom the scheduling agents 405, 417 pass control when it is time for a scheduled activity to begin. Note that resource scheduling agents 417 can represent other types of resources, e.g., dummy wafers, empty cassettes, wafer fabrication technicians (WFT), maintenance technicians (MT), etc.

The agents 405, 410, 415, 417 employ negotiation techniques that apply market dynamics to scheduling decisions. These decisions are generally influenced by a schedule of prices for a variable that encourages some assignments over others. In the illustrated embodiment, such price schedules are generated from a toolkit of parameterized exponential functions (PEFs). In some cases, the parameters of an individual function can be adjusted to generate the desired schedule, while other applications employ a sum of these functions. The following discussion of the parameterized exponential function toolkit is referenced in the subsequent detailed discussions that follow.

In general, exponential functions can be characterized as Increasing vs. Decreasing (i.e., inc or dec), and as Concave vs. Convex (i.e., C or V). FIGS. 5A through 5D illustrate the four possible combinations of these characteristics. Each of these functions is a function of one variable, x. These functions may be tuned using four parameters:

The steepness, s, determines how quickly the function climbs or falls.

The x-reference, x.sub.0, and y-preference, y.sub.0, define a point the curve must pass through (x.sub.0, y.sub.0).

The asymptote, a, shifts the line y=a that the curve approaches as it flattens out. For a convex cu