home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #3 / NN_1993_3.iso / spool / ont / events / 646 < prev    next >
Encoding:
Internet Message Format  |  1993-01-27  |  4.0 KB
  1. Xref: sparky ont.events:646 uw.talks:123 uw.cs.grad:294
  2. Newsgroups: uw.icr,ont.events,uw.talks,uw.cs.grad
  3. Path: sparky!uunet!watmath!watserv2.uwaterloo.ca!watserv1!icr.uwaterloo.ca!ylkingsb
  4. From: ylkingsb@icr.uwaterloo.ca ()
  5. Subject: ICR Presents a Colloquium on "Have We Achieved the Holy Grail of        Schedulers", on Wednesday, February 3, 1993, at 3:30 pm. in DC 1302.
  6. Message-ID: <C1J5t6.4xw@watserv1.uwaterloo.ca>
  7. Keywords: Speaker:  Dr. Mark S. Fox, Department of Industrial Engineering,       University of Toronto.
  8. Sender: news@watserv1.uwaterloo.ca
  9. Organization: University of Waterloo
  10. Distribution: uw
  11. Date: Wed, 27 Jan 1993 20:48:41 GMT
  12. Lines: 82
  13.  
  14.  
  15.  
  16.                    The University of Waterloo
  17.                       200 University Avenue
  18.                         Waterloo, Ontario
  19.  
  20.  
  21.            The Institute for Computer Research (ICR)
  22.  
  23.                     Presents a Colloquium on
  24.  
  25.          Have We Achieved the Holy Grail of Schedulers?
  26.  
  27.  
  28.  
  29. by:     Dr. Mark S. Fox
  30.  
  31.  
  32. of:     Department of Industrial Engineering
  33.         University of Toronto
  34.  
  35.  
  36. Date:   Wednesday, February 3, 1993  
  37. Time:    3:30 pm.
  38. Place:  William G. Davis Computer Research Centre, Room 1302
  39.  
  40.  
  41.  
  42. Abstract:
  43.  
  44.  
  45. Conventional wisdom in the field of scheduling, is that  schedul-
  46. ing  problems  exhibit such a richness and variety that no single
  47. scheduling method is sufficient.  But in  the  last  five  years,
  48. research   in  Artificial  Intelligence  constraint-directed  ap-
  49. proaches to scheduling have demonstrated a surprising  degree  of
  50. effectiveness   and   generality.    The  primary  components  of
  51. constraint-directed scheduling are a problem  topology,  textures
  52. and  objectives.   A  problem  topology  is represented by a con-
  53. straint graph where nodes are activities and arcs are constraints
  54. among the activities, e.g., temporal and resource.  A problem to-
  55. pology my be altered by problem reformulations, such as  abstrac-
  56. tion  and aggregation.  Problem textures are fundamental measures
  57. of constraint graphs that indicate  decision  complexity,  uncer-
  58. tainty   and  elasticity.   Texture  measures,  such  as:  "value
  59. contention"--degree to which more than one variable may have  the
  60. same  value;  "variable reliance"--degree to which a variable re-
  61. lies  upon  the  assignment  of  a  particular  value;  "variable
  62. looseness"--size  of  range  (conjunction  of constraints); "con-
  63. straint tightness"--degree to which the  constraint  reduces  the
  64. set  of  admissible  solutions; and, "constraint importance"--how
  65. important is it to satisfy the constraint; are used to  determine
  66. where  in  the  constraint graph the next decision is to be made,
  67. i.e., variable and constraint selection.  Problem objectives  de-
  68. fine what is to be optimized.
  69.  
  70. Two methods for assigning resources over time to each of the  ac-
  71. tivities  have been used.  The "generative" method starts with an
  72. empty schedule and iteratively selects and assigns  resources  to
  73. each activity over time, and backtracks whenever a deadend (i.e.,
  74. infeasibility) is reached.  The "repair"  method  starts  with  a
  75. completed  schedule  containing  unsatisfied  (i.e., broken) con-
  76. straints and iteratively selects and reassigns  resources  to  an
  77. activity over time that satisfies as many unsatisfied constraints
  78. as possible.  Search in  both  cases  ends  whenever  the  "best"
  79. schedule  is  found  that  satisfies the constraints.  The repair
  80. method can be augmented by  using  simulated  annealing  to  find
  81. better  schedules.  Central to the approach is the measurement of
  82. properties of the constraint graph, which we call textures, which
  83. are  used  to  perform variable (i.e., activity) and value (i.e.,
  84. resource and time) ordering.
  85.  
  86. This presentation will describe the constraint-directed  schedul-
  87. ing  method  and  present a four level architecture for a general
  88. scheduling system based on constraint-directed search.   The  ar-
  89. chitecture   integrates   problem   acquisition,   generative-and
  90. repair-based techniques, and schedule execution around  a  single
  91. constraint graph representation.
  92.  
  93.  
  94.  
  95. Everyone is welcome.  Refreshments served.
  96.