[gecode-users] Personnel scheduling problem

[Guido Tack]

Andreas Happe wrote:

> Hi,
> I'm trying to schedule personnel depending upon attributes.
>
> Per person I have multiple vectors:
>
> < id, attr_1, attr_2, attr_3, .., attr_n>
> where attr_n is an integer in [0,1]. There are various vectors to
> model the
> various combinations of attributes that the person might fulfill.
>
> e.g.:
> 1, 0, 0, 0, 1
> 1, 0, 0, 1, 1
>
> would describe a person with id 1 that can either supply attribute 4
> or attribute (3 and 4).
>
> a timeslot has a vector that describes the needed attribute, i.e.:
>
> <1, 1, 2, 1> : 1 * attr1, 1 * attr2, 2*attr3, 1*attr3
>
> I created a matrix with all people and their attributes:
>
> 1, 0, 0, 0, 1
> 1, 0, 0, 1, 1
> 2, 1, 1, 0, 0
>
> What I want now is to create subsets of the people-matrix with a
> distinct contraint
> for the first column (so that a person can only be assigned once) and
> another
> constraint that states that sum(column_(i+1)) >= timeslot_i.
>
> The constraints wouldn't be the problem but I'm out in the dark how to
> create the subset :(

I'd introduce one Boolean variable per attribute vector.  Then the  
subset constraint would be something like sum(b with the same id) ==  
1, stating that exactly one of the BoolVars that correspond to the  
same person must be true.

The supply constraint would be sum(b[j]*attr[i+1,j]) >= timeslot[i].   
I'm not sure this gives you enough propagation, but it's something you  
could experiment with.

Cheers,
	Guido