Assigning person to Roles

[PaalNavestad]

Hi, I'm struggling to formulate/program an assignment problem. In real life the problem is filling an Emergency preparedness crew. 

The problem can be described as follows:

Assume that yo have 5 workers P1..P5. These shall be assigned the roles A,B,C,D

P1  can fill A and B, P2 can fill B,C,D, P3 can fill C, P4 can fill A,B,D and P5 can fill A,B,C,D.

If you are assigned Role A you cannot be assigned any other role. If you are assigned role B You cannot fill role C. 

For Role A you need 1 person, For Roles B, C and D you need 2 persons. 

I'm struggling to get a decent formulation for the problem. I can express all assignements explicitly but struggle to find the right combinations. 

Can somebody please give me some ideas on how to get the problem formulated?

[RobPratt · Accepted solution]

Hi, Paal.  Here's one way:

data indata;
   input worker $ role $;
   datalines;
P1 A
P1 B
P2 B
P2 C
P2 D
P3 C
P4 A
P4 B
P4 D
P5 A
P5 B
P5 C
P5 D
;

proc optmodel;
   set <str,str> WORKERS_ROLES;
   read data indata into WORKERS_ROLES=[worker role];
   set WORKERS = setof {<w,r> in WORKERS_ROLES} w;
   set ROLES = setof {<w,r> in WORKERS_ROLES} r;
   
   /* Assign[w,r] = 1 if worker w is assigned to role r; 0 otherwise */
   var Assign {WORKERS_ROLES} binary;

   /* If you are assigned Role A you cannot be assigned any other role. */
   con Con1 {w in WORKERS: <w,'A'> in WORKERS_ROLES}:
      sum {<(w),r> in WORKERS_ROLES: r ne 'A'} Assign[w,r] <= card(ROLES) * (1 - Assign[w,'A']);

   /* If you are assigned role B You cannot fill role C. */
   con Con2 {w in WORKERS}:
      sum {<(w),r> in WORKERS_ROLES: r in /B C/} Assign[w,r] <= 1;

   /* For Role A you need 1 person. */
   con Con3:
      sum {<w,'A'> in WORKERS_ROLES} Assign[w,'A'] = 1;

   /* For Roles B, C and D you need 2 persons. */
   con Con4 {r in /B C D/}:
      sum {<w,(r)> in WORKERS_ROLES} Assign[w,r] = 2;

   solve;
   print Assign;
quit;

Alternatively, you can combine constraints 3 and 4:

   con Con34 {r in ROLES}:
      sum {<w,(r)> in WORKERS_ROLES} Assign[w,r] = (if r = 'A' then 1 else 2);

[PaalNavestad]

Thanks a million Rob. I was a bit further along than when I wrote the post, but far from a solution.

For Con1 and Con2 here you've coded the roles you can't have together. In real life there is approx. 20 roles to fill all with different roles you can't fullfill at the same time. on the top of your head is there a more dynamic way to write this constraint. If no it is not a large problem as the constraints can be created in a preceding macro.

Also in real life some persons have clear preferences for certain roles. This is for an offshore platform where the personnel change rapidly. Since there in most cases are several solutions to the problem you can be assigned role A day 1 and then role B day 2. My thoughts on how to avoid this is to give the role you have the day before the value 1 and your preferred role Value 2. From that i would just hav a Var multiplying value and assign and maximize on that. Do you see any problems with that approach?

Again thanks a lot.

[RobPratt]

Here's a more compact way to prohibit those conflicts, replacing Con1 and Con2:

data conflictdata;
   input role1 $ role2 $;
   datalines;
A B
A C
A D
B C
;

   set <str,str> CONFLICTS;
   read data conflictdata into CONFLICTS=[role1 role2];
   con ConflictCon {w in WORKERS, <r1,r2> in CONFLICTS}:
      sum {<(w),r> in WORKERS_ROLES: r in {r1,r2}} Assign[w,r] <= 1;

Regarding preferences, you can certainly include an objective to maximize the linear function that you proposed.

[PaalNavestad]

Thanks again. I owe you a large beer:-)