- the density of the constraint
graph (the probability that a constraint exists between a pair of
variables). The set of parameters is expanded in order to get a constraint
network, that is typical for employee timetabling problems.
An ETP consists of assignments of employees to working shifts while satisfying all constraints. The shifts have start and end times and may overlap in time. They need to be assigned a set of employees. There are several positions in every shift. Each employee is of a certain qualification and may fulfill strictly appointed positions. The variables of the constraint network are positions. If a position needs more than one employee, it is represented by several variables. So, each variable requires a single employee to be assigned to it. It is clear now that employees are the values in the domains of variables.
The values in the domains are determined by two requirements. If a position forbids employees of certain qualifications to perform it, relevant values are ruled out from the domain of the variable, representing the position. Personal constraints of employees also determine the domains. If an employee cannot work at some shift the corresponding value is eliminated from the domains of all variables, related to this shift. These two facts create domains of variables in ETPs which are not uniform.
Employee timetabling networks have constraints of various arities. Unary constraints have already been mentioned above. They eliminate values from domains of variables. The unary constraints are checked before others are added to the network, because domains strongly influence the processing of binary and non-binary constraints.
There are several typical binary constraints in ETP CNs. The trivial one prevents an assignment of the same employee to more than one position of a single shift by connecting all variables, representing the shift. The constraint that forbids an assignment of the same employee to two overlapping shifts acts between all variables, which belong to overlapping shifts. Another binary constraint determines an interval between working shifts for employees. It connects all variables, relating to the shifts that lie within the given interval. The binary constraints of ETPs are of the non-equal or mutual exclusion type.
ETPs have also non-binary constraints. The most common non-binary constraints are of the finite capacity type. They are caused by limits on the working hours of employees. A typical restriction is on the number of shifts an employee can work during the period for which scheduling is done (a week, for example). For each employee, this non-binary constraint acts between all variables that have the corresponding value in their domains and belong to the given period (a week in the example above). To satisfy such a non-binary constraint one must control the number of working shifts assigned to employees. An efficient way to do this is to define a counter for a value. A counter is updated each time the relevant value is assigned to a variable. In other words, a counter keeps a number of shifts that have been already instantiated with the corresponding employee. The maximum of this number is the limit on the number of times that the employee can work during the period. An assignment is compatible with this non-binary constraint if the relevant counter is not ``full'', i.e. the value of the counter is less than the defined limit.
There is another non-binary constraint of the finite capacity type which controls the number of shifts of a certain kind that an employee can work during some period (for example, the limit of night shifts per week for each employee). The restriction is also implemented using a counter for each value. The difference from the previous non-binary constraint lies in the fact that a counter must not be updated every time a value is assigned to a variable. Such a counter is connected not to all variables that have some value in their domains, but to a subset of them, that contains only variables representing the shifts of the given kind (nights). The counter is updated only if the corresponding value is assigned to a variable in the subset.
Based on the above description we see that the constraint networks, representing employee timetabling problems, differ from uniform BCSPs in three major features:
The specific parameters of constraint networks of employee timetabling problems
are determined by the characteristic features of ETPs. We consider a CN with
three standard parameters of CSPs: n - the number of variables, k - the
total number of values in the problem and - the density of the constraint
graph (the probability that a constraint exists between a pair of
variables). The set of parameters is expanded in order to get a constraint
network, that is typical for employee timetabling problems.
One important characteristic of ETP constraint networks is the distribution of
values in domains of variables. We have chosen to generate the domains of
variables by assigning values (employees) randomly to variables (tasks), in
analogy to real life ETPs. This is equivalent to randomly selecting the subsets
of employees that can be assigned to every task. The resulting domains are
characterized by their sizes. To characterize the fact that different
variables have different domains we define a new parameter: the probability
that a value belongs to a domain of a variable. The intuitive meaning of the
parameter, which we denote 
, is the ``degree of filling'' of
domains of variables.
The typical binary constraints of employee timetabling problems are of mutual exclusion. Two variables can be connected by a non-equal binary constraint only if they have common values in their domains and these are the values the two variables conflict on. If one represents binary constraints by (0-1) matrices, which have 0's for illegal pairs of values, then in a graph coloring problem there are 0's on the diagonal (table 1(a)). In ETPs two constrained variables have 0's only on that part of the diagonal that belongs to the intersection of their domains (table 1(b)).
Table 1: The non-equal binary constraints in a GCP and an ETP with three
available colors 
; in the ETP the constraint is between two
variables 
and 
with the domains 
and 
correspondingly.
Binary constraints of the mutual exclusion type rule out a small fraction
of all possible pairs of values. For graph coloring problems with k values
the fraction, that is the tightness of the constraints 
, is equal to
. To calculate the tightness in an ETP we first express the
probability of a conflict across a constraint in it. Let, C be the number of
constraints. Let, 
be the number of zeroes (conflicts) in the
constraint i. Let the constraint i be between two variables x and y
and 
and 
be the sizes of the domains of these variables,
respectively. Then, the probability of a conflict in the constraint i is
defined as
and the formula for the evaluation of the value of for an
ETP:
From the above discussion, it is clear, that the tightness of constraints in ETP CNs, that have a large number of values (employees), is low.
Thus, random ETP networks are characterized by the tuple 
.
Since all constraints are of the mutual exclusion type, no probability
(tightness of constraints) is needed. The probability of a conflict is
determined by the non-equality constraints and can be calculated by equation
(2).
One of the characteristic features of ETPs is the existence of non-binary constraints. They can be easily incorporated in the generating mechanism for random CNs of ETPs of section 2. There are also necessary changes needed to CSP search algorithms in order to solve constraint networks with non-binary constraints of the finite capacity type. We will discuss one of the best search algorithms on constraint networks, forward-checking with conflict-directed backjumping (FC-CBJ).
As we noticed in section 1, a convenient way of representing non-binary constraints of finite capacity is by using counters, one for each constrained value. A counter connects all the constrained variables, that have the corresponding value in their domains. Suppose, for example, that variables in the constraint network represent shifts over one week. Consider two non-binary constraints:
Let us demonstrate the changes to the FC-CBJ search algorithm, to make it work with counters, on the example of the two non-binary constraints, described in the previous section. Denote the counters of a value j: c1[j] and c2[j], which correspond to the two non-binary constraints above. We will use also the following data structures:
holds a set of past variables of i that eliminate
some values from the domain of i (check against i)
holds a set of past variables of i that check
against those future variables of i which are incompatible with some values
in the domain of i.
The rest of the steps of the FC-CBJ algorithm remains the same as in FC-CBJ without counters. In particular, backjumping from a dead-end is performed
to the most recent conflicting variable in the set that includes both the
binary and the non-binary conflicts.
