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 ** T1 < T2 (T1 before T2)
3. A > C & B > C ==> fail
4. B < C < A ==> T2 < T1**