Raith (and other tools) scheduling: another idea...

John Shott 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
based including:

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.

Thanks,

John





More information about the raith mailing list