La lecture en ligne est gratuite
Le téléchargement nécessite un accès à la bibliothèque YouScribe
Tout savoir sur nos offres
Télécharger Lire

cbs-tutorial

14 pages
--*Constraint-based SchedulingMarkus P.J. FromherzXerox PARC, 3333 Coyote Hill Road, Palo Alto, CA 94304, USAwww.parc.com/fromherzAbstract resources, constraints, and objectives from thealgorithms that solve the problem. This allows oneConstraint-based scheduling has become the to deal with a wider variety of constraints, facili-dominant form of modeling and solving scheduling tates the changing of the model, even dynamically,problems. Recently, due to ever more powerful em- without changing the algorithms, and enables thebedded processors, it has become possible to embed re-use of the model for other tasks, such as simula-and run constraint-based schedulers on-line even tion, planning, and diagnosis. Constraint solvingfor fast processes such as product assembly se- methods such as domain reduction, constraintquencing. This makes constraint-based scheduling propagation, and backtracking search have provedinteresting to the control community as a new tool to be well suited for many industrial applicationsfor system control, distributed and reconfigurable [23,17]. Today, these methods are increasinglycontrol, and the integration of various planning, combined with classic solving techniques from Op-scheduling, and control tasks. This tutorial gives a erations Research (OR), such as linear, integer,brief introduction to constraint-based scheduling, and mixed integer programming [5,37], to yieldgeneric constraint programming techniques for powerful tools ...
Voir plus Voir moins

-
-
*
Constraint-based Scheduling
Markus P.J. Fromherz
Xerox PARC, 3333 Coyote Hill Road, Palo Alto, CA 94304, USA
www.parc.com/fromherz
Abstract resources, constraints, and objectives from the
algorithms that solve the problem. This allows one
Constraint-based scheduling has become the to deal with a wider variety of constraints, facili-
dominant form of modeling and solving scheduling tates the changing of the model, even dynamically,
problems. Recently, due to ever more powerful em- without changing the algorithms, and enables the
bedded processors, it has become possible to embed re-use of the model for other tasks, such as simula-
and run constraint-based schedulers on-line even tion, planning, and diagnosis. Constraint solving
for fast processes such as product assembly se- methods such as domain reduction, constraint
quencing. This makes constraint-based scheduling propagation, and backtracking search have proved
interesting to the control community as a new tool to be well suited for many industrial applications
for system control, distributed and reconfigurable [23,17]. Today, these methods are increasingly
control, and the integration of various planning, combined with classic solving techniques from Op-
scheduling, and control tasks. This tutorial gives a erations Research (OR), such as linear, integer,
brief introduction to constraint-based scheduling, and mixed integer programming [5,37], to yield
generic constraint programming techniques for powerful tools for constraint-based scheduling.
modeling and solving scheduling problems, and a
* Recently, due to continuing increases in computa-concrete real-time application example.
tional power and available memory of embedded
processors, it has become possible to embed and1Introduction
run constraint-based schedulers on-line and in real
Scheduling is the process of allocating resources to time even for fast processes that demand solving
activities over time [3]. In a typical scheduling times on the order of tens or hundreds of millisec-
problem, resources are scarce and constrained in onds [13,17]. This development makes CBS inter-
various ways (e.g., in the capacity of resources and esting to the control community as a new tool for
the order of activities), and one is looking for a system control, distributed and reconfigurable con-
schedule of the activities that both satisfies the trol, and the integration of various planning,
constraints and is optimal according to some crite- scheduling, and control tasks. For the scheduling
rion (e.g., the length of the schedule). community, it highlights a set of concerns that are
much less prominent or non-existing in stand-
Scheduling problems are ubiquitous and appear in
alone, off-line scheduling applications [14].
many forms, from classic job-shop scheduling to
manpower and service scheduling, from product In this tutorial, I will first introduce scheduling in
assembly sequencing to logistics resource alloca- more detail and then concentrate on the presenta-
tion and scheduling. Scheduling has become an tion of constraint programming as the foundation
important component of business processes such as of CBS. I will then discuss various scheduling-
supply chain management, and it has its own specific extensions and scheduling variations, in-
range of successful software tool vendors. cluding concerns in embedded, real-time schedul-
ing. As a concrete example, I will present the use
Over the last decade, constraint-based scheduling
of constraint-based scheduling in print-engine con-
(CBS) has become the dominant form of modeling
trol, which has led to a set of technologies devel-
and solving scheduling problems [35,39,4,23]. CBS
oped at the Xerox Palo Alto Research Center and
separates the model the description of activities,
deployed in Xerox products. The primary purpose
of this tutorial is to give control researchers and
practitioners an overview of the workings and ca-*
Invited tutorial paper at the American Control Confer-
pabilities of current CBS techniques.
ence (ACC’01), Arlington, VA, June 2001.2Scheduling complex resource allocation or job-shop problems),
even where scheduling is automated, planning is
The traditional positioning of scheduling is be- still being done by hand or relies on a library of
tween planning and execution: for a set of desired plans prepared by human experts that allow a
products, a planner determines the sequence of simple mapping from products to plans. Even for
tasks (the plan) that will deliver the products, the schedulers, readability and modifiability of sched-
scheduler decides on the specific resources, opera- ules by humans is often an explicit requirement
tions, and their timing to perform the tasks (the due to the limitations of existing technology.
schedule), and an executor (or controller) then di-
In certain domains, however, both planning andrects the system’s resources to perform the opera-
scheduling can be completely automated and thustions at the specified times such that the products
embedded in an integrated control system. Oneare produced (Fig. 1). (Occasionally in the litera-
example is the planning and scheduling of paperture, the term “planning” is meant to include
transport and print operations on a modern, dy-scheduling. Here, planning generally means the
namically reconfigurable, multi-function print en-decision what to execute, and scheduling means
gine (copier, printer, fax machine, etc.). There,the decision when and how to execute it.)
planning and scheduling are part of the machine’s
system control software, and scheduling may be
User thought of as just another level in the system’s hi-
erarchy of controllers. Scheduling tends to considerProduct
higher-level or aggregate operations and take a
Planner longer-term view, and thus scheduling problems
are decidedly complex, combinatorial problemsPlan
that are in general NP-hard [21,18]. At the same
Scheduler
time, embedded schedulers are expected to have
Schedule the usual properties of lower-level controllers, such
as operating in parallel with the system’s execu-
Executor
tion (on-line scheduling) and in a feedback loop
Control (reactive scheduling), and providing results within
hard real-time boundaries (real-time scheduling).
System
Classical scheduling problems are often catego-
rized using the machine shop metaphor, such asFig. 1 Scheduling in context
flow shop, job shop, and open shop problems [7]. A
machine shop consists of a set of machines (or re-The terms involved are meant to be generic. Prod-
sources), each of which can work on one task at aucts may be physical products, but also lectures in
time. Jobs (e.g., the manufacturing of products)a university lecture timetabling problem, staff as-
consist of tasks, each of which requires a resourcesignments in a staff scheduling problem, or object
during its execution. Particular machine shoplocations in a logistics problem. Resources may be
problems differ in whether the order of tasks in amachines or machine components, people, or any
job is constrained (flow shop and job shop), and onother object that is able to perform a useful opera-
whether the use of resources is fixed (flow shop).tion. Tasks typically are individual steps available
Deterministic algorithms are known only for prob-from unspecified resources in the system, such as
lems with a few (2-3) machines and jobs.moving or transforming a product. Operations re-
fers to the specific capabilities of resources that
Although the metaphor of resources, jobs and tasks
perform particular tasks. The system is the collec-
can be generally applied to most scheduling prob-
tion of resources, from a single machine to a fac-
lems, real-life problems typically have a much
tory of machines to an organization of people, fac-
wider variety of constraints than just precedence
tories, vehicles, etc.
and resource constraints [39]. Constraint-based
methods have proved successful when problemsIn the setup of Fig. 1, complexity increases from
are hard (solutions not obvious, many hard con-the bottom up, and consequently applications often
straints, strong constraint interactions), when do-are less automated (i.e., require more human in-
main-specific and redundant constraints are avail-tervention or at least preparation) at the higher
able, and when problems change often [33].levels. For example, in many applications (such as




-





˛
˛
·










˛
-

·
£



3 Constraint Programming 3.1 Constraint problems
At its heart, scheduling is a constraint satisfaction A constraint satisfaction problem (CSP) is defined
and optimization problem.Thus,inconstraint- by a set of n variables x (i =1,…,n), a correspond-
i
based scheduling, tasks are represented by re- ing set of domains D (i =1,…,n) that declare thei
source selection and timing variables, possibly con- allowable values for each variable x , and a set of mi
strained by precedence constraints, resource con- constraints c (x ,…,x)( j =1,…,m) over the vari-
j 1 n
straints, routing conditions, and other restrictions. ables which restrict the allowable combinations of
The search space is the space of possible assign- variable values. More formally, a constraint is a
ments of tasks to resources and the concrete tim- mathematical relation which defines a subset S of
ings of tasks. As tasks are assigned to resources, the domain space D … D such that the con-
1 n
their timing variables are further constrained by straint is said to be satisfied for a variable assign-
resource constraints, such as limited capacities and ment x ,…,x = v ,…,v , v D (i =1,…,n), if1 n 1 n i i
setup delays. A solution a schedule is an as- v ,…,v S. A variable assignment is inconsistent1 n
signment to the resource and timing variables that if at least one constraint is not satisfied. The col-
specifieswhenthetaskshavetobeexecutedon lection of constraints is often called the constraint
what resources. Sometimes, a constraint-satisfying store.Asolution to the CSP is an assignment of
solution is sufficient, but often we demand an op- domain values to the variables that satisfies the
timal schedule. In that case, an objective function constraints. In short, a constraint satisfaction
defines the optimality criterion, such as schedule problem is defined as follows.
length, resource usage, or average or maximum
Given n variables x with domains D and m con-
i ilateness with respect to due dates.
straints c ,
j
Modern constraint solvers have their roots in at find a solution x ,…,x = v ,…,v
1 n 1 n
least three research communities [5,29]: Artificial such that v D i=1,…,n
i i
Intelligence (AI), which investigated constraint
c (v ,…,v ) j=1,…,mj 1 n
satisfaction problems (CSPs) with a focus on gen-
Before we look at variables and constraints ineral search procedures; Logic Programming, which
more detail, we can extend this definition to a con-led to constraint (logic) programming (CP/CLP)
strained optimization problem. A constrained op-with a focus on modeling and programmability;
timization problem (COP) is defined as a CSP withand Operations Research (OR) with a focus on effi-
an additional objective function h(x ,…,x)thatcient algorithms for restricted problem formula- 1 n
specifies a preference criterion between solutions.tions. Thus, CSP research has focused on the basic
That is, if the goal is to minimize h, then solutionmeans for representing and operating on con-
v ,…,v is preferred to solution v ’,…,v ’ ifstraints, in particular various forms of backtrack- 1 n 1 n
h(v ,…,v)<h(v ’,…,v ’). Consequently, a solutioning search algorithms [30]. CP added an explicit 1 n 1 n
programming component that allows programmers v ,…,v is optimal if h(v ,…,v ) h(v ’,…,v ’) for all1 n 1 n 1 n
other solutions v ’,…,v ’ . Without loss of general-to more easily and flexibly define how to combine 1 n
the basic constraint operations [35]. Today, solver ity, we assume that h is to be minimized. The con-
strained optimization problem is thus defined asalgorithms are increasingly augmented with tech-
follows.niques from OR for specific constraint systems,
such as linear constraints or constraints over reals
Given n variables x with domains D , m con-i i
[37]. In the following, I will take primarily a con-
straints c , and objective function h,
jstraint programming view and use “CP” to refer to
find a solution x ,…,x = v ,…,v
1 n 1 nthe combination of techniques just mentioned.
with minimal h(v ,…,v )
1 n
In the following, I will first introduce generic defi- subject to v D i =1,…, n
i i
nitions and techniques used for constraint satisfac- c (v ,…,v ) j =1,…, mj 1 n
tion and optimization problems. Later, I will pre-
sent some of the constraints and search algorithms
that have been added to address the specific char-
acteristics of scheduling problems.
3„
£
£
£
˛
£
˛
˛
Ù
˛
˛
˛
˛
˛
£
£
3.2 Modeling constraint problems tems and usually allow multiple constraint sys-
tems to be used in parallel. This generality and
Variables may be of various types, i.e., have differ- extensibility is part of what makes CP so attractive
ent types of domains: for scheduling applications with their diverse types
• integer domains [l,u] with a lower bound l and of constraints.
upper bound u, i.e., variables may take any
An objective function maybeassimpleasasingle
integral value in that range;
variable (e.g., representing the last task in a
• logical (or Boolean) domains [false,true], often schedule), or it may formalize more complex crite-
represented by integer variables with do- ria, including combinations of objectives, such as a
mains [0,1]; weighted sum of the individual objective functions.
• enumeration (or choice) domains representing
3.3 Solving constraint problemsa set of choices, often represented by integer
variables with range [1,k], where k is the
The usual way of solving finite-domain CSPs (andnumber of choices;
COPs) in CP is a combination of domain reduction,
• real domains with a lower and upper bound
constraint propagation, and search. To understand
which may take any real value in that range; these techniques and their various instances, it is
• set domains where each value is a set. best to think of a finite-domain CSP as a graph,
where the nodes are variables (represented by
Correspondingly, each variable type has its own
their current domains) and the edges are con-
types of constraints,suchas
straints between the variables (cf. table below).
• arithmetic constraints for integer and real
variables (e.g., 3x+y z); Domain reduction, constraint propagation
• Boolean relations for logical variables (e.g., x
Domain reduction is the direct application of a(y ÚØ z));
unary constraint c(x) to the variable x. For exam-
• set constraints (e.g., to enforce element and
ple, if x is an integer variable with current domain
subset relations).
[0,10] and c is x > 3, then the domain of x becomes
[4,10].Constraints over integer and related variables are
also called finite-domain constraints. They are of-
Constraint propagation is the propagation of
ten handled in similar ways and form the domi-
changes in one variable’s domain to the domains of
nant part of many solvers from the AI and CP
other variables connected by constraints. For ex-
communities. Many scheduling problems can be
ample, if x and y are integer variables with current
represented as finite-domain COPs. Also, finite-
domains [0,10], and a constraint x y–3 is added,
domain techniques are less well known than con-
we can immediately propagate the lower bound of x
tinuous optimization techniques in the control
to y, i.e., y’s domain becomes [3,10], and we can
community. I therefore focus on these in this pa-
propagate the upper bound of y to x, i.e., x’s domain
per.
becomes [0,7]. Furthermore, if a constraint x >3is
A set of primitive constraints (e.g., equality and added next, reducing x’s domain to [4,7], the new
inequality relations over integer expressions) to-
gether with rules for how to combine and derive Table 1 Propagation in a constraint graph
constraints is called a constraint system. Depend-
Operation Constraint graphing on the constraint system, constraints may be
linear or nonlinear over discrete or continuous
Define x and y.
x [0,10] y [0,10]variables and include equality, inequality, dise-
quality ( ), or special-purpose relations.
x y-3Add x y–3; x [0,7] y [3,10]More generically, however, variables, domains, and
propagate.
constraints may be of any arbitrary, application-
x y-3specific type without necessarily stepping outside Add x >3;
x [4,7] y [3,10]
reduce x,the CP framework. In fact, as the next section will
x y-3
demonstrate, many constraint programming tools propagate. x [4,7] y [7,10]
are parametric with respect to their constraint sys-




£



lower bound is propagated to y’s domain, which Refinement-based methods are the most common
becomes [7,10]. Table 1 gives a recap of this se- form of search in constraint programming. Here,
quence of operations. each of the variables is assigned a value incremen-
tally until a complete solution is found or a con-
Notice that, with a constraint like x y–3, only the straint is violated (“labeling”). If a constraint is
upper bound of x and the lower bound of y can be violated, the last assignment is undone and an al-
propagated. Propagation can often be attached to ternative value is chosen (“enumeration”). If no
or “indexed” by components of a domain represen- value assignment is consistent, search backtracks
tation. This realization has led to the introduction to a previously assigned variable, and so on. The
of so-called indexicals (or projection constraints), result is a depth-first tree search. The following is
efficient specialized edges in a constraint graph the corresponding pseudo-code.
that replace the original constraints [10]. For ex-
set X = x ,…,x ;ample, the constraint x y–3 can be represented 1 n
while there are unassigned variables in Xby the two indexicals lb(y) := max(lb(x)+3,lb(y)) and
select an unassigned variable x from X;ub(x):=min(ub(y)–3,ub(x)), where lb and ub denote
select a value v from the domain of x;the lower and upper bounds of the domains, re-
assign x = v;spectively. The first indexical, for instance, is “at-
backtrack if a constraint is violated;tached” to the lower bound of x’s domain and trig-
end whilegers propagation whenever that value changes.
More generically, a constraint c(x ,…,x)istrans-
1 n This algorithm contains primarily two choices,
formed to one or more indexicals “x in r”( i =i i namely variable selection and value selection. The
1,…,n), where r specifies the feasible values for x
i i order in which variables and values are selected
in terms of the other variables in the constraint. can have a significant impact on search efficiency,
and various heuristics exist for these choices thatThis form of constraint propagation leads to so-
try to minimize the need for backtracking. For ex-called arc-consistency [30], as it removes inconsis-
ample, heuristics that select variables with thetent values from the variables’ domains along the
smallest current domain and values that reduceedges (or arcs) of the graph. By itself, constraint
other variables’ domains the least through propa-propagation is an incomplete technique, since it
gation are known to lead to good performance indoes not remove all possible combinations of values
many applications [2].that are inconsistent. For example, the solution
x,y = 7,7 would not be a consistent solution in While such domain-independent heuristics can be
the above scenario, even though 7 is still in both effective, domain-specific heuristics are even bet-
domains. ter. This is of interest in the context of scheduling
problems, where prior knowledge about the prob-Because of this incompleteness, domain reduction
lem (e.g., the typical order of tasks) can be used asand constraint propagation have to be comple-
a heuristic (e.g., select variables and values in timemented by search. Note that search is usually in-
order, constrain the maximum total scheduleterleaved with constraint propagation: fixing a
length) [19].variable value during search may lead to further
propagation from that variable. For example, given Another choice is in the backtracking procedure.
the constraint problem above, if the search proce- Chronological backtracking – backtracking to and
dure selects 6 as the value for x,thedomainofy undoing previous variable and value selections in
becomes [9,10] through propagation. From the reverse order of assignment – is the easiest to im-
search point of view, the goal of domain reduction plement, often quite effective, and thus the most
and constraint propagation is to reduce the search common form used in constraint programming.
space as much as possible before and during However, various forms of “intelligent backtrack-
search. ing” have been explored in the CSP community. It
has been shown, for example, that “easy” problems
Search (with many solutions) sometimes lead algorithms
to make a wrong choice early on that is not de-
Search methods in constraint programming may
tected until much later during search [22]. In that
be divided into refinement-based methods and re-
case, instead of spending time on fruitless search
pair-based methods [34].
at the bottom of the search tree, a “backjumping”
5




£


£


£
algorithm will try to identify the earliest inconsis- until a solution is found. The following is the corre-
tent assignment and directly backtrack to that sponding pseudo-code.
variable.
set V = v ,…,v as initial solution for x ,…,x ;
1 n 1 n
Different degrees of arc-consistency embedded in while V is inconsistent
search lead to different degrees of lookahead, from select an inconsistent assignment x = v from V;
pure generate-and-test if no propagation is per- select a new value v’forx;
formed to full lookahead if complete network con- assign x = v’inV;
sistency is enforced [31,25]. Since full lookahead end while
can be costly to compute and add more in overhead
This algorithm again contains primarily two
than it saves in backtracking, backtracking search
choices, namely variable selection and value selec-
with partial (local) arc-consistency has been shown
tion. Well-known heuristics include selecting vari-
to perform best for a variety of constraint prob-
ables that violate the largest number of constraints
lems.
with values that decrease the number of violations.
If the constraint problem is an optimization prob- In the case of an optimization problem, repair-
lem, a refinement-based search can be augmented based methods can be combined easily with well-
easily with a mechanism that adds a new con- known optimization techniques such as hill climb-
straint h(x ,…,x )<h(v ,…,v ) every time a new so- ing or simulated annealing. In these cases, vari-1 n 1 n
lution v ,…,v is found. This forces subsequent able and value selection not only consider the re-
1 n
solutions to have increasingly better objective val- duction in constraint violation, but also the de-
ues and can be very effective in removing parts of crease in the objective function when selecting
the search tree. At the end, the last-found solution variables and values to repair.
is returned as the optimal solution. (This kind of
In contrast to refinement-based methods, repair-
optimizing search has been called branch-and-
based methods typically are not complete, i.e., they
bound search, not to be confused with the branch-
are not guaranteed to find the global optimum or
and-bound optimization technique used to solve
even a variable assignment that satisfies all the
integer optimization problems with continuous
constraints. Therefore, repair-based methods typi-
techniques.) A variation of this technique, which is
cally require additional termination criteria, such
effective in scheduling problems, is binary search,
as an upper limit on the number of repairs.
which keeps progressively narrower lower and up-
per bounds l and u on h(x ,…,x ). The algorithm Both classes of search algorithms may further be
1 n
augmented with randomization techniques. As al-first adds the constraint h(x ,…,x ) (l+u)/2. If a
1 n
ready noted, refinement-based search in particularsolution v ,…,v is found, u is set to h(v ,…,v );1 n 1 n
can be inefficient for “easy” optimization problems,otherwise, l is set to (l+u)/2+1. The new value for l
where many solutions exist and no strong upperor u is substituted in the objective bound h(x ,…,x )1 n
bound on the objective function helps during(l+u)/2 and search is restarted. This is repeated
propagation. Approximate techniques using ran-until l u, when the optimal solution is found. Yet
dom restarts and limits on backtracking have beenanother effective and popular variant is iterative
shown to be effective for a range of schedulingdeepening, where the limit l on h in the constraint
problems [4].h(x ,…,x ) l starts from a lower bound and is in-1 n
creased until a solution is found. This is effective if
4 Constraint-based Schedulingthe initial l is close to the optimum. A more recent
technique that has proved to be very effective for
large problems is so-called limited discrepancy 4.1 Modeling scheduling problems
search, which assumes that the chosen value heu-
Building on the CP representations and techniquesristic makes few mistakes, and which therefore
introduced above, various variable and constraintinitially limits the number of allowed deviations
types have been developed specifically for schedul-from the heuristic [20,38].
ing problems. Variable domains include
Repair-based methods start with a complete as-
• interval domains where each value is an in-
signment to the variables. If this assignment is
terval (e.g., start and duration);
inconsistent, i.e., at least one constraint is violated,
• resource variables for various classes of re-the assignment is “repaired” iteratively by assign-
sources.ing different values to one or more of the variables

£

£
˛
Ú

£

£
£
S
In scheduling applications, integer variables might or n-ary resources) allow tasks to overlap so long
be used to represent timings, interval variables to as the total amount of resource use at any time
represent tasks, logical variables to represent mu- does not exceed a given capacity limit. State re-
tual dependencies or exclusions, resource domains sources allow tasks to overlap if they require the
to denote classes of resources, etc. Higher-level same state (e.g., the state of a switch). In contrast
domains may also be defined in terms of lower- to renewable resources, consumable resources get
level domains; for example, interval variables are depleted with each use and have to be renewed
often represented as tuples of integer variables explicitly. Finally, tasks may or may not be inter-
that denote start and duration of the interval. ruptible, leading to the distinction between pre-
emptive and non-preemptive scheduling [28] (not
Scheduling-specific constraints include
further discussed here).
• interval constraints for interval variables
As an example, we can assign a unary resource r to(e.g., t t to express that task 1 has to occur
1 2
two tasks t and t by posting the constraints allo-1 2before task 2);
cate(r,t ) and allocate(r,t ). These constraints are
1 2• resource constraints for timing (integer or in-
equivalent to the disjunctive constraint t t t
1 2 2terval) variables (e.g., allocate(r,t) for resource
t . Explicit use of resource constraints allows the
1r and interval t to express that the task occu-
solver to use and reason about more efficient rep-
pies resource r during interval t).
resentations than with such disjunctive con-
Again, higher-level constraints may be defined in straints.
terms of lower-level constraints. For example, for
Instead of resource constraints with incremental
intervals t and t with start time variables t .s and1 2 i allocations, some constraint programming systems
duration variables t .d (i =1,2;t .d > 0), the interval
i i provide global constraints [1,36]. A sample global
constraint t t is equivalent to the integer con-
1 2 constraint useful for scheduling is the cumulative
straint t .s+t .d t .s.
1 1 2 constraint: given intervals t , resource uses u dur-i i
ing t , and resource capacity k, cumulative([t ,…],Resource constraints define and constrain the i i
[u ,…], k) is satisfied if, for every time point withavailable resources by restricting how multiple i
overlapping tasks and corresponding resource usesuses of a resource can be combined [1,5,27,17]. Re-
U at this time point, u k. In systems withoutsources are either renewable or consumable. Some u U
interval constraints, this constraint would be de-renewable resource types are depicted in Fig. 2.
fined as cumulative([s ,…], [d ,…], [u ,…], k), whereUnary resources r can handle only one task at a i i i
s and d correspond to the start and duration timestime. Volumetric resources (also called multi-unit i i
capacity capacity capacity
3
t
2
1 1
t t t t t t t
1 2 1 3 1 2 3
a) time b) time c) time
unary_resource(r), volumetric_resource(r,3), state_resource(r, [1,2]),
allocate(r, t ), allocate(r, t , 1), % use=1 allocate(r, t , 1), % state=11 1 1
allocate(r, t ) allocate(r, t , 2), % use=2 allocate(r, t , 2), % state=22 2 2
allocate(r, t , 1) % use=1 allocate(r, t , 2) % state=23 3
cumulative([t ,t ],[1,1],1)1 2
cumulative([ , , ],[1,2,1],3) cumulative([ , ],[1,1],1),t1 t2 t3 t1 t2
cumulative([ , ],[1,1],1)t1 t3
Fig. 2 Some types of resources: a) unary resource (tasks cannot overlap); b) volumetric re-
source (sum of task uses cannot exceed capacity (here 3) at any time; height indicates task use);
c) state resource (tasks can only overlap if they require the same state; color indicates state). In
all cases, length indicates task duration. The examples are shown with their definitions as re-
source and global constraints.
7
£
£
£

£
£
Ú
of the intervals, respectively. Other examples for 4.3 Scheduling
global constraint are the all-different constraint
As an example, a simple but complete job-shop(forcing all variables in a given set to have differ-
scheduling problem can be defined as a COP asent values) and the cardinality constraint (limiting
follows. Given are a set of jobs and a set of ma-the number of variables that a given value can be
chines. Each job consists of a set of tasks withassigned to) [36].
given durations to be processed in a given order on
One difference between using allocation con- assigned machines. Each machine can process only
straints and global constraints is that global con- one task at a time. The problem is to find a sched-
straints cannot be defined incrementally, i.e., all ule, i.e., a start time for each task, that minimizes
taskshavetobeknownwhentheconstraintis the makespan (the total length of the schedule, i.e.,
posted, which makes them less useful for on-line thetimeatwhichalljobsarefinished).
scheduling applications.
We can represent a task by an interval variable t,
The constraints presented so far are hard con- where t.s and t.d represent the start and duration
straints, i.e., they represent restrictions that must times of the task, respectively, and t.e = t.s+t.d is
be satisfied. Scheduling applications have led to its end time. We can further represent a machine
increased interest in soft constraints, i.e., restric- by a unary resource variable r. Assume that all
tions that can be relaxed if no feasible schedule can times are integers. Finally, the makespan is repre-
be found (in the allotted time). Examples are job sented by variable l. Then the following constraints
due dates or resource use preferences. Some tools apply.
provide specific soft constraint systems [12,6]. Al-
For every task t:0 t l.ternatively, soft constraints can often be added in
appropriate form to the objective function (e.g., For every task t, given duration d: t.d = d.
“minimize the difference between desired and ac- For every job with tasks t ,…,t :1 n
tual due dates”).
t t (i =1,…, n–1).i i+1
For every task t, given assigned machine r:
4.2 Scheduling-specific propagation tech-
allocate(r, t).
niques
The objective function is defined as h = l, i.e., the
Several scheduling-specific propagation techniques goal is to minimize l. Remember that, given the
have been developed, mostly concerning the rea- appropriate resource constraint system, a unary
soning about resources and intervals. In one tech- resource r with allocated tasks T automaticallyr
nique, resource timetables [26], a timetable with
enforces the constraints t t t t for all t ,t ini j j i i j
required and available capacity at any time is T . Alternatively, using global constraints, the re-r
maintained for each resource. Propagation be- source constraints could be defined as cumula-
tween resources and tasks works both ways: as a
tive(T , [1,1,…], 1) for each resource r with allo-r
task time becomes fixed, the task resource usage is cated task list T .
r
entered in the timetable; conversely, as available
In traditional, off-line / predictive scheduling,thiscapacity in the timetable is reduced, the interval
problem is solved by posting the constraints to thedomains of associated tasks are updated.
constraint solver and then calling the search pro-
Another technique, edge finding [9,32], reasons
cedure, e.g., minimize(X, l), where X is the list of
about the order in which tasks can execute on a all task intervals t and the variable l. This will in-
given resource. Each task is evaluated with respect
stantiate the variables in X, using the propagation
to a set of other tasks. If it is determined that the and search techniques presented above.
task must or cannot execute before (or after) these
In on-line / reactive scheduling, the tasks andtasks, it may be possible to infer new precedence
their constraints may become known only incre-constraints and new bounds on the task’s interval
mentally, and the scheduler may run concurrentlydomain.
to the execution of a previous (partial) schedule.
As mentioned before, depending on prior knowl- Furthermore, the constraints (e.g., the availability
edge about the scheduling problem, there may also
of resources) may change during scheduling and/or
be domain-specific redundant constraints and
execution, in which case part or all of the problem
search heuristics that lead to increased propaga- has to be rescheduled. The simplest approach to
tion and smaller search trees.
8







on-line scheduling is to treat the scheduling prob- in general, we found that, for a set of typical ma-
lem as a sequence of constraint problems, and to chines, we can always find a solution in polynomial
transfer commitments (variable assignments being time, and for a set of typical jobs, we can also find
“executed”) from one problem to the next. However, the best solution in polynomial time [17]. Also,
optimizations to this approach are possible and mitigating strategies may be available for atypical
necessary for real-time applications [14,24,11]. cases, such as slowing down the machine. Thus,
separating typical from average and worst-case
More generally, when embedding scheduling into a
scenarios can be fruitful for real applications.
control system, a set of unique requirements come
into play that require to adapt the constraint
4.4 On-line scheduling and model-predictive
solver to this environment. These issues include
control
memory management, real-time issues in updating
constraints and assigning variables, and the inter- Model-predictive control (MPC) [8] has become a
face to the control application [14]. popular control approach that has a number of in-
teresting similarities to CBS. In particular, MPCThere are many published examples for industrial
also takes a model-based approach in which theconstraint-based scheduling applications. (Descrip-
model, objectives, and constraints are stated ex-tion can for example be found on the Web sites of
plicitly as a COP, independently of the control pol-major tool vendors such as Ilog and Cosytec.) Ex-
icy. MPC also shares with on-line scheduling theamples for deployed real-time schedulers embed-
incremental nature of processing incoming re-ded in an on-board control system include Xerox’s
quests and the optimization of decisions with re-print-engine paper-path scheduler [17], NASA’s
spect to a horizon of known or predicted futureRemote Agent Planner and Scheduler (RAX-PS)
events.[24], and JPL’s Aspen planner and scheduler [11].
The Xerox scheduler is discussed in the next sec- While it is impossible to do justice to the various
tion. The RAX-PS system for NASA Ames’ Remote forms of MPC, it is instructive to highlight some of
Agent, part of the experimental spacecraft Deep the differences and similarities between CBS and
Space One, was supported by a constraint solver MPC. Recall that in scheduling we are given n
with customized (depth-first) search strategies and tasks with times t , m constraints c , and objectivei j
fast operations for on-line constraint management. function h, resulting in the COP
JPL’s Aspen planner and scheduler for NASA
find a solution t ,…,t = v ,…,v1 n 1 nspacecraft contains an on-line constraint manage-
with minimal h(v ,…,v )
1 nment system and provides real-time response by
subject to c (v ,…,v ) j =1,…, mj 1 nusing iterative repair techniques.
In on-line scheduling, this is the COP at a particu-
Complexity lar time step k,andthetasks t ,…,t represent
1 n
the horizon at that time (with t > k, i =1,…,n).
i
Unfortunately, most real scheduling problems are More tasks and constraints may be added in sub-
NP-hard [21,18]. Scheduling problems can some- sequent time steps as they become known. At each
times be made easier by relaxing certain assump- time step k,thegoal,initssimplestform,isto
tions, e.g., by allowing to preempt tasks. However, identify which task(s) to start next. Depending on
most research has emphasized finding generic
the solution times v ,…,v , a single, multiple, or1 n
heuristics and enabling programmers to guide al- no tasks t may be scheduled to execute next (con-
i
gorithms with domain-specific knowledge. Hence
cretely all those with times v = k+1 in this exam-i
the move to “glass-box” constraint solvers, which
ple). The variables of these tasks thus become
are parametric not only with respect to constraint committed and no longer appear as variables at
systems but even with respect to propagation
subsequent time steps.
rules [10].
In a discrete state-space formulation of MPC, we
For specific real-time applications, it is useful to
start from a process model
perform a dedicated complexity analysis. As an
x = Ax + Buk+1 k kexample, we analyzed the complexity of the paper-
y = Cx
k+1 kpath scheduler presented below by considering
both typical and worst-case system configurations. that predicts the evolution of system state x and
While the scheduling problem is still exponential system output y over time, given control input u
9

-



and system, input, and output matrices A, B,and 5 Application Example: Constraint-based
C, respectively. (x, y,andu are in general vectors.) Scheduling for Paper-path Control
In a simple control example, we are given a refer-
Modern digital reprographic systems come in manyence trajectory r , i = k+1,…,k+n, for a horizon of n
i
forms, from low-end printers to high-end multi-steps at time step k, together with m constraints c ,j
function devices. They typically consist of a sourceresulting in the COP
of paper and images, a paper path that brings
find a solution u ,…,u = v ,…,vk+1 k+n k+1 k+n these together at the right time, place and orienta-
with minimal h(v ,…,v )
k+1 k+n tion, and finishing components that collate, sort,
subject to c (v ,…,v ) j =1,…, mj k+1 k+n staple and bind the resulting, marked sheets. As a
where h requires the system output to match the concrete example for how CBS can be used in a
reference trajectory, e.g., real-time control environment, this section pre-
sents its use in paper-path control at Xeroxk +n 2h = (r y ) ,
i ii=k+1 [17,15,16,14].
with y defined by the process model as a function
i 5.1 Architecture and control process
of the current system state x and the control in-k
puts u = v . The constraints c typically encode lim-i i j Large machines are typically split into modules
its on control and output values. such as feeder, mark engine, and finisher, which in
turn consist of components such as feed trays,In contrast to tasks t in scheduling, the order ofi
1
transport belts, sheet inverters, etc. As a concretereference points r and control inputs u is fixed and
i i
example, consider a sheet inverter with its twogiven. Also, the solution values v in MPC do noti
modes of operation (Fig. 3): either the sheet isrepresent different tasks, but the values of the
guided by the inversion gate from the input rollerssame control “task” at different times. Thus, at
down into the inversion rollers, where it is stoppedeach time step k, the goal is to determine at what
and then moved in reverse direction up andvalue to set the next control input, u .Theresult-
k+1
through the output rollers (inverting it from face-ing state x becomes the new “start” state for thek+1
up to face-down orientation or vice versa), or it isnext time step, and the horizon is extended accord-
guided by the inversion gate directly to the outputingly.
rollers (leaving its orientation unchanged).
From a constraint programming perspective, on-
line scheduling and MPC have several common resources:
requirements. Both work incrementally on a resource: space
stream of requests (tasks, reference points), and gate position
port: in port: out
have to be reactive in the sense that tasks, states,
and reference trajectories may change over time
from their original or predicted values. Further-
control: parameters:more, both generally use a full optimization with
bypass path dimensionsminimal commitment approach [13]: while the
or invert (lengths, widths)variable assignment for the next step to be exe-
cuted is part of an optimal solution for all vari-
ables, the other variables are to be kept open in
parameters:work unit: sheet
case more information becomes available (in the roller speed, acceleration
form of new or changed tasks and reference points,
respectively). In other words, the optimizer is to
Fig. 3 Schematic view of a machine com-
return a solution for the next step only, but guar-
ponent (inverter) and its model elementsanteethatitispartofanoptimalsolutionforall
known future steps. Because of these similarities,
The hierarchical control software architecture mir-
it is to be expected that constraint-based schedul-
rors the architecture of the machine, with low-level
ing and model-predictive control will benefit from
each other’s techniques as common needs and ge-
neric solutions are better understood.
1 All examples of machine configurations and use scenar-
ios are realistic but simplified, and none should be taken
as describing an existing or future Xerox product.
10

Un pour Un
Permettre à tous d'accéder à la lecture
Pour chaque accès à la bibliothèque, YouScribe donne un accès à une personne dans le besoin