cbs-tutorial

Informations

• Publié par: Zaur
• Nombre de lectures: 19
• Langue: English

Extrait

-
-
*
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
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 co