This report covers the period from the contract start (October 1) through
June 30, 1998.
3. Activities
4. Research Tasks Progress Report
| Matt Hickie | Motorola | ASU |
| Bob Baker | Intel | ASU |
| Court Hilton | Intel | ASU |
| Kishore Potti | AMD | ASU,UI |
| Ed Yellig | Intel | MIT |
| Larry Farey | LSI Logic | MIT |
| Jeriad Zoghby | AMD | MIT |
| Steve Markle | Lucent | UI |
| Frank Alvarez | Intel | UI |
| Bruce Sohn | Intel | UI |
| Mani Janakiram | Motorola | UI |
| Ed Rietman | Bell Labs | UI |
| Stuart Bermon | IBM | ASU,MIT,UI |
The field of queueing networks has essentially had three waves of progress. The early work of the Danish teletraffic engineer Erlang was concerned with analyzing busy probabilities in telephone exchanges. Sub-sequent work of Jackson in the 1950s, motivated by the problem of predicting performance of job shops, obtained explicit solutions for certain systems, now called Jackson networks. In the 1970s this work was generalized to a larger class of product-form networks. Recently, new methods have been developed which have led to a fresh wave of progress. A procedure based on studying functionals of the system was developed by the PI which allows the development of performance bounds for systems with re-entrant process flows. It has also illustrated capacity loss problems arising from the use of priority policies. The dynamic programming approach allows for optimization of capacity decisions over time, in the face of yield, demand uncertainties, etc.
In this paper, we obtain new linear programs for obtaining bounds on
such performance measures. These bounds exploit the key facts that the
transition probabilities of the mathematical queueing network models of
the plants are shift invariant on the relative interiors of faces, and
that the performance measures of interest, such as cycle-time and WIP,
are linear in the state of the system.
A systematic procedure for choosing different quadratic functions on
the relative interiors of faces to serve as surrogates of the differential
costs in an inequality relaxation of the average cost function leads to
linear program bounds. These bounds are provably better than earlier
known bounds. It is also shown how to incorporate additional features
such as the presence of virtual multiserver stations to further improve
the bounds. The approach also extends to provide functional bounds
valid for all arrival rates.
The UI researchers are also working with Motorola and Lucent personnel
to test scheduling policies developed at UI.
Existing methods for manufacturing system analysis suffer from many shortcomings. Simulation is time-consuming to build and to run and extremely difficult to debug. It is a crude tool for the design of systems, and ill-suited for determining operating policies. Conventional analytic methods for system evaluation such as queuing networks make simplifying assumptions that cast doubt on their results (unlimited inventory, reliable machines) and do not allow the modeling of operational policies.
We plan to build upon existing decomposition methods for production line analysis and on dynamic programming methods for real - time scheduling.
In earlier work, Markov process models of manufacturing systems were
analyzed approximately by system decomposition. These models accounted
for disruptions due to machine failures and for finite buffers. They considered
the propagation of disruptions from machine to machine, in which a failure
of one machine would cause buffers to be empty or full, and therefore other
machines to be forced to be idle. Approximation is required because the
large state spaces of such models can not be treated analytically or numerically.
Decomposition seeks to replace a complex system by a set of simple systems
which are chosen carefully. Existing methods have been shown to work well.
We plan to
extend existing models to account for multiple part types and reentrant
flow, which is essential for modeling semiconductor production.
Management Of Ion Implantation Processes: The management of ion implantation processes is one of several challenging problems in scheduling wafer fabrication facilities. A complicating factor is the fact that there are sequence dependent setups (e.g. species changes). Because of the setups, it is sometimes desirable to leave an implanter idle (if another lot requiring this species will arrive soon) rather than to change the setup. There are several goals in managing an ion implantation area. These include: 1) maximizing the throughput; 2) minimizing the cycle time through the area; and 3) supplying the correct material to downstream constraint operations in a timely fashion. A deterministic scheduling approach to this problem is investigated in this research.
Reticle Management: Photolithography performance is not only dependent upon the stepper and the track being available to process material, but it is also dependent upon the right reticle also being available. This effort focuses on the strategic, tactical, and operational aspects of reticle management. Strategically, decisions must be made as to how many copies of each reticle will be purchased. Tactically, reticle assignments to steppers must be decided. Operationally, real-time decisions must be made as to what material to run on which stepper.
Operator Cross Training: The operation of any wafer fabrication facility
is highly dependent on both labor and equipment. Modeling a fab ignoring
either labor constraints or bottleneck equipment could misrepresent cycle
times, throughput rates, and work-in-process. The variety of equipment
in wafer fab creates the need for a highly skilled labor force, characterized
by a high level of cross-training, and the ability to monitor multiple
machines at one time.
Composite Dispatch Rule: When a series of jobs in a queue are waiting
in front of a machine or bank of machines to be processed, dispatching
rules are used to sequence the order in witch the jobs are going to be
processed. Commonly used dispatching rules (FIFO, EDD, SPT, etc.) only
evaluate one performance measure to sequence the jobs through the machine
or bank machines (Time in queue, Due date, Makespan, etc.) in an existing
process. Composite dispatching rules consider more than one performance
measure when deciding which lot to work on next.
Reticle Management: Our efforts to date have been focused on the tactical decision of reticle assignment. The current approach is to run a simulation starting with the current WIP and machine status for the length of one shift in order to determine which lots will arrive to the photolithography during the next shift. We then formulate the problem of reticle assignment as an out-of-kilter network problem in order to maximize the throughput of lots through the area while keeping the number of reticle movements between steppers (and the reticle stocker) to a minimum. We are working closely with our Motorola sponsor on this effort and have started discussions with a Cornell intern currently working at Micrus.
Operator Cross Training: Determining the optimal number of operators trained for specific skill levels can be a key factor in meeting production requirements. In addition, it takes time to train an operator and the training cost is one of the major factors which is always considered by management. The objective of our research is how to determine the optimal number of operators to be trained for each skill levels for a certain period while keeping total training cost minimized. Both mathematical programming and simulation techniques are employed.
Composite Dispatch Rule: The Apparent Tardiness Cost with Setups (ATCS)
rule is a heuristic that differs from the other commonly used dispatching
rules. Instead of taking only one performance measure into consideration
to schedule jobs that are in a queue, it evaluates three: sequence dependent
setups, job slack and job weight. The purpose of this dispatching rule
is to minimize total weighted tardiness on either a single machine or a
series of parallel machines in a given process. The sequence is generated
by computing a priority index of every job that is in queue at any instant
t when the machine is available. The job with the highest priority is the
one that is going to be processed next. This heuristic can be divided into
two phases, in the first phase a number of parameters characterizing the
problem instance and two scaling factors (k1 and k2) are computed and in
the second phase the priority index and schedule are calculated based on
the results of the first phase.