NetNews Usenet Archive 1992 #18/NN_1992_18.iso/spool/comp/ai/3120

Internet Message Format | 1992-08-17 | 4.3 KB

Path: sparky!uunet!cs.utexas.edu!usc!sdd.hp.com!elroy.jpl.nasa.gov!ames!purdue!news.cs.indiana.edu!umn.edu!noc.msc.net!uc.msc.edu!apctrc!zwsd06
From: [e-mail] (Bill Davis)
Newsgroups: comp.ai
Subject: Re: planning/scheduling
Message-ID: <[e-mail]>
Date: 17 Aug 92 18:32:50 GMT
References: <[e-mail]>
Sender: [e-mail]
Organization: Amoco Production Company, Tulsa Research
Lines: 74

In article <[e-mail]> [e-mail] (Dave Pensak) writes:
>We have been approached by a local psychiatric hospital to see if
>any of our scheduling folks can help them with the following problem:
>
>There are N patients
>
>There are M staff members  (N >> M)
>
>There are I activities in J locations throughout the day
>
>Is there any machine assisted way to make sure that the best possible
>staff combinations are associated with the right group of patients
>throughout the day (the groupings can, and do, change during the day).
>...
>Add to this the problem that there are (semi)random perturbations
>both throughout the day (patients wandering off...., unexpected
>medical tests, etc) and between days (staff calling in sick, etc).

Planning and scheduling are two very distinct things; and yet, when
facing complex "real-world" problems, they are often interdependent
when deriving a solution.  Broadly speaking, one can't begin to schedule
until one determines which tasks must take place, what causal dependencies
exist among them, and what constraints exist on resource assignments.
Scheduling may then impose further constraints on the actual placing of
the events to a timeline, and identifying specific resources and their
quantities for each task in the plan.  A perspective I like is this:
You need planning when there are many possible tasks and combinations of
tasks from which to select an appropriate subset that will acheive a
stated (set of) goal(s);  You need scheduling when the tasks and their
relative order are known but they must be positioned on a timeline so as
to meet duration constraints (deadlines, etc) and resource constraints
(maximize throughput, minimize workload, etc.).

This is of course a generalization.  What happens when the schedule
"doesn't fit" the deadline?  More planning must be done possibly to
select an alternative set of tasks which still accomplish the goal but have
different temporal or resource constraints.  There are many such examples.

You must determine if the I activities above are fairly static and routine.
If so, then the problem is more of a resource assignment/scheduling
problem, and constraint satisfaction solutions are what you're looking for.
Mark Fox & others working in knowledge-based scheduling (a la constraint-
directed search) is where you might want to look.

If they aren't, and I suspect that's the case from your "disclaimer" about the
semi-random perterbations, then you have a more complex problem.  This would
be the case if the set of tasks changes according to the context of
the situation -- i.e., there may be a number of ways to accomplish some
goal, but which tasks and in what combination/order depends on the context
in which they're executed.  This involves planning *and* scheduling.

Deriving "the best" (optimum) solution in either of these paradigms is
at least an NP-hard problem (i.e., computationally intractable).
However, one can possibly derive a "good" solution from knowledge-based
approaches.  For the planning *and* scheduling problem, look into work
on the SIPE and O-Plan systems.  SIPE was developed by David Wilkins at
SRI International; this is best documented in his book "Practical Planning"
(Morgan Kaufmann).  O-Plan was originally developed by Austin Tate, and
continues development under his direction at the AI Applications Institute
in Edinburgh, Scotland.  A recent AI Journal article (vol. 52 #1) reports
on this system.

Building a system such as these domain-independent planners is a monumental
task.  I can't imagine it would be much simpler for a domain-specific
application, assuming you want to "do it right" (my bias :-) and keep
the planning mechanisms separate from the domain knowledge.

Good Luck!

--
Bill Davis                      [e-mail]
Amoco Production Research       [phone]
P.O. Box 3385, Room 1A10         fax  [phone]
Tulsa, OK 74102