creating worker schedules

[ilikesas]

Hi,

here is a puzzle (although it could have a real application) I am working on and will be glad for assistance! Its about creating random working schdules for employees subject to constraints.

suppose that a company has a 3 day work week, and each day consists of 3 consecutive working hours - so there are 9 working hours in a work week. These 9 work hours have to be equally divided between 3 employees, so each employee works 3 hours in a work week.

It should be noted that any employee can't work more than 2 hours in a day, and if an employee works 2 hours in a given day these hours have to be consecutive. Also, the first hour of the first day belongs to employee # 1.

Thanks!

[ballardw]

Is the challenge creating any schedule or all schedules? Or did another constraint get lost?

1 hour per person per work day looks like a minimal solution

Day employee hour

1      1              1

2      1              1

3      1              1

1      2              2

2      2              2

3      2              2

1      3              3

2      3              3

3      3              3

[ilikesas]

that would be a trivial solution, the spirit of the question (and I guess that I should have mentioned it) is to create a random schedule, given the constraints. But now that you mentioned it, creating all possible schedules could also be very interesting!

[ballardw]

---

@ilikesas wrote:

that would be a trivial solution, the spirit of the question (and I guess that I should have mentioned it) is to create a random schedule, given the constraints. But now that you mentioned it, creating all possible schedules could also be very interesting!

---

I'm a mathematician by (some) training. Unless a non-trivial solution is specifically requested I'm going to generate the simplest and often trivial solution.

[ilikesas]

Trying to generate all the possible schedules, here I used a frequentist approach. This code is basically a collection of answers that I received from other community members (or a modification) so all credit goes to them:

data permutations (drop=i);
array time{9} $ ("a" "a" "a" "b" "b" "b" "c" "c" "c") ; /*initialize the first possible schedule,
which assumes that employee a fills all 3 time slots of day 1, employee b all time slots of 
day 2 and employee c all time slots of day 3*/

do i = 1 to fact(9);
   call allperm(i, of time[*]);
   output;
end;
run;

/*select unique schedules because all possible permutations resulted in many repetitive schedules */
proc sql;
create table schedule as
select distinct * from permutations;
quit;

/*apply the constraint that the first hour of day 1 belongs to employee a*/

data schedule;
set schedule;
if time1 = "a";
n = _n_;
run;

/*apply the constraint that in any given day no more than 2 time slots are allocated
to the same employee. First create data constraint2 because the sortc function will 
sort the time slots of each day, therefore diminishing the possibilities. */
data constraint2;
  set schedule;
  array v1(*) $ time1-time3;
  array v2(*) $ time4-time6;
  array v3(*) $ time7-time9;

  call sortc(of v1(*));
  do i=1 to dim(v1);
    if not missing(v1(i)) then do;
      if i lt dim(v1) then do;
        if v1(i)ne v1(i+1) then day1=sum(day1,1);
      end;
      else day1=sum(day1,1);
    end;
  end;

call sortc(of v2(*));
  do i=1 to dim(v2);
    if not missing(v2(i)) then do;
      if i lt dim(v2) then do;
        if v2(i)ne v2(i+1) then day2=sum(day2,1);
      end;
      else day2=sum(day2,1);
    end;
  end;

  call sortc(of v3(*));
  do i=1 to dim(v3);
    if not missing(v3(i)) then do;
      if i lt dim(v3) then do;
        if v3(i)ne v3(i+1) then day3=sum(day3,1);
      end;
      else day3=sum(day3,1);
    end;
  end;
run;

data constraint2 (drop=i);
set constraint2;
if day1 ne 1 and day2 ne 1 and day3 ne 1;
drop time1-time9;
run;

data schedule;
merge schedule constraint2;
by n;
if day1 ne '.';
run;



/*apply the constraint that when an employee works 2 hours in a day these 2 hours must be consecutive*/
 data schedule;
set schedule;
array day(*) day1-day3;
array time(*) time1-time9;
array flag(3);

do j = 1 to 3;
   if day{j} = 3 then flag{j} = 1;
   else  
     do i=1 to 2;
       if time{3*(j-1)+i}=time{3*(j-1)+i+1} then flag{j}=1;
     end;
end;

  do k = 1 to dim(flag);
    if flag{k}=1;
  end;
drop i j;
run;

In total I obtained 248 different schedules given the constraints. I will be very glad to have suggestions on how to make this code better!

[DanielSantos]

Hi.

Interesting puzzle, here a greedy approach (will try to allocate maximum hours first) to solve it:


%macro rand_schedule(TOTAL,SPLIT,FIRST,MAXUNIT);

%let EACH=%eval(&TOTAL/&SPLIT);

data _SCHEDULE;
     length HOUR 8;
     array _TOTAL[&SPLIT]; * totals;
     array SCHED[&SPLIT]; * schedule;
     drop _:;
     _I_=0;
     do HOUR=1 to &TOTAL; 
        do until (_TOTAL[_I] lt &EACH and _I ne _I_);
           if HOUR eq 1 then _I=&FIRST; * force first allocation;
           else _I=ceil(rand("Uniform")*&SPLIT);
        end; * randomly select;
        _I_=_I; * keep last allocated;
        if sum(_TOTAL[_I],&MAXUNIT) gt &EACH then _NEXT=sum(&EACH,-_TOTAL[_I]);
        else _NEXT=&MAXUNIT; * try max allocation;
        _TOTAL[_I]=sum(_TOTAL[_I],_NEXT);
        * schedule;
        do _J=1 to _NEXT;
           do _K=1 to &SPLIT; 
              SCHED[_K]=0;
           end; 
           SCHED[_I]=1;
           output;
           HOUR+1;
        end;
        HOUR+-1;
     end;
run;

%mend rand_schedule;

%rand_schedule(9,3,1,2); * total hours, num. of workers, first allocated, max consecutive hours;

Hope it helps.

Daniel Santos @ www.cgd.pt

[ilikesas]

Hi DanielSantos,

thanks for the code, it is pretty complex and I am trying to understand it. 

If HOUR = 1 , then _I = 1, but what is _TOTAL[1] if it was never allocated ?

[DanielSantos]

Hi.

I've commented the code a little more to help you understanding it.

So, as you can see the code works on 3 separate phases.

%let EACH=%eval(&TOTAL/&SPLIT); * calculate the amount of hours per worker;

data _SCHEDULE;
     length HOUR 8

     array _TOTAL[&SPLIT]; * this is used to track the current hours allocated to each worker;
     array SCHED[&SPLIT]; * this is the schedule for each worker, SCHED1 ... SCHEDn;

     drop _:; * auxiliary vars prefixed with _ so than can be easily dropped;

     _I_=0; 
     do HOUR=1 to &TOTAL; * cycle for each hour;

        * 1. find one worker with available time and that is not working in the previous hour;
        do until (_TOTAL[_I] lt &EACH and _I ne _I_); 
           if HOUR eq 1 then _I=&FIRST; * force first allocation to be worker 1;
           else _I=ceil(rand("Uniform")*&SPLIT); * pick one worker randomly;
        end;
        _I_=_I; * keep track of last allocated worker for next hour;

        * 2. greedly try to allocate maximum hours;
        if sum(_TOTAL[_I],&MAXUNIT) gt &EACH then _NEXT=sum(&EACH,-_TOTAL[_I]);
        else _NEXT=&MAXUNIT; * try max allocation;
        * _NEXT holds the allocated hours;
        _TOTAL[_I]=sum(_TOTAL[_I],_NEXT); * update total hours allocated for selected worker;

        * 3. update the schedule;
        do _J=1 to _NEXT; * cycle throught allocated hours;
           do _K=1 to &SPLIT; 
              SCHED[_K]=0; * set 0 for workers not selected;
           end; 
           SCHED[_I]=1; * set 1 for selected worker;
           output;
           HOUR+1; * adjust next;
        end;
        HOUR+-1; * adjust back;
     end;
run;

%mend rand_schedule;

%rand_schedule(9,3,1,2); * total hours, num. of workers, first allocated, max consecutive hours;

First it tries to find an available worker that has not reached the total amount of hours for each and that is not working in the previous hour.

Then it tries to allocate the maximum consecutive hours, if it is not possible, then it will allocate the difference (maximum - current total).

Finally it will build the schedule by cycling through the number of hours allocated and setting 0 and 1 to the corresponding workers.

Hope it helps.

Daniel Santos @ www.cgd.pt 

[ilikesas]

Thanks for the explanation, now I understand the code much better and learned a lot from it!

After running the code several times, I noticed that the schedules are not "truly random" in the sense that each employee necessarily has 2 consecutive hours and his single hour is always preceded by the 2 consecutive hours. Trying to make the schedules more "random" I added a code that if the hour is the last hour of the day, then the next hour can be either consecutive to it or not.

Here is the new code:

data _SCHEDULE;
     length HOUR 8;
     array _TOTAL[3]; * this is used to track the current hours allocated to each worker;
     array SCHED[3]; * this is the schedule for each worker, SCHED1 ... SCHEDn;
     drop _:; * auxiliary vars prefixed with _ so than can be easily dropped;
     _I_=0;

     do HOUR=1 to 9; 

	 * 1. find one worker with available time and that is not working in the previous hour;
        do until (_TOTAL[_I] lt 3 and _I ne _I_);
           if HOUR eq 1 then _I=1; * force first allocation to be worker 1;
           else _I=ceil(rand("Uniform")*3); * pick one worker randomly;
        end; ;
        _I_=_I; * keep track of last allocated worker for next hour;


if (hour/3) ne int(hour/3) then do; 
		* 2. greedly try to allocate maximum hours;
        if sum(_TOTAL[_I],2) gt 3 then _NEXT=sum(3,-_TOTAL[_I]);
        else _NEXT=2; * try max allocation;
        _TOTAL[_I]=sum(_TOTAL[_I],_NEXT); * update total hours allocated for selected worker;
      
		* 3. update the schedule;
        do _J=1 to _NEXT; * cycle throught allocated hours;
           do _K=1 to 3; 
              SCHED[_K]=0; * set 0 for workers not selected;
           end; 
           SCHED[_I]=1; * set 1 for selected worker;
           output;
           HOUR+1; * adjust next;
        end;
        HOUR+-1; * adjust back;
     end ;

else if (hour/3) = int(hour/3) then do;
_NEXT = 1 + rand("Bernoulli",0.5);
_TOTAL[_I]=sum(_TOTAL[_I],_NEXT);
do _J=1 to _NEXT; * cycle throught allocated hours;
           do _K=1 to 3; 
              SCHED[_K]=0; * set 0 for workers not selected;
           end; 
           SCHED[_I]=1; * set 1 for selected worker;
           output;
           HOUR+1; * adjust next;
        end;
        HOUR+-1; * adjust back;
    end;
end;
run;

That is, the Bernoulli random number generator decided whether the next hour will be consecutive or not. At first I ran the code several times and it seemd that the schedules appeared more random, but then saw weired things: sometimes an employee would get 4 hours whereas another enployee would get only 2, and sometimes an additional 10th hour was created to accomodate a consecutive hour to the 9th hour. Please help! 

[DanielSantos]

Hi.

Sorry for the late reply, I've been busy lately.

If you need total randomess it's much simpler than that, you just have to modify the following piece of my code:

...

* 2. randomly allocate hours <= MAXUNIT;
_NEXT=ceil(rand("Uniform")*&MAXUNIT); * choose randomly up to MAXUNIT;
if sum(_TOTAL[_I],_NEXT) gt &EACH then _NEXT=sum(&EACH,-_TOTAL[_I]); * adjust if above total;
* _NEXT holds the allocated hours;
_TOTAL[_I]=sum(_TOTAL[_I],_NEXT); * update total hours allocated for selected worker;

...

Hope it helps.

Daniel Santos @ www.cgd.pt