🚀 go-pugleaf

                   The University of Waterloo
                      200 University Avenue
                        Waterloo, Ontario


           The Institute for Computer Research (ICR)

                    Presents a Colloquium on

         Have We Achieved the Holy Grail of Schedulers?



by:     Dr. Mark S. Fox


of:     Department of Industrial Engineering
        University of Toronto


Date:   Wednesday, February 3, 1993  
Time:	3:30 pm.
Place:  William G. Davis Computer Research Centre, Room 1302



Abstract:


Conventional wisdom in the field of scheduling, is that  schedul-
ing  problems  exhibit such a richness and variety that no single
scheduling method is sufficient.  But in  the  last  five  years,
research   in  Artificial  Intelligence  constraint-directed  ap-
proaches to scheduling have demonstrated a surprising  degree  of
effectiveness   and   generality.    The  primary  components  of
constraint-directed scheduling are a problem  topology,  textures
and  objectives.   A  problem  topology  is represented by a con-
straint graph where nodes are activities and arcs are constraints
among the activities, e.g., temporal and resource.  A problem to-
pology my be altered by problem reformulations, such as  abstrac-
tion  and aggregation.  Problem textures are fundamental measures
of constraint graphs that indicate  decision  complexity,  uncer-
tainty   and  elasticity.   Texture  measures,  such  as:  "value
contention"--degree to which more than one variable may have  the
same  value;  "variable reliance"--degree to which a variable re-
lies  upon  the  assignment  of  a  particular  value;  "variable
looseness"--size  of  range  (conjunction  of constraints); "con-
straint tightness"--degree to which the  constraint  reduces  the
set  of  admissible  solutions; and, "constraint importance"--how
important is it to satisfy the constraint; are used to  determine
where  in  the  constraint graph the next decision is to be made,
i.e., variable and constraint selection.  Problem objectives  de-
fine what is to be optimized.

Two methods for assigning resources over time to each of the  ac-
tivities  have been used.  The "generative" method starts with an
empty schedule and iteratively selects and assigns  resources  to
each activity over time, and backtracks whenever a deadend (i.e.,
infeasibility) is reached.  The "repair"  method  starts  with  a
completed  schedule  containing  unsatisfied  (i.e., broken) con-
straints and iteratively selects and reassigns  resources  to  an
activity over time that satisfies as many unsatisfied constraints
as possible.  Search in  both  cases  ends  whenever  the  "best"
schedule  is  found  that  satisfies the constraints.  The repair
method can be augmented by  using  simulated  annealing  to  find
better  schedules.  Central to the approach is the measurement of
properties of the constraint graph, which we call textures, which
are  used  to  perform variable (i.e., activity) and value (i.e.,
resource and time) ordering.

This presentation will describe the constraint-directed  schedul-
ing  method  and  present a four level architecture for a general
scheduling system based on constraint-directed search.   The  ar-
chitecture   integrates   problem   acquisition,   generative-and
repair-based techniques, and schedule execution around  a  single
constraint graph representation.



Everyone is welcome.  Refreshments served.