[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Planning and scheduling survey.
From our recent attendance at the SLUG '90 conference, it has
become very obvious that a significant fraction of Symbolics customers
are engaged in work on planning and scheduling applications. It seems
possible that some E-mail discussion of the subject may be of interest
to a reasonable number of SLUG members. To further that end, I made up
a brief, informal survey which I hope will shed some light on where
there are significant similarities and differences among ongoing
projects. Hopefully, this can serve as a springboard into some
interesting discussions.
I've also provided the answers to this survey for OPTIM, the
particular planning and scheduling application that we're working on
here. This serves the dual purpose of disseminating information as well
as providing example answers which may help to illuminate my rather
vague survey questions.
Before anyone responds to the actual content of this message,
however, I think we need a preliminary meta-discussion. I'm concerned
about not generating overwhelming amounts of E-mail and swamping those
SLUG readers who would rather not see it. On the other hand, perhaps
the response to this wouldn't be voluminous enough to be a problem.
Some obvious alternatives are:
1) Just go ahead and discuss this topic on the SLUG list.
2) Everyone respond to me privately, then I summarize the responses and
post them back on SLUG. I would be glad to do this but my fear is that
by not having a "free for all", I might stifle any ensuing conversation.
3) Create a special mailing list for this purpose. Unfortunately, it
would be infeasible for me to establish this at Lockheed (because of
internal networking issues).
4) Move this discussion to another, already established mailing list.
This might be good unless it results in too much dilution of the
potential discussion.
Opinions?
(Remember: don't respond to the rest of the message yet.)
--------------------------------------------------------------------------------
Survey Questions
1) What kind of problem are you trying to solve? Is it a very specific,
"in house" problem or a rather general kind of problem?
2) Is your design based on any particular field of operations research?
If so, how?
3) Is your design based on any particular field of AI research? If so,
how?
4) What approach(es) do you use generate schedules? For example, do you
generate schedules constructively? Find them using search? Do
something else?
5) What is your general system architecture?
6) What is the status of your project?
7) How much effort have you devoted to the user interface? Has this
paid off?
8) By what criteria do you judge "good" schedules?
9) Do you deal with the issue of predictive versus reactive scheduling?
10) How do you deal with an overconstrained problem? Do you provide for
any ability to relax constraints?
11) Are there any stochastic elements in your system? If so, what (for
example, uncertain task durations, uncertain process yields, uncertain
resource availability, etc.)?
12) Do you use Statice to store data?
13) Do you use Joshua in your system? Something similar (ART, KEE, etc)?
--------------------------------------------------------------------------------
Answers for the "OPTIM" System
1) Very general planning and scheduling. Particularly, anything from
problems which are classified as "project management" to a generalized
version of "job shop scheduling". Additional dabbling in "factory floor
layout". No work in "assembly line balancing".
2) We have no particular operations research basis in the system design.
We do have one operations researcher on staff to keep us all aware of
that perspective.
3) Both search and knowledge representation issues figure in our design
(at least, the way I conceive of it). However, in each case they are
more or less implicitly embodied in our system. We are very interested
in incorporating the ideas from blackboard systems but haven't started
on that yet. Interestingly, we don't particularly rely on any work from
the field of planning and problem solving (as described in the "Handbook
of Artificial Intelligence").
4) We have a hybrid constructive/search procedure. Our Scheduler
constructs schedules heuristically and the resulting solution space is
searched using constrained combinatorial optimization.
5) The architecture is fairly simple. A collection of objects (such as
tasks and resources) is manipulated through the user interface in order
to specify the problem. Computing a solution (schedule) involves
reducing the rich object-oriented model into a more compact internal
representation, constructively generating schedules, and then searching
for an optimum solution.
6) Our project is currently in Beta Test. Two (internal) customers are
currently experimenting with the system and providing feedback. A third
customer appears imminent. We would like the system to be in production
use by November.
7) Significant effort devoted to the user interface (I would say 50%+).
We feel that this is essential in order to get the system used. Key
features of the user interface are that it is reconfigurable for
different classes of users, very interactive (thanks to DW), highly
graphical, and has a fairly decent help system. The majority of our
feedback still seems to be requests for UI improvements.
8) Currently we compute optimum schedules only by the maximum completion
time (the "make-span" in operations research jargon). Making this more
elaborate is one of the obvious next issues for us to address.
9) We deal with reactive scheduling by allowing the user to get "some"
answer "fast" but a better answer if they are willing to wait "long
enough".
10) We currently fail when a problem is overconstrained. No constraint
relaxation.
11) No stochastic elements are currently in our system.
12) We don't currently use Statice. It's very likely that we will be
using it by Genera 8.1, however.
13) We don't currently use Joshua or any other commercial product.