Proceedings of the 2008 Winter Simulation Conference

S. J. Mason, R. R. Hill, L. Mönch, O. Rose, T. Jefferson, J. W. Fowler eds.

TECHNOLOGY THAT UPSETS THE SOCIAL ORDER – A PARADIGM SHIFT IN ASSIGNING LOTS TO
TOOLS IN A WAFER FABRICATOR – THE TRANSITION FROM RULES TO OPTIMIZATION

Ken Fordyce Robert Bixby Richard Burda

IBM ILOG IBM
Essex Junction, VT USA Mountain View, CA USA East Fishkill, NY USA

ABSTRACT exploits emerging opportunities on the manufacturing

floor, and reduces the distortion from unplanned events
Historically the dominant decision technology to make Strategic – What Markets
dispatch decisions was “rules” which involves the
following basic computational mechanisms: merge, select, Tactical -committed orders, supplies near term,
synchronized output, business rules, plan/
sort, and if/then/else in a decision tree. Although rules do schedule tactics
a reasonable job they fundamentally lack a robust ability
to: (a) look across time, (b) look across tools at a tool set, Operational – daily adjustments: need date, selection of
focus, short term projected outs, target moves
(c) create an anticipated sequence of events at a tool set
over some time horizon, (d) establish a formal metric and Global Guide – Game Plan – ZOC
(f) search alternatives. However, standard wisdom was
Scheduling
dynamically generated hints for dispatch

Dispatch
from models that as needed, but feed real-
the rapid pace of change and short time interval between time to dispatch
dispatch decisions precluded the use of optimization to
build dispatch applications. Although this barrier was Dispatch – What next when tool is free based
on local information – opportunistic scavenging
legitimate in the 1980s and most of the 1990s based on
limitations in hardware and software (algorithms); the real
barrier today is cultural; not technical. From 2004-2007,
IBM and ILOG jointly worked to deploy the ILOG Figure 1: Sullivan decision tiers
optimization product FPO to key tools sets in IBM’s
300mm fab resulting in substantial improvements in Historically, dating back to the work in the early
performance and significantly reduced overhead to adapt to 1980s by IBM’s Gary Sullivan (Sullivan et al. 1992), the
changing circumstances. This paper will cover the dominant decision technology found in applications to
fundamentals of the paradigm shift. make dispatch decisions was “rules” which involve the
follow basic computational mechanisms: merge, select,
1 INTRODUCTION sort, and if/then/else in a decision tree. Although these
“rules structures” (which we will call heuristic dispatch)
The demand supply network for the production of can and do capture some reasonably complex logic and
semiconductor based packaged goods consists of a provide reasonable decisions in many cases, they
hierarchical sequence of decisions (Sullivan 1992; Figure fundamentally lack a robust ability to: (a) look across time,
1) focused on assigning assets to meet demand ranging (b) look across tools at a tool set, (c) create an anticipated
from a high level decision to allocate WIP and capacity to sequence of events at a tool set over some time horizon, (d)
meet exit demand to the low level decision of assigning a establish a formal metric for the quality of the decision,
specific manufacturing lot to a specific tool to receive a and (f) search across alternatives. However, standard
specific value add process in wafer fabrication. This last wisdom was the rapid pace of change and short time
decision is called a dispatch or assignment decision and interval between dispatch decisions precluded the use of
thousands of these decisions are made each day. more sophisticated decision technology (such as
The assignment decision process must coordinate optimization -- which had successfully displaced rules in
the actions and decisions of several logically isolated other situations) to build “dispatch” applications.
participants in a serially dependent system of activities. Therefore the core approach changed little, if any, over
Therefore it balances the requirements of several goals twenty years; in spite of advances in algorithms and
(cycle time, output, serviceability, and inventory computer performance.
management) which compete for the same resource, In 2003-2004 time frame IBM recognized that
“rules” and their opportunistic scavenging approach (Fox

978-1-4244-2708-6/08/$25.00 ©2008 IEEE 2277

 Fordyce, Bixby, and Burda

and Kempf 1985, Lin 1992, Sullivan 1987) was resulting

in lost thruput, increased cycle time, a loss of flexibility,
and the allocation of manufacturing energy on the wrong
lots in its fully automated 300mm wafer fabrication facility
located in East Fishkill, NY. Additionally, IBM believed MFG Transaction Systems (dynamic)
- lot movement
Build time (static – not dormant)
- transaction data base layout

that twenty years after it had developed and deployed one - tool status
- knowledge bases (fact bases, translators, routings,
tool-lot affinity rules
- other
of the first real time rule based systems to control dispatch - models / - end user routines

decisions, computational advances in algorithms and Gateway – Decision & View Enabler- -
hardware made optimization possible. At the same time - receive floor transaction
- appropriate disposition of floor transaction
ILOG had arrived at a similar conclusion and was - invoke knowledge bases & models
- build new transaction record(s)
developing its FPO rapid scheduling application for key
tool sets in FABS relying on recent advances in Integer and Transaction Data Bases – Blackboards
- state of floor arrays
Constraint Programming.. - levels, counts, delta schedule

From 2004-2007, IBM and ILOG jointly worked - tool lot affinity

to deploy the ILOG optimization product FPO to key tools

User Views Alerts DDM/SIS
sets in IBM’s fully automated 300mm wafer fabrication - passive - proactive - intervention / assignment logic
- information
facility. FPO now controls the dispatch decision at each - line views
- issue alerts
- monitor/review
- dispatch list / “direct robot”
- dispatch scheduling logic
major tool set (over ½ of the tools) in the 300mm fab. It - query

has resulted in substantial improvements in performance; Display access via Web

email / page /
Floor System / operator
sametime
significantly reduced overhead to adapt to changing
circumstances; and made the complex easy to understand Figure 2: Core flow for rule based dispatch
and control. The Fab moved from “heuristic dispatch” to
“schedule dispatch”.
This paper will provide an overview of the Dispatch Request Sequence
dispatch environment; the key differences between “rules” 1. What is the next lot for tool XXXX Dispatcher
and “optimization”, the development and deployment of MES 2. Execute dispatching
logic for tool XXXX using
optimization to control the assignment of lots to tools, real-time data in repository
specific examples from key tool sets, the key advances for 3. Lot YY is the next lot for tool XXXX
Material
the business and the tool set managers, and the basics of Manager
Dispatch
Server
the core advances in the mathematical optimization over
the past 20 years that enables optimization to be a practical
Changes to monitored tables Dispatcher
alternative in such a dynamic and rapid fire environment. MMDB continuously sent to Dispatcher Data
Repository
2 FUNDAMENTALS OF THE WAFER
FABRICATION, ASSIGNMENT DECISION AND Figure 3: Typical dispatch request sequence
THE ARCHITECTURE OF RULE BASED
DISPATCH SYSTEMS The problem has fundamentally remained true to
John Fowler’s 1992 (NSF Workshop October 1992 New
The work by Sullivan, Kempf, Fowler, Graves, Wein, Hampshire) description:
Glassey, Bitran and many others in the 1980s and early “Dynamic Production Planning and Scheduling
1990s in planning, scheduling, and dispatching wafer is needed in semiconductor manufacturing
fabricators has been extensively written about the basics of because of the complexity of the manufacturing
wafer fabrication flow (reentrant); the core considerations processes including factors such as unreliable
in assigning a lot to a tool; and the basic architecture of a equipment, batching, reentrant flows, rework,
rule based dispatch system is now well known. Specific yield loss, hot lots, combination of production,
the applications for rule based dispatch there are (and have engineering and R&D lots, and varying product
been for a while) a number of commercial applications as mix and start rates. In addition to these factors,
well as “home grown” applications that are part of day to future wafer fabs will probably be more
day life. This paper will assume the reader is familiar with automated than current factories. This will
the basics and focus on reviewing some key aspects of the require computers to control the flow of
assignment decision and its solution. material through a fab instead of humans. While
The core architecture of a dispatch system and the all of the factors mentioned above make the
method of obtaining and organizing knowledge has real-time control of a factory necessary, they
remained remarkably similar to the original work done by also make it very complicated to determine what
Sullivan. Figure 2 (Sullivan 1991) and Figure 3 provide a the best decisions are. There are, however, a few
basic overview. things that we have going for us.

2278
 Fordyce, Bixby, and Burda

1. Except for rework, most of the flow in a fab 1.6. status of lot – on hold, not on hold, send ahead
is deterministic (instead of probabilistic as required
in a job shop). 1.7. oper-tool relationships
2. The processing time per wafer or per lot or 1.8. manufacturing engineering requirements
per batch is very nearly deterministic, so 1.8.1. counts (avoid too many wafers on certain
that once processing begins; we can get a tools)
very good prediction of when the 1.8.2. time limits (tool requires re-
processing will end. qualification)
3. The shop floor control systems in place in 1.8.3. send ahead required
current wafer fabs provide much of the 1.8.4. result of metrology
information we need in order to make good 2. global importance of the lot to the supply chain or
decisions business
2.1. priority, customer, development vs production,
2.1 Fundamentals of the Assignment Decision lots
2.2. one might have all lots the same, that is still
Historically, the easiest way to conceive of dispatch is global importance
when a tool becomes free (moves from a busy state to a 3. pacing lot movement
non busy state or comes back on line) lots compete to be 3.1. fluctuation smoothing, range management, delta
the “next on the tool”. In practice, other triggers, such as schedule, critical ratio
the change in status of a lot or elapsed time, can trigger the 4. local tool characteristics and performance
logic to review and assign lot(s) to a tool. Figure 4 5. batching, trains
illustrates the basics of lots waiting for a tool at a tool set. 5.1. time sensitivity for yield and rework
5.2. local zone of control
Tool Group 5.3. manufacturing engineering, tool-oper affinity
The virtual queue is
dynamic with lots entering
Virtual Queue 6. upstream and down stream requirements
and exiting based on in-
gate, dispatch, hold, hold
6.1. WIP aversion
ABC ABC BC
release, inhibits, etc. Tool A 6.2. extended zones of control
AB AB AB B 7. more complex global controls beside pacing
• Dispatch can return no
lots, and wait for next AC BC ABC
request
• Dispatcher sorts the AB BC BC Tool B 2.2 Guidance and Judgment
current queue based on
business rules
The core dispatch decision making activities can be
ABC - Lot eligible to run on tool A,B or C, green recipe divided into two primary components: guidance and
Tool C
judgment.
Guidance or advocate logic is the set of
Figure 4: Basics of lots waiting to be dispatched computational activities (which may be a program or
manual) to create information posted some location (often
Fundamentally this decision process must first a table structure) that the assignment logic accesses or to
determine which lots are eligible to run on which tools and trigger an assignment module to execute. The most
then narrow the selection process based on business common example is the calculation of some type of “delta
guidelines (Due dates, Business Rules, dedication schedule” value for each. Another example is the updating
strategies, phase in tools); Process requirements of a fact base that may contain operation – tool preference.
(production paths, reticle available, tool specific inhibit); A third example is the establishment of the tool
and Intrinsic properties of tools which significantly impact deployment tables (operation – tool affinity) which is done
throughput (for example batch size and trains); and separate from the assignment logic and posts this
occasionally synchronization of events across the Fab. We information to data set where the assignment logic can
can break the key elements down as follows: access this information.
1. tool – lot affinity Judgment or assignment is the set of
1.1. what lots can run on this tool, what tools can computational activities that when completed, result in a
handle this lot change of state or action on the manufacturing floor. The
1.2. what are preferred tools, what are preferred lots judgment algorithm must balance competing requirements
1.3. establishes initial feasible state space with such as meeting on time delivery, but improving
preference value based on tool-lot affinity throughput with batches and trains.
1.4. includes Conceptually, the guidance logic and the
1.5. what manufacturing activity (oper) next for a lot assignment logic can run asynchronous – that is the
guidance logic runs when it “wants” and without concern

2279
 Fordyce, Bixby, and Burda

for when the assignment logic runs and the reverse is true making approaches in a wide range of applications from
for the assignment logic. Sometimes during an computer chess to supply chain planning to the placement
implementation, we choose to run the two together; but of radioactive seeds to treat prostrate cancer (*** give
conceptually the two could be split. Guidance logic can references). Despite the clear advances in other areas,
further be classified by the frequency with which it runs or Fabs have clung to their “only simple can work” approach
its function. and the corresponding culture of reaction and “heroic
action”.
2.3 Historical Limitations of Judgment
3 AN EXAMPLE OF THE LIMITATION OF RULES
Dating back to the 1980s the computation methods used
within judgment could be described as “decision tree one The following example clearly illustrates the limitations of
pass logic”: rules for “dispatch heuristics” and the value in optimization
• join or link methods to deploy dispatch scheduling. These limitations
• sort and select include: the inability to (a) look across time, (b) look
• scoring across tools at a tool set, (c) create an anticipated sequence
• if then else of events at a tool set over some time horizon, (d) establish
• one pass logic no looping (except accumulation), a formal metric and (f) search alternatives.
algorithm In top half of Figure 5 we have typical dispatch
Although this method produced adequate situation. There are three lots waiting to be processed.
decisions, the decisions were far from optimal and often Two of the lots (94 and 92) are behind schedule. One of
rigid – that is requirement changes in the programming as the lots is ahead of schedule (88). There are three tools in
business conditions changed. It stood in start contrast to the tool group and their status is given in Figure 5. When
the successful deployment of far more intelligent decision tool#1 becomes available what lot is it assigned?

WIP in Queue in priority order:

Status: Available for work
Tool #1
delta schedule Process Rq’d Current Setup on B, but can Run: A,B,C

Lot#94 (behind) Proc=B

Status: Running
Lot#92 (behind) Proc=A Tool #2 Est Completion: 5 min
Current Setup on B, and can only Run B
Lot#88 (ahead) Proc=C
Status: Running
Tool #3 Est Completion: 45 min
Current Setup on A, but can Run: A,C
Simplifying Assumptions
- All processes are 60 minutes long
- All setups take 15 minutes

Tool #1 has just become available -> What should it run next?
Typically, heuristic dispatch will consider only the tool that is available. It will not look at the potential
impact of actions in the future or across the tool set

At time 0: Tool#1 free, chooses lot #94 to tool #1 because the lot is behind schedule and the
setup matches (sound thinking)
Figure 5: Example dispatch situation

In bottom half of Figure 5 we have typical Let’s return to the original decision and see how
“intelligent” assignment decision by a rules engine. The optimization can avoid the undetected collateral damage.
dispatch engine chooses lot #94 to tool #1 because the lot In Figure 7 we see three possible solutions that are
is behind schedule and the setup matches. This meets two projected forward through the complete of all lots
key criteria: working on lots that behind and improving currently waiting to be serviced by this tool group.
throughput by avoiding setups --- very sound thinking -- Observe for each potential solution a tentative detailed
however? schedule (in our example, we round to 10 minute intervals
As we play events forward in time, we quickly simply to avoid overburdening the reader with detail, but
(Figure 6) find previously “undetected collateral damage” FPO keeps details to the minute or less if needed). Since
from our decision -- at 5 minutes: tool # 2 idle -> no wip we are projected forward in time across lots and across
available since tool #2 can only run process B and there tools we can directly measure the impact of the decision
are no lots in queue that require process in terms of such items as completion time for lots (Figure
7) and tool utilization or idle time (Figure 8). For both

2280
 Fordyce, Bixby, and Burda

measurements, options 2 and 3 substantially out perform

option 1.

WIP in Queue in priority order:

Status: Available for work
Tool #1
delta schedule Process Rq’d Current Setup on B, but can Run: A,B,C

Lot#94 (behind) Proc=B

Status: Running
IDLE at 5 min mark
Lot#92 (behind) Proc=A Tool #2 Est Completion: 5 min
Current Setup on B, and can only Run B
Lot#88 (ahead) Proc=C
Status: Running
Tool #3 Est Completion: 45 min
Current Setup on A, but can Run: A,C
Simplifying Assumptions
- All processes are 60 minutes long
- All setups take 15 minutes

Tool #1 has just become available -> What should it run next?
Typically, heuristic dispatch will consider only the tool that is available. It will not look at the potential
impact of actions in the future or across the tool set

At time 0: Tool#1 free, chooses lot #94 to tool #1 because the lot is behind schedule and the
setup matches
Undetected collateral impact of this decision
At 5 minutes: tool # 2 idle -> no wip available since tool #2 can only run process B and there
are no lots in queue that require process B
At aggregate level shows idle with WIP (albeit wrong WIP)
Figure 6: Collateral damage and limits of dispatch

scaled to 10
min intervals,
start/stop are
Three Options approximate

Option 1
tool 0 10 20 30 40 50 60 70 80 90 100 110 120 130 135 140
Tool 1 lot 94 (behind) lot 88 (ahead) idle
Tool 2 busy idle
Tool 3 busy lot 92 (behind) idle

Option 2
tool 0 10 20 30 40 50 60 70 80 90 100 110 120 130 135 140
Tool 1 lot 88 (ahead) idle
Tool 2 busy lot 94 (behind) idle
Tool 3 busy lot 92 (behind) idle

Option 3
tool 0 10 20 30 40 50 60 70 80 90 100 110 120 130 135 140
Tool 1 lot 92 (behind) idle
Tool 2 busy lot 94 (behind) idle
Tool 3 busy lot 88 (ahead) idle
Figure 7: Three sequence schedule options

2281
 Fordyce, Bixby, and Burda

Completion Time for Lots

Option 1 Option 2 Option 3

120

100

80

elapsed time 60

40

option 2 generates the option 3 generates the

lowest average cycle lowest average cycle
20 time for all lots at tool time for "behind" lots at
set tool set
0

ave all lots ave behind lots

results each option per lot

Figure 8: Comparison of three options for lot complete time

For each option when a tool become idle

Tool 1 Tool 2 Tool 3

120

100

80
elapsed time

60

40

Slightly less disparity in

20 "idle" time distrubtion in
option 2 over option 3
0

Option 1 Option 2 Option 3

each tool for each option

Figure 9: Comparison of three options for tool utilization

The application of optimization methods decisions – two key ones are deployment decisions (the
improved the assignment decision by generating optional processes a tool is qualified and/or allowed to handle) and
decisions across time and tools, evaluating these decisions the movement, location, and cleaning of masks or reticles.
with a firm metric, searching for other options, and having Additionally optimization enables the
a selection or stopping criteria. Observe: Option 2: lower organization to move beyond ranking and transition from
average cycle time for lots and less variation in exit time specifying what from how. Let’s look at two examples.
for lots and tool use. Option 3: lot#92 (which is behind) A typical goal for a fab is to eliminate
completes sooner good utilization of tools. Both options unnecessary transport of lots. The goal is “minimize” lot
are superior to option 1. The best option depends on movement and this part of a goal of minimizing cycle time.
(a)details (how far behind and ahead, lot priority, demand The optimization engine with create solutions with this
class, (b)near term WIP conditions, and (c)business goal in mind.
priorities. However the value of optimization goes well A rule engine requires the rule writer to specify
beyond a better assignment decision, but provides a “how to limit” travel. A typical rule would be: <If lot is of
visibility impossible to obtain with simple point of sale type A, B, or C do not let it travel to another sector to be
rules. It enables everyone to clearly see an anticipated processed by a tool until it has waited at least 30 minutes in
projected schedule for lots and tools and anticipated tool its current sector>. What the rule really wants is to keep a
utilization and WIP levels. This is critical, since the lot from traveling to another sector from its current sector
assignment decision is strongly influenced by many other if there is a tool in this sector that can handle the lot

2282
 Fordyce, Bixby, and Burda

reasonably soon. There is no way to specify this general 1990s, it was generally acknowledged, even by experts in
policy. So the rule specifies the “specifics” of how and mixed-integer programming, that while these techniques
hopes many times a tool will become free in the lot’s were a powerful tool in the solution of schedule models,
current sector within 30 minutes that is a good match for they were simply not fast and robust enough to offer the
this lot. Obviously, if a fab is heavily loaded this is a turn-around times that were necessary in real-time, or even
higher probability event. A fab that is only moderately near real-time applications (Durbin and Hoffman 2001).
loaded could have a problem and the rule would need to be However, as demonstrated in Bixby (2001), Bixby (2003),
manually changed. and Bixby and Rothberg (2003), that situation has changed
A second common limitation involves the use of dramatically in the last several years. In 2001 ILOG began
rankings. Assume lots A, B, and C are behind schedule by to seriously investigate the use of MIP and CP to address
1.1, 1.2, and 4.8 days respectively. The lot C has the rank detailed production scheduling for a large semiconductor
of 1 (most behind) since it is 3.6 days worse off the lot B. fab.
Alternatively if lot C was behind schedule by 1.3 days it
would still have the rank of 1, but it just barely worse off 5 BASICS OF APPLYING MIP AND CP TO FAB
(0.1 days) then lot B. Typically, heuristic dispatch will PRODUCTION SCHEDULING
work with the ranking and not be able make use of the
richer information about the magnitude of the difference. “Our approach uses MIP and CP as components
Scheduling dispatch (mathematical optimization) will. in a special-purpose decomposition algorithm that iterates
alternately over the space and time dimensions. We call the
4 WHAT MATHEMATICAL METHODS MAKES algorithm STARTS for Space-Time Allocation for Real-
THIS POSSIBLE? Time Scheduling. To solve fab scheduling problems using
the STARTS algorithm, operational models must first be
The challenge, besides finding a quality solution, is finding defined in terms of variables, objectives and constraints.
a quality solution fast. The requirement is the generation During production operations, lot and equipment status
of a complete solution in 60 seconds or less, which enables data from a fab manufacturing execution system (MES) are
an updated solution to be generated every 5 to 10 minutes. continually sent to the STARTS scheduling software and
Obviously, simple brute force of generating all or most evaluated according to the defined model.
alternatives and evaluating is not going to the job done. Conceptually, the scheduler begins by generating
The key is the coordinated use of mixed integer variable values that satisfy all of the constraints (i.e. by
programming (MIP) from Operations Research and finding a feasible solution). When a feasible solution is
constraint programming (CP) from computer science to found, the scheduler evaluates the objective function using
narrow and direct search. these same values. If more than one feasible solution
MIP is well suited to resource allocation exists, the STARTS algorithm continues to modify the
applications and is used extensively to compute optimal variables to improve the objective function. Feasible
order fulfillment locations, crew-shift equipment solutions are compared until the optimal solution is
assignments, vehicle routes in transportation and determined. It is central to the success of these methods
production plans for manufacturing. CP has been that the theories of MIP and CP allow the determination of
successful in solving large combinatorial problems in the these ever-improving solutions by explicitly examining
areas of planning, scheduling, natural language processing only a very small fraction of the total number of feasible
and DNA sequencing. CP techniques are a particularly solutions.
effective companion for MIP techniques in detailed The optimal solution for a fab process area
scheduling applications. Two fab examples are: schedule contains a list of lotstep assignments to specific
1. Two lots (A and B) with identical characteristics tools for a certain time horizon (usually 8 to 12 hours)
(manufacturing activity, lot size), etc starting from the current time, with recommended start
1.1. Lot A is behind schedule and Lot B is ahead times and expected finish times. This schedule can be
1.1.1. Lot B will never go before Lot A packaged as messages, database tables or files to be used
2. Mask W has “50 wafers life” left before maintenance. by a lot dispatcher and viewed in Gantt format.
2.1. Lots A, B, C, D, E (each with 25 wafers) require The user controls the behavior or personality of
mask W the solver by inputting preferences or priorities and
2.1.1. Near term schedule will always be weights. For example, the user can set “preference” for
limited to 2 out of 5 of these lots urgent lots (P1), throughput (P2), and total item time (P3).
For an overview of MIP see Wolsey (1998) and Williams For example, by setting P1 >> P2 >> P3, the
(1999). For an exposition of the fundamentals of CP see urgent_lot_assignment would be maximized first, then the
Lustig and Puget (2001). throughput, and, finally, the total_idle_time would be
In spite of the widespread applications of minimized. In effect, this choice would rank the urgent-lot
integrality-based techniques, up until as recently as the late

2283
 Fordyce, Bixby, and Burda

objective higher than throughput, and throughput higher Bixby, R., and E. Rothberg. 2003. Solving linear and
than tool idle time. The priority values integer program. MPI Informatik ADFOCS 2003
illustrated by P1, P2, and P3 (above) can be tuned to </[Link]/conferences/adfocs-03/
respond to changing operational goals. For example, Slides/Bixby_1.pdf>
during a new fab ramp, the urgent lot assignment objective Bruno, G., A. Elia, and P. Laface. A rule based system to
may be ranked higher than the throughput objective in schedule production. IEEE Computer 19(7):32-41.
order to support critical process or product development. Chen, H., M. Harrison, A. Mandelbaum, A. Ackere, and L.
On the other hand, a fully-ramped production fab may rank Wein. 1988. Empirical evaluation of a queueing
the throughput objective higher than other objectives in network model for semiconductor wafer fabrication.
order to meet critical production targets during high Operations Research 36(2):202-215.
seasonal demand periods.” (Bixby, Burda, and Miller Consilium, 1988. Rule Based Dispatch User's Guide,
2006) Mountain View, CA.
Dabbas, R., and J. Fowler. 2003. A new scheduling
6 RESULTS AND DISCUSSION approach using combined dispatching criteria in wafer
Fabs. IEEE Transactions on Semiconductor
A set of critical fab metrics including throughput, cycle Manufacturing 16(3):501-510.
time, hot lot cycle time and QTime lot conformance, with Fargher, H., and R. Smith, 1994. Planning in a flexible
secondary metrics including such measurements as batch semiconductor manufacturing environment. Chapter
size and balance across tool sets, were analyzed to 19 in Intelligent Scheduling, edited by Mark Fox and
determine the effectiveness of the solution. The scheduler Monte Zweben, Morgan Kaufman Publishers
provided benefits in throughput, cycle times, and hot lot Fox, M. 1987. Constraint-directed search: a case study of
performance, while automating managing of QTime lot job-shop scheduling. Morgan Kaufman Publishers,
scheduling. Additionally, the scheduling solution also Los Altos, Ca.
provided fab operations with improved visibility. FPO is Fox, B., and K. Kempf. 1985. Complexity, uncertainty,
currently deployed in about ½ of the tools and most of the and opportunistic scheduling. In Proceedings of the
critical tool sets. IEEE Second Conference on Artificial Intelligence
The new optimization methods enable fabs to take Applications: The Engineering Knowledge Based
the next leap in dispatch scheduling. The biggest obstacle Systems, Miami, Florida, 487-492.
is no longer technology, but social order. Glassey, C., J. G. Shanthikumar, and S. Seshadri. 1996.
"There is no more delicate matter to take in hand, Linear control rules for production control
nor more dangerous to conduct, nor more doubtful of semiconductor Fabs. IEEE Transactions on
success, than to step up as a leader in the introduction of Semiconductor Manufacturing 9(4):536-549.
changes. For he who innovates will have for his enemies Glassey, C., and W. Weng. 1991. Dynamic batching
all those who are well off under the existing order of heuristic for simultaneous processing. IEEE
things, and only lukewarm support in those who might be Transactions on Semiconductor Manufacturing,
better off under the new.” (Niccolo Machiavelli) 4(2):77-82.
Graves, S., H. Meal, D. Stefek, and A. Zeghmi, 1983.
REFERENCES .Scheduling of re-entrant flow shops. Journal of
Operations Management 3: 197-203.
Bitran, G., and D. Tirupati. 1989. Tradeoff curves, Gurnani, H., R. Anupindi, and R. Akella. 1992. Control of
targeting and balancing in manufacturing networks. batch processing systems in semiconductor wafer
Operations Research 37:547-555. fabrication facilities. IEEE Transactions on
Bixby, R, R. Burda, and D. Miller. 2006. Short-interval Semiconductor Manufacturing, 5:4. 319-327.
detailed production scheduling in 300mm IBM Burlington Today. 1990. Decision making,
semiconductor manufacturing using mixed integer and scheduling, and running the line. In Communications
constraint programming. In Semiconductorfabtech – Operations Department, General Technology
32nd edition, <[Link]>, 34-40. Division, IBM, Essex Junction, Vermont 05452,
Bixby, R. 2001. Solving real-world linear programs: a 26:136, 1.
decade and more of progress. Operations Research 50: Johri, P. 1989. Dispatching in an integrated circuit wafer
3-15. fabrication line. In Proceeding of the 1989 Winter
Bixby, R, M. Fenelon, Z. Gu, and E. Rothberg. 2004. Simulation Conference, 918-921.
Mixed-Integer programming: a progress report, The Kempf, K., D. Le Pape, S. Smith, and B. Fox 1991. Issues
sharpest cut, Grotschel, M. (editor), Society for in the design of AI based schedulers. AI Magazine
Industrial and Applied Mathematic ISBN 11(5):37-45.
0898715520. Kempf, K. 1989. Manufacturing planning and scheduling:
where we are and where we need to be. In

2284
 Fordyce, Bixby, and Burda

Proceedings of the Fifth IEEE Conference on AI Williams, H. 1999. Model building in mathematical
Applications, IEEE Computer Society Press, Los programming. 4th Edition, John Wiley and Sons..
Alamitos, CA. 13-19.
Kempf, K. 1989. Manufacturing scheduling: intelligently AUTHOR BIOGRAPHIES
combining existing methods. In Working Notes of
AAAI AI in Manufacturing Symposium, M. Fox editor, KENNETH FORDYCE joined IBM in 1977 and is
AAAI, 445 Burgess Drive Menlo Park, CA 94025- involved in the integrated application of decision and
3496. information technology to improve organizational
Kempf, K. 1994. Intelligent scheduling semiconductor performance especially for planning, scheduling, and
wafer fabrication. Intelligent Scheduling 18: 473-516. dispatch. He has received awards from IBM, INFORMS,
Lee C., R. Uzsoy, L. Martin-Vega, and P. Leonard. 1991. POMS, and AAAI; been a key contributor to IBM’s
Production scheduling algorithms for a semiconductor advanced supply chain planning solution used inside and
test facility. IEEE Transactions on Semiconductor outside of IBM; and published numerous papers on
Manufacturing 4:271-280. planning, scheduling, and dispatch. He is an adjunct at
Lee C., R. Uzsoy, and L. Martin-Vega. 1992. Efficient Columbia University; serves as a research team member at
algorithms for scheduling semiconductor burn-in Einstein College of Medicine; and has a PhD from Union.
operations. Operations Research 40(4):764-775.
Lin, G. 1992. An opportunistic price-based multiple DR. ROBERT BIXBY earned a Bachelor of Science
resource and part scheduling. Ph.D. dissertation, degree from the University of California-Berkeley and a
School of Industrial Engineering, Purdue University. PhD from Cornell University. Bixby holds positions at
Lustig, I., and J. Puget. 2001. Program does not equal Rice University as research professor and Noah Harding
program: constraint programming and its relationship Professor Emeritus of Computational and Applied
to mathematical programming. Interfaces, 29-53. Mathematics, and as research professor of management in
Martin-Vega. L., M. Pippin, E. Gerdon, R. Burcham. 1989. the university's Jesse H. Jones Graduate School of
Apply just in time at a wafer Fab case study. IEEE Management. Bixby was formerly chairman of the
Transactions on Semiconductor 2(1):16-22. Mathematical Programming Society, and editor-in-chief of
Savell, D, R. Perez, and S. Koh. 1989. Scheduling the journal Mathematical Programming. In addition, he has
semiconductor wafer production: an expert system authored over 50 scholarly publications. He is a member of
implementation. IEEE Expert 4(3):9-15. the National Academy of Engineering, and has received
Sullivan, G. 1987. Logistics Management System (LMS): the Mathematical Programming Society Beale-Orchard-
lessons in manufacturing dispatch. In Flexible Hayes Prize for Computational Mathematical
Manufacturing Systems, edited by K. Stecke and R. Programming as well as the INFORMS Impact Prize.
Suri, Elsevier, New York 33-44.
Sullivan, G. 1994. Logistics Management System (LMS): RICHARD BURDA is the lead architect for 300mm
integrating decision technologies for dispatch scheduling and dispatch at IBM and received a number of
scheduling in semiconductor manufacturing. Chapter patents. Burda has held several positions relating to
17 in Intelligent Scheduling, edited M. Fox and M. industrial engineering, operations management and product
Zweben, Morgan Kaufman Publishers, 473- 516. marketing in the semiconductor and other industries. He
Sullivan, G., R. Dunki-Jacobs, B. Gerard, and R. Sell. holds a Bachelor of Science in Mechanical Engineering
1992. Logistics Management System (LMS): an from Villanova University and an MS in Management
advanced decision support system for the fourth from the Pennsylvania State University
decision tier dispatch or short interval scheduling.
Production and Operations Management 1(1):70-86.
Sullivan, G., M. Morreale, and J. McGrew, J. 1992.
Knowledge based systems: APL techniques. In
Encyclopedia of Microcomputers 9:345-378.
Sullivan, G. 1990. Logistics Management System (LMS):
implementing the technology of logistics with
knowledge based expert systems. Innovative Expert
System Applications, 183-202, AAAI and MIT Press,
Menlo Park, CA.
Wein, L. 1988. Scheduling semiconductor wafer
fabrication. IEEE Transactions on Semiconductor
Manufacturing 1(3):115-130.
Wolsey, L. 1998. Integer programming. John Wiley and
Sons.

2285