United States Patent (19)
`Gupta et al.
`
`(11)
`(45)
`
`Patent Number:
`Date of Patent:
`
`4,888,692
`Dec. 19, 1989
`
`(54)
`(75)
`
`(73)
`
`(21)
`22)
`
`REAL-TIME SCHEDULING SYSTEM
`Subhash Gupta; Sanjiv S. Siduh, both
`Inventors:
`of Dallas; Frank Vlach, Plano, all of
`Tex.
`Texas Instruments Incorporated,
`Dallas, Tex.
`273,643
`Nov. 10, 1988
`
`Appl. No.:
`File:
`
`Assignee:
`
`(63)
`
`(51)
`(52)
`(58)
`
`(56)
`
`Related U.S. Application Data
`Continuation of Ser. No. 895,061, Aug. 11, 1986, aban
`doned.
`Int. Cl." .............................................. G06F 15/46
`w8 364/402; 364/468
`Field of Search ............... 364/478, 156, 468, 152,
`364/402, 153
`
`References Cited
`U.S. PATENT DOCUMENTS
`3,703,725 1/1972 Gomersall et al. ............. 364/468 X
`3,845,286 10/1974 Aronstein et al. .
`... 364/468 X
`3,891,836 6/1975 Lee .................................. 264/156 X
`
`4,548,023 3/1987 Powell ............................ 364/156 X
`4,607,325 8/1986 Horn ............................... 364/153 X
`4,628,434 12/1986 Tashiro et al. .................. 364/402 X
`4,628,435 12/1986 Tashiro et al. .................. 364/468 X
`OTHER PUBLICATIONS
`Goldratt, Eli, et al., The Race, North River Press
`Croon-on-Hudson, N.Y., 1986, p. 125-141.
`Primary Examiner-Clark A. Jablon
`Attorney, Agent, or Firm-James T. Comfort; N. Rhys.
`Merrett; Melvin Sharp
`57
`ABSTRACT
`A system for scheduling the operation of interrelated
`machines which perform a process flow. A global defi
`nition of the system is made once, and each machine has
`an individual profile describing its local interaction with
`the system. Local scheduling decisions for each ma
`chine are made based on that machines individual pro
`file and the state of the manufacturing facility at the
`time a decision is needed. Operation of the individual
`machines is controlled by the local scheduling decisions
`made therefor.
`
`7 Claims, 7 Drawing Sheets
`
`DETERMINE PARAMETERS
`OF MANU FACTURING
`FACLTY
`
`
`
`CALCULATE MACHINE
`AND PROCESS
`PARAMETERS
`
`
`
`DENT FY CRITICAL
`MACH NES
`
`CREATE MACHINE
`PROFES
`
`
`
`
`
`CREATE PROCESS
`PROF LES
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1008, IPR2022-00681, Pg. 1
`
`

`

`U.S. Patent Dec. 19, 1989
`
`Sheet 1 of 7
`
`4,888,692
`
`
`
`PROCESS
`
`MACHINE
`
`PROCESS-NAME
`PROCESS-NUMBER
`PRECEDING-PROCESS
`NEXT-PROCESS
`WHICH-MACH NES
`REWORK-POINTER
`REWORK - PROCESS
`PROCESS-TME
`CONSTRANT-STARTER
`CONSTRANT-MEMBER
`USAGE
`QUEUE
`
`-
`
`Afg.2
`
`MACHINE-NUMBER
`MACH NE-NAME
`MACH NE-TYPE
`PROCESSES
`CAPACTY
`SET-UP-TIME
`SCHEDUED - DOWNTM E-FREQUECY
`SCHEDULED-DOWNTIME-LENGTH
`MTBF
`MTTR
`T
`MTA
`USAGE
`AVAL BILITY
`S DES
`LOTS-DONE - ON - CURRENT-PROCESS
`LOTS-DONE - ON - CURRENT-SIDE
`LAST-LOADED-AT
`NEXT-AVAILABLE-A
`NEXT-MANTENANCE-T ME
`DONG
`SCHEDULING-TYPE
`WAITING-T ME
`OPTIMIZNG 7
`CHECKED - UP-TO
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1008, IPR2022-00681, Pg. 2
`
`

`

`U.S. Patent Dec. 19, 1989
`
`Sheet 2 of 7
`
`. 4,888,692
`
`FROM
`
`SET UP
`TIMES
`
`TO
`
`P2
`
`1O
`
`P3
`
`5
`
`15
`
`O
`o
`(INTIME STEPS)
`A77.4
`
`
`
`SAFE-T ME-CONSTRAINT
`
`BEGINNING-PROCESS
`END-PROCESS
`PROCESSES
`LENGTH
`GREATEST-FROCESS-TIME
`CONTROLLING-PROCESS
`FME-TO-CONTROLLING-PROCESS
`NEXT-AVAILABLE-TIMES
`LOT-NUMBERS
`OPT Mi ZNG 7
`Avg. 5
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1008, IPR2022-00681, Pg. 3
`
`

`

`U.S. Patent Dec. 19, 1989
`
`Sheet 3 of 7
`
`4,888,692
`
`DETERM NE PARAMETERS
`OF MANUFACTURING
`FACLTY
`
`
`
`
`
`
`
`CAL CULATE MACH NE
`AND PROCESS
`PARAMETERS
`
`
`
`DENTIFY CRITICAL
`MACH NES
`
`CREATE MACHINE
`PROF LES
`
`
`
`CREATE PROCESS
`PROF LES
`Afg. 6
`
`CONSTRANT
`STARTER
`YES, NO
`
`DETERMIN E MACHINE
`CAPACTY
`
`CONSTRANT
`MEMBER
`
`
`
`DETERMINE
`PROCESSES DONE
`
`
`
`DETERMINE
`AVAILABILITY
`
`
`
`
`
`CAL CULATE
`MACHINE
`USAGE
`Afg. 7
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1008, IPR2022-00681, Pg. 4
`
`

`

`US. Patent
`Dec. 19, 1989
`U.S. Patent Dec. 19, 1989
`
`
`
`4,888,692
`
`Sheet 4 of 7
`Sheet 4 of 7
`
`4,888,692
`
`Petitioner STMICROELECTRONICS, INC.,
`|
`Ex. 1008, IPR2022-00681, Pg. 5
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1008, IPR2022-00681, Pg. 5
`
`

`

`US. Patent
`Dec. 19, 1989
`U.S. Patent Dec. 19, 1989
`
`Sheet 5 of 7
`Sheet 5 of 7
`
`4,888,692
`4,888,692
`
`Fig.11
`
`
`
`ARRIVALMQUEUEP10
`
`Cl
`(s)(S(X) is
`X
`
`
`
`LOTSQUEUEP4
`
`QUEUEP18
`
`Petitioner STMICROELECTRONICS,INC.,
`Ex. 1008, IPR2022-00681, Pg. 6
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1008, IPR2022-00681, Pg. 6
`
`

`

`U.S. Patent Dec. 19, 1989
`
`Sheet 6 of 7
`
`4,888,692
`
`
`
`A77. /3
`FROM
`M1 P2O P8O
`P2O -
`O
`P4O 2O
`-
`
`TO
`
`SET UP T MES
`A77. /4
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1008, IPR2022-00681, Pg. 7
`
`

`

`US. Patent
`
`Dec. 19, 1989
`
`Sheet 7 of 7
`
`4,888,692
`
`Q—@)-@)—@
`
`Fig.15
`
`3
`
`+21) ok
`BUCKET 0{2.
`2kLI
`
`0
`
`1023
`
`SLIDING
`
`k=1{0
`
`42BITS
`
`
`
`
`
`40BITS10BITS410BITS.
`
`Fig.16
`
`
`
`SORTEDUNSORTED
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1008, IPR2022-00681, Pg. 8
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1008, IPR2022-00681, Pg. 8
`
`

`

`1.
`
`5
`
`0
`
`15
`
`REAL-TIME SCHEDULING SYSTEM
`This application is a continuation, of application Ser.
`No. 895,061, filed 8/11/86.
`BACKGROUND AND SUMMARY OF THE
`INVENTION
`The present invention relates to automated schedul
`ing and planning systems.
`Resource planning is used extensively by industry. It
`is especially useful in the manufacturing sector, where
`careful scheduling of a manufacturing facility is neces
`sary in order for such plants to be efficient. The flow of
`raw and partially finished goods, and scheduling of
`work on the various available machines, is a significant
`problem in large manufacturing facilities. A few exan
`ples of manufacturing facilities which are especially
`sensitivie to scheduling problems include semiconduc
`tor fabrication facilities (front-ends), job shops, and
`20
`plants making automobiles and heavy machinery.
`The number of details and computations involved in
`completely scheduling a large manufacturing facility
`are enormous. No exact mathematical solution can, in
`general, be generated for such a facility. This is primar
`25
`ily because the facility does not operate in an ideal man
`ner. Unforeseeable events are very common, including
`machine breakages, bad work which must be reworked
`or thrown away, and delays in moving material within
`the facility. These minute by minute events can have an
`impact on the overall operation of the facility and the
`precise nature of such impact cannot generally be deter
`mined in advance.
`Many different schemes are currently in use for
`scheduling factory systems. These include the simplest
`scheduling system, that of no preplanned scheduling at
`all. In some factories, a work piece simply moves from
`machine to machine under the experienced guidance of
`the operator, and no particular pre-planning is made. In
`slightly more sophisticated systems, various rules of
`40
`thumb are used by operators and process experts to
`control the flow of material through the plant. Some of
`these rules are very simple, such as FIFO (first-in first
`out). These rule of thumb decisions are made at a local
`ized level. That is, the operator or expert will decide
`45
`which workpiece should next go onto a particular ma
`chine based on the list of those workpieces currently
`available for the machine.
`A more sophisticated system includes coordinated
`plant wide planning at some level. This is generally
`done by globally defining the manufacturing process
`and studying the interrelation between the various sub
`processes therein. Such plant wide planning typically
`includes the identification of trouble spots such as bot
`tlenecks in the overall process flow. An example of a
`55
`state-of-the-art system would be OPT (Optimized Pro
`duction Technology) which has been used for modeling
`and planning of manufacturing facilities since approxi
`mately 1979. The general theory of OPT is that plant
`capacity is determined by one or a small number of
`60
`bottleneck processes. The overall strategy is then to
`ensure that the bottleneck processes are kept constantly
`busy by ensuring that queues are maintained in front of
`them. Desired work in process inventory levels at key
`points throughout the plant are determined at the global
`65
`planning stage, and these desired values are compared
`to those which actually occur to determine the operat
`ing conditions within the plant.
`
`4,888,692
`2
`Current sophisticated scheduling procedures gener
`ally begin with the creation of a global plan which
`outlines the overall characteristics of the manufacturing
`facility. Based on the current status of the facility, in
`cluding such information as identification of work in
`process and machines which are down for repair, a
`general plan is made for some future time period. This
`plan will include directives such as "begin work on
`some number of identified items each hour for the next
`eight hours." Running a global plan periodically can be
`referred to as batch processing.
`Batch processing of the global plan does not allow
`quick or easy response to changing conditions. If plant
`conditions change, such as a major piece of machinery
`going off-line for repair, the entire global plan must be
`recalculated. Such global plans do have the advantage
`that they take into account in the relationship between
`various parts of the manufacturing process, but they are
`relatively inflexible and can only be applied to broad
`concepts. Decision making at the level of a particular
`machine must still be done using rules of thumb.
`Even is sophisticated systems, there is little interac
`tion between the global plan and local decision making
`process. The global plan cannot comprehend the effect
`of breakage of a particular machine in advance. Local
`decision making, that is, which work to load on which
`machine and in which order is generally done by rules
`of thumb and cannot comprehend the effect of a partic
`ular action on overall plant operation. Planning is done
`only periodically at the global level, and often incorrect
`or inaccurate rules of thumb constitute the entire deci
`sion making process at a local level.
`It would be desirable for a scheduling system to com
`prehend a global planning strategy combined with intel
`ligent local decision making which considers the effect
`of local decisions elsewhere within the manufacturing
`process. It would be further desirable that such system
`be able to react to the numerous uncontrollable events
`which occur during the manufacturing process.
`Therefore, a scheduling system includes a global,
`steady-state model of the entire manufacturing process.
`This global calculation is done one time and recalcu
`lated only when there is a major change in process flow
`definition or machine availability. This global plan gen
`erates parameters which are used to control local deci
`sion making strategies. The local strategies are applied
`to each machine in the manufacturing facility, and are
`relatively simple. Based upon the parameters extracted
`from the global definition, and information regarding
`the current state of the neighborhood of the particular
`machine, local decisions can be made on a real time
`basis. Special decision making strategies may be used by
`machines which are identified as critical to the manufac
`turing process flow.
`The novel features which characterize the present
`invention are defined by the appended claims. The fore
`going and other objects and advantages of the present
`invention will hereafter appear, and for purposed of
`illustration, but not of limitation, a preferred embodi
`ment is shown in the accompanying drawings.
`BRIEF DESCRIPTION OF THE DRAWINGS
`FIG. 1 illustrates a sample process flow, including a
`rework loop;
`FIG. 2 illustrates a Process data structure;
`FIG. 3 illustrates a Machine data structure;
`FIG. 4 is a setup time matrix for a machine having
`sides;
`
`30
`
`35
`
`50
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1008, IPR2022-00681, Pg. 9
`
`

`

`5
`
`15
`
`20
`
`3
`FIG. 5 is a safe time constraint data structure;
`FIG. 6 is a flowchart of a portion of the global plan
`ning process;
`FIG. 7 is a flowchart illustrating another portion of
`the global planning process;
`FIG. 8 is an illustration of a portion of a process flow
`near a large capacity machine;
`FIG. 9 illustrates a portion of a process flow for a
`multiple process machine;
`FIG. 10 illustrates a portion of a process flow for
`10
`multiple process machines operating on multiple ma
`chine processes;
`FIG. 11 is a timing diagram for the process flow of
`FIG. 10;
`FIG. 12 is a portion of a process flow illustrating a
`bottleneck machine;
`FIG. 13 illustrates a different bottleneck machine
`situation;
`FIG. 14 is a chart of setup times for the process flow
`of FIG. 13;
`FIG. 15 illustrates a process flow utilizing a negative
`request signal; and
`FIG. 16 illustrates a preferred calendar mechanism.
`DESCRIPTION OF THE PREFERRED
`25
`EMBODIMENT
`The following description of the preferred embodi
`ment includes detailed examples as well as the general
`approaches used in making a scheduling system. The
`description is broken into 4 major areas: a general de
`30
`scription of a factory system, including definitions of
`terms found elsewhere; the global (steady-state) plan
`ning process; local planning and optimization; and a
`preferred calendar mechanism for use by the scheduler.
`It is understood that particular references and descrip
`35
`tions are not intended to limit the scope of the Claims to
`the details shown therein, but are for illustrative pur
`poses.
`DESCRIPTION OF THE FACTORY SYSTEM
`The scheduling system is itself constrained by the
`nature of the factory to be controlled. It must be able to
`handle special situations which occur in the factory,
`such as relationships between certain machines. Many
`relationships which are found in factories and other
`45
`systems which can be controlled by a scheduler are
`similar, and will be the same as those which will now be
`described.
`The preferred scheduling system will be described
`with relation to a front-end manufacturing facility for
`integrated circuits. This type of manufacturing facility
`is sufficiently complex to illustrate many features of the
`scheduling system. Other types of manufacturing facili
`ties will have different specific machine types and other
`considerations, but most will be clearly adaptable from
`the described system.
`The scheduling system will be described with respect
`to a front end which is highly automated, but automa
`tion is not a necessary feature for its use. Commands
`which are made to machines and controllers in the
`automated system can just as easily be made to human
`operators running the machines. As will be described,
`most of the control functions will be handled directly
`by the scheduling system, but it is a straightfoward task
`to have some of these functions handled by the ma
`65
`chines themselves if they are capable of doing so.
`The period of time which will be used herein is called
`the time step. A time step is preferably 0.1 hours, or 6
`
`4,888,692
`4.
`minutes. All times used by the scheduler are expressed
`in time steps, and all absolute times, such as the pre
`dicted time for an event, are expressed as a number of
`time steps from some arbitrary beginning. Thus, clock
`time is not used, but there is a simple correlation be
`tween actual time and time indicated by the time step
`Count.
`The procedure by which a semiconductor slice is
`transformed into integrated circuits can be conceptual
`ized as a series of discrete process steps. These process
`steps are independent of the machines actually located
`on the factory floor. These process steps are the func
`tional description of what actually happens to the slices
`at each stage of manufacture. For example, a short
`series of process steps might be: apply photoresist, pat
`tern photoresist, develop photoresist, inspect, bake pho
`toresist. These process steps are the atomic elements of
`the scheduling plan; each is an indivisible action which
`occurs at a single place and over a fixed, unbroken
`period of time. A typical front end process will include
`several hundred such process steps. In addition, multi
`ple process flows may operate in one facility simulta
`neously, such as when a front end has several product
`lines. Each product line will have different process
`steps for each stage of manufacturing. Even though
`there may be much similarity between two different
`process flows, for simplicity it is preferable that each
`step of each process be uniquely identified. The fact that
`a single machine may perform a similar step for each
`process flow causes no confusion, as will be explained
`below.
`The process steps can be visualized as a long string of
`events which operate to transform a bare silicon slice at
`the first process step to finished integrated circuits at
`the last process step. As far as a front-end is concerned,
`the finished product is usually a semiconductor slice
`having fully formed integrated circuits thereon. The
`individual circuits are separated and packaged else
`where.
`The string of process steps is not always a single
`string of events occuring in a fixed order. It is some
`times necessary to rework some slices at various stages
`of the process. For example, if for some reason a photo
`resist patterning step did not occur properly, it is neces
`sary to remove all of the resist, clean the slice, reapply
`photoresist, and redo the patterning step. This is re
`ferred to as a rework loop, and, on a schematic diagram
`of the manufacturing process, appears as a small loop of
`process steps off to one side of the main process flow.
`Rework loops are not available for all types of process
`ing; for example, a metal workpiece which has been
`incorrectly drilled may not be salvagable.
`FIG. 1 shows a very short process flow for an imagi
`nary front end. Process steps are identified by P, so the
`main flow has process steps P1-P7. A single rework
`loop is shown containing process steps P8-P11.
`A process step has several important properties. The
`most important of these are collected in a process data
`structure such as shown in FIG. 2. The process must be
`uniquely identified, preferably by a PROCESS-NAME
`and PROCESS-NUMBER. The preceding and follow
`ing processes are identified in PRECEDING-PROC
`ESS and NEXT-PROCESS. A list of machines that
`perform this process is included. If this process is a
`rework decision point, that is, a check or inspection
`process that might cause slices to branch into a rework
`loop as described above, a pointer to the start of the
`rework loop is kept. This pointer is nil if the process
`
`50
`
`55
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1008, IPR2022-00681, Pg. 10
`
`

`

`4,888,692
`6
`5
`nance, plant shutdowns, and other predictable events.
`step is not a rework decision point. If this process is part
`Mean time between failure (MTBF) and mean time to
`of a rework sequence, that rework sequence is identi
`repair (MTTR) information is also included. This infor
`fied. The other data contained in the structure of FIG.
`mation helps provide statistical information on the ma
`2 will be described later.
`chine's availability. Related to MTBF and MTTB infor
`The basic unit of material will be referred to as the
`mation is nean time between assists (MTBA) and mean
`lot. In a semiconductor front end, a lot is a group of
`time to assist (MTTA). An assist is a very short and
`slices which are processed together. A lot typically
`simple fix that doesn't qualify as a repair, and doesn't
`consists of 24 slices. Most machines used in the front
`require a major recalculation of other machine's opera
`end operate on some number of lots, which in this case
`tion. An assist would typically be something that could
`is a multiple of 24. Machine capacity will be referred to
`be repaired in less than one time step by a single opera
`by lot size, so that a 4 lot machine can handle 96 slices
`simultaneously in the present description. Of course,
`tor. MTBA and MTTA information is also used for
`statistical availability calculations.
`lots may be of other sizes if desired. Also, in many man
`USAGE for a machine is an indicator of how much
`ufacturing facilities, individual items (such as a metal
`of the time a machine actually processes each lots as it
`ingot) would be the basic unit of material. The lot is
`15
`goes through the entire process flow, adjusted for avail
`considered to be a single atomic unit, in that operations
`ability. A high usage indicates that the machine spends
`on partial lots are not allowed.
`more time processing each lot than machines having
`As stated above, process steps are independent from
`low usage. If the manufacturing facility is operating at
`the actual machines on the factory floor. Several ma
`or near maximum capacity, machines having a high
`chines are often used for a single process step. These
`20
`usage will be nearly always busy. Machines having a
`machines may not be identical. Additionally, a single
`high usage are referred to as bottlenecks, and are
`machine could be used for more than one process step.
`For example, a machine for applying photoresist can be
`treated in more detail in the discussion of global plant
`used for any process step that requires application of
`optimization. Low usage machines are idle more of the
`time. Typical manufacturing operations are fairly
`resist. If a process flow requires 4 applications of resist,
`25
`sparse, that is, a large number of the machines have a
`and there is only one machine for the job, that machine
`is actually used in four distinct process steps. A typical
`moderate to low usage factor. A term related to usage is
`application might have 8 identical photoresist applica
`utilization, which is a percentage indicating how much
`tion machines, ten normal process steps for applying
`of the time a machine is actually processing lots. If the
`resist, and ten rework process steps for applying resist.
`facility is operating at or near maximum capacity, ma
`Each process may have access to each machine, so that
`chines having the highest usage numbers will also have
`nearly 100% utilization. If the facility is operating at,
`each process thinks that it has 8 machines to choose
`from whenever a lot passes through that process. How
`for example, 50% of maximum capacity, the bottleneck
`machines will have a utilization of approximately 50%.
`ever, there will be contention for the machines by the
`various processes, so that, on the average, each process
`The usage number is constant regardless of current
`35
`has access to each machine for only its proportional
`plant output.
`share of the time. For example, in the case of.8 ma-.
`The AVAILABILITY of a machine is an indication
`chines, 10 process steps, and 10 rework process steps, it
`of how much of the time the machine is operational. A
`may be that a rework sequence needs to be done on the
`machine which breaks down often, or takes a long time
`average of 1 time in 10. Every normal process step will
`to repair, has a low availability factor.
`have the same utilization because every lot must go
`The next item shown in FIG. 3 is the SIDES itern.
`through every step, while the rework steps will, on the
`The concept of sides is an illustration of the types of
`average, have only one-tenth the utilization of the nor
`complex interactions which occur between the con
`mal steps.
`cepts of processes and the machines which perform
`Each machine also has an associated data structure,
`them. A side is a grouping of processes on which a
`such as shown in FIG. 3. This structure includes a
`machine can operate simultaneously. An example of
`unique machine number and name for each machine,
`such a machine is shown in Table 1. The machine in this
`and the machine's type and the processes in which it is
`example can handle 4 lots simultaneously, and is used
`involved. The capacity of the machine is expressed in
`for (hypothetical) processes 4, 12, 35, 48, and 62. Pro
`number of lots.
`cesses 4, 12, and 62 are short, low temperature bake
`The structure for each machine has a pointer labelled
`steps, while steps 35 and 48 are high temperature bakes.
`SET-UP-TIME, which points to a series of tables, each
`Thus, lots from steps 4, 12 and 62 form a side, and steps
`table corresponding to one machine. When a machine
`35 and 48 form a side.
`changes over from one process to another, there may be
`TABLE 1
`some machine setup which must be done. This setup
`55
`time will be added to the total job time when it is neces
`Processes
`sary. The setup time may be different for each pair of
`4.
`processes moved from and to, so a setup time matrix
`12
`35
`such as that shown in FIG. 4 is used by the scheduler.
`48
`This matrix is for a machine which does 3 different
`62
`processes, and shows the setup time to be added to the
`job time whenever moving from any process to any
`process. Setup times are shown in time steps as de
`scribed above.
`Each machine also has information showing its
`scheduled downtime. This includes both the frequency
`and expected length of such downtimes. Scheduled
`downtimes are those required for preventive mainte
`
`This machine can process any mix of lots from one
`side at a time. Lots from the two sides cannot be mixed,
`and there may be a setup time associated with changing
`from the process of one side to that of the other. This
`side information allows the machine to operate much
`more efficiently in many instances, because it need not
`
`MACHINE M
`
`Description
`low temp bake
`low temp bake
`high temp bake
`high temp bake
`low temp bake
`
`10
`
`30
`
`45
`
`50
`
`60
`
`65
`
`Petitioner STMICROELECTRONICS, INC.,
`Ex. 1008, IPR2022-00681, Pg. 11
`
`

`

`5
`
`10
`
`4,888,692
`7
`8
`wait for four lots of a single process to arrive in its input
`and the first step of the constraint is the constraint
`queue before it can process a full load. This has the
`starter. Membership in a constraint, or being a con
`effect of increasing the percentage of the time that M1
`straint starter, is indicated in the process data structure
`operates full (4 lots), as well as minimizing the average
`(FIG. 2).
`amount of time that lots wait in the queue.
`The timing of the constraint is controlled by its slow
`The remaining items in the data structure of FIG. 3
`est members. For example, if one constraint member is
`are related to the dynamic operation of the scheduler,
`a process that is one lot wide and take 10 time steps to
`rather than the steady-state structure of the machine as
`complete, and there is only one machine to do that
`do the above described data items. The information
`process, only one lot can pass through the constraint
`concerning lots done on the current process and side are
`every 10 time steps regardless of the speed and capacity
`used in the local decision making process, or local opti
`of the remaining members. Thus, when load decisions
`mization, of the machines as will be described under
`are made for the process starter, it is necessary to know
`that section. The LAST-LOADED-AT and NEXT
`the characteristics of all processes in the constraint.
`AVAILABLE-AT items are used to determine when
`A separate data structure is kept for each constraint.
`the machine will be available to accept the next incon
`15
`Such a structure is shown in FIG. 5. This structure
`ing load. The NEXT-AVAILABLE-AT item also indi
`indicates the beginning and end processes, lists the ac
`cates the expected time that a machine will be returned
`tual processes by number, and gives the total processing
`to service if it is currently down for repair or mainte
`time of the constraint. The longest process time of any
`nance. The NEXT-MAINTENANCE-TIME item in
`process in the constraint is given in GREATEST
`dicates when the machine is next expected to be taken
`PROCESS-TIME, and the first process having that
`20
`out of service. This refers to scheduled maintenance.
`process time is considered to be the controlling process.
`The DOING data item is a list of lot and process
`TIME-TO-CONTROLLING-PROCESS is the nun
`pairs, which indicates which lots are currently in the
`ber of time steps from the constraint starter, including
`machine, and which processes those lots are involved
`the process time of the constraint starter, until a lot or
`in. As shown in the discussion on sides, it is not neces
`group of lots is available for loading into the controlling
`25
`sary for all lots in the machine to be in the same step of
`process. If the next available time for the controlling
`the process flow.
`process is known, TIME-TO-CONTROLLING
`SCHEDULING-TYPE indicates what type of deci
`PROCESS determines when the next batch of lots can
`sion making process should be used on this machine
`be started into the constraint. Also included in the struc
`whenever a load decision is to be made. Some of the
`ture are the lot numbers currently within the constraint,
`30
`preferred decision types include multi-lot machine opti
`and a flag to indicate whether this constraint is cur
`nization, round robin, and constraint member. These
`rently included in a local optimization process.
`decision making processes are discussed under the local
`In the embodiment of the scheduler which is de
`optimization topic. WAITING-TIME is a number indi
`scribed herein, delays which occur between unloading a
`cating at which time step the machine should load the
`machine and making a lot available to the next process
`35
`next group of lots. During the local optimization pro
`are not considered. Such delays are usually small con
`cess, it is sometimes desirable that a particular machine
`pared to the overall operation of the facility, and are not
`not load right away, but instead wait for another lot that
`generally important. However, in cases where delays
`is expected in the near future. In such cases, WAIT
`are significant, it may be necessary to take them into
`ING-TIME contains the time at which the machine is
`account. In such a situation, the transfer time is consid
`40
`next expected to take some action. As far as the sched
`ered to be simply another process step, and is treated as
`uler is concerned, the machine will simply sit idle until
`are all other process steps. Thus, the overall scheduling
`the current time, as defined by the calendar mechanism,
`system need not be modified to take such delays into
`catches up to the value in WAITING-TIME.
`account; they are handled within the parameters of the
`The values OPTIMIZING and CHECKED-UP.
`system as is currently described.
`45
`TO are used in the local prediction process as described
`under the subject of local optimization.
`GLOBAL PLANNING
`Sometimes there will exist a special relationship be
`Before actual scheduling of the processing facility is
`tween groups of processes which requires that succes
`undertaken, a global analysis of the facility must be
`sive process steps be performed with very little wait
`made. The results of the global analysis are made avail
`between them. This is especially true in semiconductor
`able to the local decision making portion of the sched
`processing, wherein lots must be moved quickly from
`uler to improve its optimization functions. The global
`step to step for some span of process steps. If a delay
`analysis is preferably made only one time unless process
`occurs in the middle of this sequence, the semiconduc
`parameters change significantly or process flows are
`tor slices may be ruined. An example of such a series of
`changed.
`55
`related process steps could be the several steps involved
`The purpose of the global planning stage is to define
`in applying, patterning and baking photoresist on a
`the steady-state features of the manufacturing facility.
`slice. Extended interruption of this set of processes
`This includes defining process flows and statistics of the
`could ruin the work in process, requiring that the slices
`various process steps. Special features of various ma
`in question be reworked or discarded.
`chines are taken into account, such as machines which
`60
`The group of process steps so related is referred to as
`have a high usage or long process times. Special pro
`a time constraint, or simply a constraint. The timing of
`cessing conditions are considered in terms of their in
`the steps in the constraint is critical; no large queues
`pact on the overall plant operation. The results of the
`must be allowed to build up within the constraint. Once
`global planning step indicate the macroscopic operation
`a lot or batch of lots has entered the constraint, they
`of the facility, giving such information as the cycle time
`