Method and apparatus for automatically generating schedules for wafer processing within a multichamber semiconductor wafer processing tool

Abstract

A method and apparatus for producing schedules for a wafer in a multichamber semiconductor wafer processing tool comprising the steps of providing a trace defining a series of chambers that are visited by a wafer as the wafer is processed by the tool; initializing a sequence generator with a vertex defining initial wafer positioning within the tool; generating all successor vertices to produce a series of vectors interconnecting the vertices that, when taken together produce a cycle that represents a schedule. All the possible schedules are analyzed to determine a schedule that produces the highest throughput of all the schedules.

What is claimed is:  
     
       1. A method of producing schedules for processing a wafer in a multichamber semiconductor wafer processing tool comprising the steps of: 
       (a) providing a trace defining a series of chambers that are visited by a wafer as the wafer is processed by the tool;  
       (b) initializing a sequence generator with an initial digraph vertex defining an initial wafer positioning with the tool; and  
       (c) generating vectors that represent all valid wafer movements related to the initial digraph vertex that lead to valid successor vertices, where said vectors and vertices, taken together, form a digraph that represents at least one schedule for processing a wafer.  
     
     
       2. The method of  claim 1  wherein combinations of vertices and vectors form cycles in the digraph, where each cycle represents a schedule. 
     
     
       3. The method of  claim 1  further comprising the steps of: 
       (d) backtracking through a set of vertices and applying step (c) to a prior vertex to produce further successor vertices and vectors; and  
       (e) stopping said backtracking when all possible cycles are produced that represent all possible valid schedules.  
     
     
       4. The method of  claim 3  further comprising the step of: 
       (f) identifying at least one schedule in all possible valid schedules that provides an optimal throughput for a given trace.  
     
     
       5. The method of  claim 4  wherein said identifying step (f) further comprises the step of computing the throughput for each and every schedule of said all possible schedules and selecting an optimum schedule for the trace which produces the highest throughput. 
     
     
       6. The method of  claim 3  wherein said backtracking step (d) further comprises the steps of: 
       (a′) initializing a vertex;  
       (b′) identifying an unused successor vertex;  
       (c′) appending the unused successor vertex to a path;  
       (d′) querying whether the last vertex is the same as a previous vertex in the path and, if not, repeat steps (b′), (c′), and (d′) until the last vertex of the path is the same as some previous vertex in the path;  
       (e′) storing the path as a cycle;  
       (f′) querying whether any other cycles remain and, if not, stopping; otherwise, proceeding to step (g′);  
       (g′) removing the last vertex of the cycle;  
       (h′) querying whether there is an unused successor vertex and, if there are no unused successor vertices, repeating steps (f′), (g′) and (h′) until there is an unused successor vertex;  
       (i′) appending the unused successor vertex to a new path, marking the successor vertex as used; and  
       (k′) returning to step (b′).  
     
     
       7. The method of  claim 6  wherein successor vertices are defined by successor generation rules that are prescribed by wafer processing parameters. 
     
     
       8. The method of  claim 6  wherein successor vertices are generated with regard to transport-robot positioning. 
     
     
       9. Apparatus for producing schedules for processing a wafer in a multichamber semiconductor wafer processing tool, having a trace defining a series of chambers that are visited by a wafer as the wafer is processed by the tool, said apparatus comprising: 
       a sequence generator, being initialized with an initial value of a vertex defining an initial wafer positioning within the tool, for generating values of said vertex that represent all valid successor wafer positions related to the initial vertex, where said vertices and vectors connecting the vertices, taken together, form at least one cycle that represents a schedule for processing a wafer.  
     
     
       10. The apparatus of  claim 9  further comprising a throughput model, coupled to said sequence generator, for computing a throughput value for each possible schedule in said all possible schedules. 
     
     
       11. The apparatus of  claim 10  further comprising means for identifying at least one schedule that has the largest throughput value. 
     
     
       12. Apparatus for producing schedules for processing a wafer in a multichamber semiconductor wafer processing tool, having a trace defining a series of chambers that are visited by a wafer as the wafer is processed by the tool, said apparatus comprising: 
       (a) means for providing a trace defining a series of chambers that are visited by a wafer as the wafer is processed by the tool;  
       (b) means for initializing a sequence generator with an initial digraph vertex defining an initial wafer positioning with the tool; and  
       (c) means for generating vectors that represent all valid wafer movements related to the initial digraph vertex that lead to valid successor vertices, where said vectors and vertices, taken together, form a cycle that represents at least one schedule for processing a wafer.  
     
     
       13. The apparatus of  claim 12  wherein combinations of vertices and vectors form cycles in the digraph, where each cycle represents a schedule. 
     
     
       14. The apparatus of  claim 12  further comprising: 
       (d) means for backtracking through a set of vertices and applying said means for generating vectors to a prior vertex to produce further successor vertices and vectors; and  
       (e) means for stopping said backtracking when all possible cycles are produced that represent all possible valid schedules.  
     
     
       15. A computer readable memory containing software that, when executed by a processor, causes a sequence generator to perform a method of producing schedules for processing a wafer in a multichamber semiconductor wafer processing tool comprising the steps of: 
       (a) providing a trace defining a series of chambers that are visited by a wafer as the wafer is processed by the tool;  
       (b) initializing a sequence generator with an initial digraph vertex defining an initial wafer positioning with the tool; and  
       (c) generating vectors that represent all valid wafer movements related to the initial digraph vertex that lead to valid successor vertices, where said vectors and vertices, taken together, form a digraph that represents at least one schedule for processing a wafer.  
     
     
       16. The method of  claim 15  wherein combinations of vertices and vectors form cycles in the digraph, where each cycle represents a schedule. 
     
     
       17. The method of  claim 15  further comprising the steps of: 
       (d) backtracking through a set of vertices and applying step (c) to a prior vertex to produce further successor vertices and vectors; and  
       (e) stopping said backtracking when all possible cycles are produced that represent all possible valid schedules.  
     
     
       18. The method of  claim 17  further comprising the step of: 
       (f) identifying at least one schedule in all possible valid schedules that provides an optimal throughput for a given trace.  
     
     
       19. The method of  claim 18  wherein said identifying step (f) further comprises the step of computing the throughput for each and every schedule of said all possible schedules and selecting an optimum schedule for the trace which produces the highest throughput. 
     
     
       20. The method of  claim 17  wherein said backtracking step (d) further comprises the steps of: 
       (a′) initializing a vertex;  
       (b′) identifying an unused successor vertex;  
       (c′) appending the unused successor vertex to a path;  
       (d′) querying whether the last vertex is the same as a previous vertex in the path and, if not, repeat steps (b′), (c′), and (d′) until the last vertex of the path is the same as some previous vertex in the path;  
       (e′) storing the path as a cycle;  
       (f′) querying whether any other cycles remain and, if not, stopping; otherwise, proceeding to step (g′);  
       (g′) removing the last vertex of the cycle;  
       (h′) querying whether there is an unused successor vertex and, if there are no unused successor vertices, repeating steps (f′), (g′) and (h′) until there is an unused successor vertex;  
       (i′) appending the unused successor vertex to a new path, marking the successor vertex as used; and  
       (j′) returning to step (b′).  
     
     
       21. The method of  claim 20  wherein successor vertices are defined by successor generation rules that are implied by a wafer processing sequence. 
     
     
       22. The method of  claim 20  wherein successor vertices are generated with regard to transport-robot positioning.