Note taker:     Tuan Chi Le (lctuan@asu.edu)
Reviewed by:	Minh Binh Do
Date:           Feb. 21
Subject:        Cont'd on Scheduling
                Pls. comment. Thanks!
--------------------------------------------------------
Reading: The paper of Beck & Fox: Generic Framework
	 for Constrained-Directed Search & Scheduling
--------------------------------------------------------

The plan for today:

1. Propagation:
 + ARC-Bounded technique
 + Edge-finding technique
2. Variable ordering
 + Contention-based ORR-FSS
 + PCP-SLACK
3. Solving (local search)
 + EBL/DDB

In a specific scheduling problem, people often talk about
resources: Single capacity/shared resources, consumable resources,
metric resources. In Job-Shop-Scheduling (JSS), the problem is dealing 
with single capacity resources. The metric resources for JSS is described
in terms of time. However, the jobs in a scheduling is not always known
before a scheduler start its job, the jobs can be given "on the fly", these
are called run-time jobs. An example is about processes in an operating system,
waiting in a queue for despatching.

The JSS has a rather clear problem specifications, in which: 
+ All requirements, jobs, machines needed are known before hand. 
+ JSS can be solved by one of two ways: Integer Linear Programming-based
  (ILP-base) or CSP-based approach.

If we take CSP-based approach, the next questions will be: what search solver
should be used, what propagation techniques are appropriate, what heuristics 
methods would be used.

As we may known (from Smith's paper or other sources), a search solver can be 
systematic or local, of course, there are a bunch of search solver lie in between
these main streams. We are more interested in these two extremes. 

*If we use systematic search, then there are three issues that should be addressed:
+ constraints propagation approaches
+ variable ordering approaches
+ backtracking approaches

A standard propagation can be considered as the degree of consistency. A CSP 
problem can be solved by legal compound labels and illegal sub-assignment 
propagation approaches. The legal compound labels tries to prunes choices, 
whilst the illegal sub-assignment approach derives new "no-good" choices.

There are two techniques in propagation: arc-bounded and edge-finding techniques
in arc-bounded technique, n^2 combinations are considered whilst in edge-finding
technique, each time just consider one task among a set of taks and to find the
earlest starting time task to commit to. (more on this in the next class)

In using systematic search, variable ordering means which variables we should 
commit to. In scheduling this means which task to sequence (or despatch) next.

Backtracking: when adding a new constraint and that addition leads to an 
incosistency, we need to do backtracking to retract that constraint. The question
is then, what we will do with the constraints added before this point ?

*If we use local search, we will try to make a complete assignment to see whether
that assignment is OK or not, if it is then we are done, otherwise, we need to 
identify what are the reason for that and try to improve that to get closer to 
the solution. The local search strategy is not complete in the sense that it does 
not give the ability to deal with optimization. We also know that, if we do not
use systematic search strategy, we can not assure the optimization of solutions.
Systematic search in ILP stops when  an optimal solution is found.

Optimization:

An interesting issue is addressed: Pareto optimization. The idea of this kind of 
optimization is  that no local assignment change that can improve further the 
solution.

There're 2 notions of optimization:
+ CSOP: Constraint Satisfaction Optimazation problem: there exists an objective 
	function so that we can based on it to optimize solutions.
+ PCSP: Partial Constraint Satisfaction Problem:no objective function. Constraints
	are assigned with cost. This way can find optimization without doing complete 
	search.

An example is given to explained arc-bounded technique:

		[**********] 			Task1, resource: R1 (duration: d1)]
	|---------------------------|
	est1			    lft1

			[**********] 		Task2, resource: R1 (duration: d2)]
		|-----------------------------------|
		est2				    lft2

Two task: T1 & T2, 
suppose A = lft2 - est1
	B = lft1 - est2
	C = d1 + d2

We have 4 cases:
1. A < C & B < C 	==> fail
2. A < C <B 		==> T1 < T2 (T1 before T2)
3. A > C & B > C	==> fail
4. B < C < A		==> T2 < T1