Information Technology Reference
In-Depth Information
For some applications, it is necessary to make the schedule as short as pos-
sible. To this aim, we can use the following program fragment.
COMMIT
SOME deadline := 1 TO max_deadline DO
JobShopScheduling(JobVector,deadline,jobs,Gantt)
END
END
It computes the shortest schedule by
guessing
, in ascending order, the rst
deadline that can be met by a feasible assignment. The use of the
COMMIT
state-
ment ensures that once a solution is found, the alternatives, with larger
deadline
values, are discarded.
4
Introducing Constraints
In what follows we discuss a proposal for adding constraints to
.
This Section is organized as follows. In Subsection 4.1 we discuss the addi-
tion of constrained types and unknowns to the language and in Subsections 4.2
and 4.3 we dene the constraint store and illustrate its interaction with the
program execution.
To illustrate how the proposed addition of constraints to
Alma-0
provides a
better support for declarative programming we illustrate in Subsection 4.4 their
use by means of three example programs.
To simplify our considerations we ignore in this section the presence of pro-
cedures. In particular, we assume for a while that all declarations are at one
level.
Alma-0
4.1
Adding Constrained Types, Unknowns and Constraints
We start by adding a new kind of variables of simple types, called unknowns.
This is done by using the qualier
CONSTRAINED
in declarations of
simple types
,
that is
INTEGER
,
BOOLEAN
,
REAL
, enumeration and subrange types.
Denition 1.
{
A type qualied with the keyword
CONSTRAINED
is called a
constrained type
.
{
A variable whose type is a constrained type is called an
unknown
.
We shall see in Section 5 that this way of dening unknowns simplies the
treatment of parameter passing in presence of unknowns. From now on we dis-
tinguish between variables and unknowns. In the discussion below we assume
the following declarations.
CONST N = 8;
TYPE Board = ARRAY [1..N] OF CONSTRAINED [1..N];
Colour = (blue, green, red, yellow);
Info = RECORD
Search WWH ::
Custom Search