Under construction...


Employee Timetabling Problems (ETPs)
Problem generator
Solvers

Contents

• General description of ETPs and their parameters
• Description of the generator
• Generate a problem
• Save the problem
• Solve the problem
• Save results

General description of ETPs and their parameters

Description of the generator

Representation of ETPs

• Variables represent working shifts. If a shift needs more than one employee, then it is represented by a number of variables equal to the number of required employees. So, each variable requires a single employee to be assigned to it.
• Values represent employees that have to be assigned to working shifts.

Parameters of binary ETPs

• n - the number of variables,
• k - the total number of values in the problem,
• p1 - the density of the constraint graph (the probability that a constraint exists between a pair of variables),
• avg_size - the probability that a value belongs to a domain of a variable.

Non-binary constraints

• Kinds of non-binary constraints of finite capacity:
  
  1. a limit of the total number of assignments per value (employee).
  2. a limit on the number of some specific assignments (night shifts, for example) per value (employee).
• Representation of non-binary constraints of finite capacity.
  1. a non-binary constraints of the first kind:
     • an array MaxCounter1 of size k, where MaxCounter1[i] holds a limit of the total number of assignments of a value i.
  2. a non-binary constraints of the second kind:
     • an array MaxCounter2 of size k, where MaxCounter2[i] holds a limit on the number of some specific assignments of a value i.
     • an array Group2 of size n, where Group2[i] = 1 if i is in the set of variables constrained by this non-binary constraints, otherwise Group2[i] = 0.

Standard format of a problem

• Concrete problem
  1. Definition of values of the parameters n, k in the format:
     VALUE_OF_N,VALUE_OF_K
  2. Definition of domains of variables in the format:
     VALUE(,VALUE)*EOLN n times
  3. Definition of binary constraints in the format:
     (VARIABLE:VARIABLE(,VARIABLE)*EOLN)*
  4. Definition of the non-binary constraint of the first kind, if it exists. For each value the limit of its counter should be defined. The format is:
     COUNTER1
     MAX1,MAX2,...,MAXk
  5. Definition of the non-binary constraint of the second kind, if it exists.
     • For each value the limit of its counter should be defined. The format is:
       COUNTER2
       MAX1,MAX2,...,MAXk
     • The list of variables constrained by the non-binary constraint should be defined in the format:
       VARIABLE(,VARIABLE)*
• Random problem
  1. The values of the parameters n, k, p1, avg_size should be defined.
  2. A non-binary constraint of the first kind, if it exists.
  3. A non-binary constraint of the second kind, if it exists.

Generate a problem

What problem would you like to generate:

concrete
definition file: 

random

Values of parameters:	Choice of counters:
n:  k:  p1:  avg_size:	First kind of non-binary constraint MAX1,MAX2,...,MAXk :  Second kind of non-binary constraint MAX1,MAX2,...,MAXk :  VARIABLE(,VARIABLE)* :

Save the problem

yes
no

Solve the problem

yes
Please, choose a kind of problem you would like to solve: with binary constraints only adding the first kind of non-binary constraints adding the second kind of non-binary constraints
no

Save results

yes
no