Raith (and other tools) scheduling: another idea...
shott at snf.stanford.edu
Fri Jan 30 08:02:00 PST 2004
Dan and all Raith users:
I appreciate all of the efforts, suggestions, and discussion of improved
ways for allocating scarce resources. There are clearly a handful of pieces
of equipment for which this has become a major issue. The Raith and the STS
deep etcher, I'm sure, head that list!
I agree with Dan that software can provide a lot of tools to help ...
although, as you'll see later, I'm not sure that I think that a multipass,
bid system is the best approach.
Before launching into that, however, let me point out something about the
existing reservation system that may be obvious to all but that bears on the
current discussion. The current system enforces one simple rule: your
reservation has to be COMPLETED no more than 7 days from "right now". When
things get jammed up, this has resulted in the unfortunate situation of
people madly grabbing each 30 minute hunk of time ... even though 30 minutes
isn't a particularly useful or usable block of time on either the Raith or
the STS etcher.
Why was the rule made that the reservation had to be completed in less than
seven days? This was a simple choice ... at least when it was made: we
didn't want to allow someone to grab an arbitrarily long time if the rule
were "your reservation has to START no more than 7 days from right now"
because we didn't have a system for regulating or enforcing exactly how long
each reservation could be. While I'm sure that the Raith and STS users will
laugh in my face, I'll stick my neck out and say that this simple system has
worked surprisingly well if you consider that this was also the reservation
rule that was used in the predecessor to Coral (Berkeley's Microlab AKA
Stanford's Crystal) that was originally released some time prior to 1985 ...
that is, 20 years ago.
Now I'm not proposing that we do nothing ... in fact, just the opposite. It
is painfully clear that the current approach fails badly when demand for
equipment time approaches 24x7. As I indicated previously, Bill Murray has
been working on putting the tools in place to improve the reservation system
since the first of the year. He is working on what I think can be called a
"rule based" system for making reservations. I believe that we can come up
with a reasonable set of rules that prevents hogging and gave everyone a
legitimate chance of getting reasonable blocks of time. Consider the very
simple prototype rule:
1. Your reservation has to START no more than 7 days from right now.
2. That reservation has to conform to some other rules related to duration of
a single reservation (including sub-rules for peak and off-peak usage times)
and collective total time of outstanding reservations.
This would immediately make 2 enormous improvement to the existing system:
Each reservation could be a useful lenght of time ... you would no longer have
to try to swap a bunch of individually useless 30 minute time segments for a
"real" reservation. Plus, you would not have to compete for each 30 minute
slot when it became available.
The advantage of a rule-based system is that it is easier to "publish",
understand, and fine tune. I would argue that playing with maximum "prime
time" reservation length and total outstanding reservation length (with, of
course, eliminating the need to compete for 30 minute blocks) would offer a
lot of flexibility. If simple rules didn't work, I'm sure that we
could come up with effective (if somewhat more complex) rules to "fine tune"
our allocation. Of course, this assumes that we have the infrastructure in
place to easily modify/add/delete reservation rules ... it is exactly this
infrastructure that Bill is putting in place.
What are my concerns with the "bid and then allocate" approach?
1. I fear it is not too convenient from a process perspective. I assume
that there would be multiple "bid/allocate" tools in the lab ... raith,
stsetch, and tylannitride, to name three. Suppose your are allocated a time
for patterning prior to your time for depositing a nitride layer and it is the
nitride layer that you are hoping to pattern? Supporting "process
constraints" (I need to deposit a layer before I pattern it) in addition to
all of the time based constraints sounds awfully complex.
2. What do you do about cancelled reservations? Is there a secondary bidding
system, or does it become the first one to grab it? Or do you need rules to
allocate who can compete for any reservations slots that weren't claimed at
bid time (or that were later released).
I am unaware of any existing, automated "bid/allocate" reservation systems.
This, to me, says one of 2 things:
1. It is harder to implement than it appears.
2. Other, simpler, approaches work better.
Most systems for allocating scarce resources seem to be simple and rule
1. First come, first served. ... Seat selection on Southwest Airlines.
2. Rules plus first come, first served ... tickets go on sale at 10 a.m. on
Sunday, each person in line can buy up to four tickets.
3. Rules (incentives) to encourage more use during "off hours" ... checked the
fares on flights leaving at 6 a.m. instead of at noon?
4. The "patron" model. Big donors get to select their seats before the
rest. (AKA the Opera model).
Now it is true that there are very sophisticated algorithm-based scheduling
systems for getting maximum throughput in a manufacturing facility ... and a
lot of PhDs have been awarded in industrial engineering and in the business
school developing even better algorithms. Of course a lot of effort also goes
into trying to figure out how to control access to and throughput on freeways
particularly during "prime time". However, these approaches are not likely to
result in short-term benefits in our setting.
I would argue that examples of commonly used and easily implemented means of
automatically allocating scarce resources are largely rule-based and that it
is the most useful avenue for us to explore.
Thank you all for your thoughtful discussion of these matters. A detailed
discussion of the pros and cons of various approaches to allocating
reservations will, I'm sure, result in a more workable system for all.
More information about the raith