Vous aimerez aussi


*
Constraintbased 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
Constraintbased 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 reuse of the model for other tasks, such as simula
and run constraintbased schedulers online even tion, planning, and diagnosis. Constraint solving
for fast processes such as product assembly se methods such as domain reduction, constraint
quencing. This makes constraintbased 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 constraintbased scheduling, and mixed integer programming [5,37], to yield
generic constraint programming techniques for powerful tools for constraintbased scheduling.
modeling and solving scheduling problems, and a
* Recently, due to continuing increases in computaconcrete realtime application example.
tional power and available memory of embedded
processors, it has become possible to embed and1Introduction
run constraintbased schedulers online 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 nonexisting in stand
Scheduling problems are ubiquitous and appear in
alone, offline scheduling applications [14].
many forms, from classic jobshop 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, realtime schedul
ing. As a concrete example, I will present the use
Over the last decade, constraintbased scheduling
of constraintbased scheduling in printengine 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 jobshop 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, dyscheduling. Here, planning generally means the
namically reconfigurable, multifunction print endecision 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
higherlevel or aggregate operations and take a
Planner longerterm view, and thus scheduling problems
are decidedly complex, combinatorial problemsPlan
that are in general NPhard [21,18]. At the same
Scheduler
time, embedded schedulers are expected to have
Schedule the usual properties of lowerlevel controllers, such
as operating in parallel with the system’s execu
Executor
tion (online scheduling) and in a feedback loop
Control (reactive scheduling), and providing results within
hard realtime boundaries (realtime 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 reThe 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 probfrom unspecified resources in the system, such as
lems with a few (23) 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, reallife 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]. Constraintbased
methods have proved successful when problemsIn the setup of Fig. 1, complexity increases from
are hard (solutions not obvious, many hard conthe bottom up, and consequently applications often
straints, strong constraint interactions), when doare less automated (i.e., require more human in
mainspecific and redundant constraints are availtervention or at least preparation) at the higher
able, and when problems change often [33].levels. For example, in many applications (such as
2˛

˛
˛
·
˛

·
£
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 constraintsatisfying 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 conled to constraint (logic) programming (CP/CLP)
strained optimization problem. A constrained opwith 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 generalto 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 coni 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 finitedomain 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 finitedomain 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 finitedomain 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 finitedomain 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 specialpurpose relations.
x y3Add x y–3; x [0,7] y [3,10]More generically, however, variables, domains, and
propagate.
constraints may be of any arbitrary, application
x y3specific 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 y3
demonstrate, many constraint programming tools propagate. x [4,7] y [7,10]
are parametric with respect to their constraint sys
4£
£
lower bound is propagated to y’s domain, which Refinementbased 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 socalled indexicals (or projection constraints), result is a depthfirst tree search. The following is
efficient specialized edges in a constraint graph the corresponding pseudocode.
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 excalled arcconsistency [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 propapropagation 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 domainindependent heuristics can be
the above scenario, even though 7 is still in both effective, domainspecific heuristics are even bet
domains. ter. This is of interest in the context of scheduling
problems, where prior knowledge about the probBecause 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 refinementbased methods and re
case, instead of spending time on fruitless search
pairbased 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 pseudocode.
variable.
set V = v ,…,v as initial solution for x ,…,x ;
1 n 1 n
Different degrees of arcconsistency embedded in while V is inconsistent
search lead to different degrees of lookahead, from select an inconsistent assignment x = v from V;
pure generateandtest 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) arcconsistency has been shown
tion. Wellknown 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 refinementbased 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, vari1 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 lastfound solution variables and values to repair.
is returned as the optimal solution. (This kind of
In contrast to refinementbased methods, repair
optimizing search has been called branchand
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
andbound optimization technique used to solve
even a variable assignment that satisfies all the
integer optimization problems with continuous
constraints. Therefore, repairbased 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 alfirst adds the constraint h(x ,…,x ) (l+u)/2. If a
1 n
ready noted, refinementbased 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 ranuntil 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 in1 n
creased until a solution is found. This is effective if
4 Constraintbased Schedulingthe initial l is close to the optimum. A more recent
technique that has proved to be very effective for
large problems is socalled 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 schedulfrom the heuristic [20,38].
ing problems. Variable domains include
Repairbased 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 rethe assignment is “repaired” iteratively by assign
sources.ing different values to one or more of the variables
6£
£
£
˛
Ú
£
£
£
S
In scheduling applications, integer variables might or nary 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. Higherlevel 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 nonpreemptive scheduling [28] (not
Schedulingspecific 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 allo1 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, higherlevel constraints may be defined in straints.
terms of lowerlevel 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 duri 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 derenewable 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 multiunit 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 alldifferent constraint
As an example, a simple but complete jobshop(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 mathe 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 online 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 Schedulingspecific propagation tech
allocate(r, t).
niques
The objective function is defined as h = l, i.e., the
Several schedulingspecific 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 rer
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 allor
task time becomes fixed, the task resource usage is cated task list T .
r
entered in the timetable; conversely, as available
In traditional, offline / 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 online / reactive scheduling, the tasks andtasks, it may be possible to infer new precedence
their constraints may become known only increconstraints 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 domainspecific 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
online 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 realtime applications [14,24,11]. cases, such as slowing down the machine. Thus,
separating typical from average and worstcase
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 Online scheduling and modelpredictive
solver to this environment. These issues include
control
memory management, realtime issues in updating
constraints and assigning variables, and the inter Modelpredictive 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 modelbased approach in which theconstraintbased scheduling applications. (Descrip
model, objectives, and constraints are stated extion can for example be found on the Web sites of
plicitly as a COP, independently of the control polmajor tool vendors such as Ilog and Cosytec.) Ex
icy. MPC also shares with online scheduling theamples for deployed realtime schedulers embed
incremental nature of processing incoming reded in an onboard control system include Xerox’s
quests and the optimization of decisions with reprintengine paperpath scheduler [17], NASA’s
spect to a horizon of known or predicted futureRemote Agent Planner and Scheduler (RAXPS)
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 RAXPS 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 (depthfirst) search strategies and tasks with times t , m constraints c , and objectivei j
fast operations for online 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 online constraint manage
with minimal h(v ,…,v )
1 nment system and provides realtime response by
subject to c (v ,…,v ) j =1,…, mj 1 nusing iterative repair techniques.
In online 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
NPhard [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 domainspecific knowledge. Hence
cretely all those with times v = k+1 in this exami
the move to “glassbox” 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 statespace formulation of MPC, we
For specific realtime 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 worstcase 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: Constraintbased
C, respectively. (x, y,andu are in general vectors.) Scheduling for Paperpath 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 lowend printers to highend multisteps 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., realtime control environment, this section pre
sents its use in paperpath 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 ink
puts u = v . The constraints c typically encode limi 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 faceing state x becomes the new “start” state for thek+1
up to facedown 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 constraintbased schedul
rors the architecture of the machine, with lowlevel
ing and modelpredictive 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