Note 4/22/03 by Xin Zhang

each pair of ordering is one variable.  The ordering between i and j require
the same resources will become one variable.   For each variable consider both 
values, slack in both way, take the minimum of both way, then take the minimum
of the minimum, it will tell you this is the variable has the lower slack. 
This is the most constrained varibale.  Assign that ordering decistion the value
 for which the slack is higher.  This is the least constrained value.

There is another strategy called B-slack (B-slack = slack / sqrt(S), S is the 
ratio of the minimum and maximum slack of a given ordering), which is similarity 
measure to measure how tight the interval is.  If it's close to 1, it
means it's very tight; if it's close to 0, it means itis very large interval.
It's a kind of sinerio of comformant planning.  Suppose having multi-states, and
trying to find a distance of one of the states refer to some particular state, 
then the question becomes how you define the distance of the states. 


We can find the mimimum makespan schedule among schedules.  suppose we have
multiple SPN, SPN_1, SPN_2, ..., SPN_15, ..., SPN_25.  We wound out at SPN_25 based
on search.  Suppose we didn't find the best makespan dispatch at SPN_25, how do we
know we did much better makespan SPN_1.   The problem is that we don't do
optimization.  If we think we can use PCP to find best solution, it's still 
wrong.

The approach is that we can establish lower and upper bounds on overall schedule
end.  And repeatedly apply PCP to find the best solution within these bound.  We
can generate scheduel ignorning resource constraints to provide determination of
low bound.  Apply one or more dispatch scheduling procedures to provide upper
bound.  Then Apply PCP K times with "common deadlines" evenly distributed between
these bounds.  The worst makespan we can get at mostly, we can spend more time to 
get better solution.  

During search, we want to know which branch to take.  We may consider the plan with
lower bound. Pick the value which has better lower bound and makespan.  We know
upper bound, how to compute lower bound?  For the relax version of a perticular 
problem, compute the makespan, that will be a lower bound.  Suppose a ordering 
resources, based on the current set of ordering, we know the minimum makespan.  



Other Constraitn Propagation Ideas
-------------------------------------

  0 Arc-bounds propogation 
        
       [0, 12]-------> [0,12] ----------> [0, 12]

       ---------------------------------> forward propagation

       [0, 6 ]-------> [3, 9 ] ---------> [6, 12]

       <--------------------------------  backward propagation

    
      	All the activities are 3 units long.  First three activity can be as early as
      	0 and as late as 12.  We might want to get tigher bount.  For the last 
	activity, the earliest time is 6 unit, the latest time is 12 unit.  We can 
	reduce the domain.  Originally, the start time can be any point between 0 to 12. 
  	Just change the bound time by propogation.

   H-finding will give more bounds than other one, but it's costly.  Suppose we have
3 activities, all of them are 10 units long.  Least time is the deadline. There will not 
be any changes in the bounds.  


For each activity, compute the demand.

Example:

     Suppose we have an activity below using resource R1.  Clearly, beyond the resource
region, resource usage is 0.  


                          _________
                    =====|=========|===   (1) activity and resource
                         |____R1___| 

                     _________
                    |=========|========   (2) Resouce is needed as early as it
                    |____R1___| 
                            . .
                            . .
                             _________
                    ========|=========|   (3) Resource is needed as late as it
                            |____R1___| 
                            
                             __
                    ========|==|========  (4) The marked region is definitely need
                            |__|              the resource
                            

      So we will say is (4) region, the requirement for resource is 1. 


    The following is the probability demand for this problem:


               1                 ___
                                |   |
                                |   |
                          ______|   |_____
                         |                |    
               0    _____|________________|__________     
                 
     
      If there is another activity require resource R, so we have to draw this
similar figure too.  For resource R, we look at all of the activities that 
require it, add the figures up to get aggregate resource demand respect to time.
We have aggregate demand for eahc resource.  The constain is previous slack, now is the 
is the resource.  The variable ordering heuristic is to most difficult unassigned 
operation.   The start point is uniformly distributed in a feasible region. 


Classical planning has:

	o full observability: know which states are in at any time;
	o determinism: the action has deterministic effect;
	o static environment: the environment is not changing.

In pratice, having partial observability and non-deterministic actions are kind like
the same.