Algorithm for Employee Cooperative Shift Choice

Abstract

This paper is about an algorithm that helps employees to choose which shifts they would prefer to work and also allows for variable pay scales. Shift choice differs from shift bidding in that the assigment to shifts is not based on the lowest bidder or on a first come, first served basis but in such a way as to maximize employee satisfaction. Ideally, all possible combinations of shift and pay possibilities would be considered and the one chosen would be the one that  maximizzed overall employee satisfaction while equalizing pay rates as much as possible and such that the overall budget constraint was achieved. Since this would require an inordinate amount of computer resources, algorithms which achieve substantially the same goals but shorten the computational process are desiraable. This paper presents some of those algorithms.

Introduction

Shift bidding is a process that has been around for some time. It has been used primarily by hospitals to assign nurses to shifts based on their stated preferences for working different shifts and their desired compensation. Obviously, some shifts are more desirable then others so it is expected that workers on the less desirable shifts will be compensated more. The nurses input their preferences over their home computer terminals, and the hospital fills the shifts by choosing nurses for each shift who are willing to work for the least amount of money. Thus the shifts are filled by assigning nurses to shifts based on their preferences and the pay they are willing to work for. This gives the nurses choice over their schedules and pay preferences and tends to reduce costs for the horpital since, if no nurse is willing to work a particular shift, they have to hire someone from a temp agency and this turns out to be more expensive and less desirable in terms of performance.

Employee cooperative shift choice is a concept that I’m proposing which goes a step further than shift bidding. It assumes that a total budget for a set of shifts is arrived at by negotiation or some other means. Then employees state their preferences for different shifts/pay preferences. The goal is to assign employees to shifts/wages in such a way as to maximize overall employee satisfaction while staying within the total budget. For instance, let’s assume the budget for the day is X dollars and there are 3 shifts. Let’s assume that 4 nurses are required per shift. Let’s assume that the employees can list a total of 10 possible work/pay schedules. Each possible schedule is ranked from 1 to 10. A first choice might be shift 1 at $40./hour, second choice - shift 1 at $30./hour, third choice – shift 1 at $20./hour, fourth choice - shift 2 at $50./hour, fifth choice – shift 2 at $40./hour, sixth choice – shift 2 at $30./hour, seventh choice – shift 3 at $60./hour, eighth choice – shift 3 at $50./hour, ninth choice – shift 3 at $40./hour, tenth choice – shift 1 at $10./hour. What the algorithm attempts to do is to give as many employees as possible their most preferred choices while fillling all the shifts and staying within the overall budget. An additional goal is to spread the loss in satisfaction in terms of the reduction in pay levels necessary to achieve the overall budget as evenly as possible.

A Simplified Algorithm

First we consider an algorithm just based on shift preference without any pay considerations. Let us assume the following:

n = number of employees
s = number of shifts
r = number of choices
t = number of employees needed per shift

Each employee lists their shift preferences from 1 to r. For example, if there are 15 shifts and 10 choices, a typical set of preferences might be (4, 2, 14, 12, 3, 9, 15 ,6, 11, 5).  So the employee’s first choice is shift 4, second choice is shift 2 etc. 

The algorithm proceeds as follows. First give all employees their first choice. In order take the shifts that are overfilled and randomly select an employee. Place that employee in the shift pool corresponding to his/her second choice. Continue this procedure until the shift pool contains the exact number of employees required to fill that shift. Then this shift pool is completed. Take the next overfilled shift in order. Repeat the procedure of randomly selecting employees from that shift pool and placing them in their second choice shift pool without placing anyone in a shift pool that has already been completed. If a randomly selected employee’s next highest preference is for an already completed pool, randomly select another employee. If all remaining employees in the pool have second choices that are already in completed shift pools, randomly select an employee and place him/her in his/her third choice shift pool or lower choice shift pools if all second choice shift pools are completed for all employees. Proceed in order with all uncompleted shift pools and all employees until the process is finished. At that point every employee will have been assigned to a shift. 

As an example, let us consider n = 10 employees, s = 5 shifts and r = 5 choices. Each shift requires t = 2 employees. Here are the employees’ preference lists:

Employee 1: (4,3,5,2,1)
Employee 2: (3,5,4,1,2)
Employee 3: (2,4,1,5,3)
Employee 4: (3,4,2,5,1)
Employee 5: (3,2,1,5,4)
Employee 6: (1,2,5,4,3)
Employee 7: (2,1,5,4,3)
Employee 8: (4,2,1,3,5)
Employee 9: (5,1,2,3,4)
Employee 10: (1,5,3,4,2)

Proceed with Shift 1: Filled with Employee 6 and Employee10.

Shift 2: Employees 3 and 7.
Shift 3: Employees 2, 4 and 5. Randomly select Employee 4. Place in his/her second choice pool – Shift 4.

At this point shifts 1, 2 and 3 have been completed.

Shift 4: Employees 1, 4, and 8. Randomly select employee 8. Can’t place in second choce shift pool (shift 2) since it’s already been completed. Randomly select employee 1. Can’t place in second choice shift pool (shift 3) since it’s already been completed. Randomly select employee 4. Employee 4 is already in second choice shift pool. So no employees in shift pool 4 can be given their second choice in order to complete the shift. Therefore, we must randomly select again and place an employee in his or her third choice shift pool. Let’s say we randomly select employee 1. His/her third choice is shift 5. Place employee 1 in shift 5 pool and shift 4 is completed.

Shift 5: Employees 1 and 9. Shift completed.

Therefore, we have the following shift assignments followed by the employee’s ramking of that shift in parenthesis.

Shift 1: Employees 6  (1) and 10 (1).
Shift 2: Employees 3 (1) and 7 (1).
Shift 3: Employees 2 (1) and 5 (1).
Shift 4: Employees 4 (2) and 8 (1).
Shift 5: Employees 1 (3) and 9 (1).

Therefore, in this example, we have 8 employees out of 10 with their first choice shift assignment, 1 employee with his/her second choice and 1 employee with his/her third choice resulting in a very high level of social and individual satisfaction or happiness or utility. Our goal is to maximize social utility or satisfaction.

A More Complex Algorithm

Now let us consider an algorithm which takes into account not only shift preference but pay preference as well. Let us assume that each employee’s choice contains a shift preference and also a pay preference. We assume the pay preference is an hourly rate e.g. $40. an hour. Let’s further assume that the pay preferences can range from $10. to $100. in $10. increments. So an employee choice could be shift 2 at $40. an hour which we represent as (2,40). A typical employee preference schedule could be the following:

[(2,100),(2,60),(2,50),(1,50),(1,40),(1,30),(2,50),(2,40),(2,30),(2,20)]

This assumes that 10 choices are allowed. Now let us assume that there is an overall budget constraint. Let this be symbolized by b.

The algorithm proceeds as follows. Place everyone in their first choice shift/pay pool. Now consider the overfilled pools in order. Ramdomly take employees out of the first overfilled pool who have the highest pay preferences and put them in their second choice pool. This then completes the first pool. Continue on with the other overfilled pools in order. Now compute the total pay of the employees and compare with the budget constraint. If it is less than overall budget, some shifting can take place to elevate employee choices. For instance, if an employee has been given his/her third place choice at $30 an hour and his second choice is the  same shift pool at $40. an hour, his final choice level could be elevated while staying in the same shift pool.

The algorithm for elevating choices to increase the total pay up to the budget constraint is as follows. Consider employees who have been given their lowest choices in the original assignment. Randomly selecting them one at a time, see if their choice level can be elevated while keeping them in the same shift pool. Proceed with employees who have been given their next lowest choice etc. When the total pay reaches the budget constraint discontinue this process. If the process completes itself without reaching the budget constraint, elevate everyone’s  pay by an equal amount to reach the budget constraint.

But usually the opposite situation will occur wherein the employees will have to have a reduction in satisfaction and pay levels in order to meet the budgetary constraint.  Now let’s assume that the original assignment results in the situation where the total employee pay exceeds the budget constraint. The algorithm for reducing total employee pay until it reaches the budget constraint is as follows. Consider all the employees who have been given their first choices. Randomly select these employees one at a time and check to see if a lower choice corresponds to the same shift pool but at a lower pay level. If so reduce that employee’s pay and choice levels accordingly. Continue in this way with employees that have originally been given their second choices, third choices etc. Please note that we are not transferring any employees from the shift pools to which they were originally assigned. At every step compute employee total pay and, if it equals or is slightly below the budget constraint, discontinue the process. If the process completes itself and the total employee pay is still above the budget constraint, reduce everyone’s pay equally until the budget constraint is met.

As an example, let us assume the following:

n = 9 employees
s = 3 shifts
r = 10 choices
t = 3 employees/shift
b = $400.
Pay preferences in increments of $10. starting at $10. per hour

Here are the employees’ preference lists:

Employee 1: [(2,100),(2,60),(2,50),(1,50),(1,40),(1,30),(2,40),(2,30),(2,20),(2,10)]
Employee 2: [(3,100),(3,90),(2,80),(2,70),(1,50),(1,40),(1,30),(2,60),(2,50),(2,40)]
Employee 3: [(1,70),(1,60),(1,50),(1,40),(1,30),(1,20),(2,70),(2,60),(2,50),(2,40)]
Employee 4: [(1,90),(1,80),(1,70),(2,90),(2,80),(2,70),(3,100),(3,90),(3,80),(3,70)]
Employee 5: [(2,70),(2,60),(2,50),(2,40),(2,30),(2,20),(3,90),(3,80),(3,70),(3,60)]
Employee 6: [(1,100),(1,90),(1,80),(1,70),(1,60),(1,50),(1,40),(1,30),(1,20),(1,10)]
Employee 7: [(2,60),(2,50),(2,30),(3,80),(3,60),(3,40),(2,100),(2,90),(2,80),(2,70)]
Employee 8: [(3,100),(3,90),(3,80),(3,70),(2,100),(2,90),(2,80),(2,70),(1,100),(1,90)]
Employee 9: [(1,100),(2,100),(3,100),(1,90),(2,90),(3,90),(1,80),(2,80),(3,80),(1,70)]

One might infer from the above employee choice profiles that different needs and strategies are at work. We might also assume that shift 1 is the most desirable shift, pehaps the day time shift. Then we could assume that shift 2 is the twilight shift and shift 3 the night time or grave yard shift. So let’s look at Employee 1, and see if we can discern his/her strategy. Employee 1’s first choice is shift 2, a less desirable shift, which he/she is willing to work so long as he/she gets top dollar. If that doesn’t work, he/she would like to lock in shift 1 which he/she tries to do by choosing more modest pay points. After that he/she switches back to shift 2 with the remaining lower choice levels. The fact that his/her lowest choice is shift 2 at a very low pay point indicates that Employee 1 desperately does not want to work shift 3.

Now let’s consider Employee 8. Employee 8 is willing to work shift 3, the least desirable shift so long as he/she gets top dollar but going down in choice levels to a pay point somewhat above average pay which is $40 per hour (total budget divided by number of employees). Then Employee 8 switches to shift 2 also starting off high and descending in choice level down to a more reasonable pay point. Finally, he/she switches to shift 1 at unreasonable high pay points. The fact that employees know that the average pay point is $40. an hour tells them that they are more likely to get the shift they want if they choose high choice levels around $40, adjusting slightly higher or lower considering the desirability of the shift.

Now let’s work the algorithm to figure out the work/pay assignments.

Proceed with Shift 1: Filled with Employees 3, 4, 6, 9.

Shift 2: Employees 1, 5, 7.

Shift 3: Employees 2 and 8.

Shift 1 is overfilled by 1 and shift 3 is underfilled by 1. Randomly select (for example) Employee 4 from shift 1 and assign him/her to shift 3.

Then we have the following assignments:

Shift 1: Employees 3, 6, 9.

Shift 2: Employees 1, 5, 7.

Shift 3: Employees 2, 4, 8.

Now let’s compute the total pay that this assignment would require:

Shift 1: $70. + $100. + $100. =  $270.

Shift 2: $100. + $70. + $60. = $230.

Shift 3: $100. + $100. + $100. = $300.

Total projected pay = $800. - way over budget

Therefore, we proceed to consider all those employees who have been given their first choice at the highest pay level and see if they could be given a lower choice in the same pool. All employees except Employee 4 were given their first choice. Of these Employees 1, 2, 6, 8 and 9 were all assigned the highest pay points - $100. So we consider these particular employees to see if their next highest choices will lower the overall budget. In practice we randomly select from these, but for purposes of this example, we will just go in order. 

Employee 1’s next highest (second) choice for shift 2 is $60. Employee 2’s next highest (second) choice is shift 3 is $90. Employee 6’s next highest (second) choice for shift 1 is $90. Employee 8’s next highest (second) choice for shift 3 is $90. Employee 9’s next highest (fourth) choice for shift 1 is $90.

Therefore, we compute the total proposed budget to be $710. – still way over the budget constraint. 

Next we consider Employees 2, 6, and 8. They are at the highest choice/pay point level. of  $90. Employee 9 is at 4th choice and $90.  Employee 2 doesn’t have any other choice in Shift 3. Consider Employees 6 and 8.  Employee 6’s next highest (third) choice is $80. Employee 8’s next highest (third) choice is $80. Similarly, Employees 6 and 8’s next highest choices are both $70. Employee 6’s next highest choice is $60. Employee 8 doesn’t have any other choices in the same shift pool so let’s calculate the total projected budget to see where we stand now.

Here are the current pay points followed by the choice level in parentheses:

Employee 1: $60.  (2)
Employee 2: $90.  (2)
Employee 3: $70.  (1)
Employee 4: $100.(7)
Employee 5: $70.  (1)
Employee 6: $60.  (5)
Employee 7: $60.  (1)
Employee 8: $70.  (4)
Employee 9: $90.  (4)
      Total       $670.

At this point if we reduce everyone’s hourly pay by $30. we will come in under the budget constraint.

Final pay assignments:

Employee 1: $30. (2)
Employee 2: $60. (2)
Employee 3: $40. (1)
Employee 4: $70. (7)
Employee 5: $40. (1)
Employee 6: $30. (5)
Employee 7: $30. (1)
Employee 8: $40. (4)
Employee 9: $60. (4)
      Total     $400.

As a final step we can do a head to head comparison and see if the overall employee satisfaction can  be improved by swapping two employees’shifts.

Employee 1 and Employee 2:  Impossible
Employee 1 and Employee 3: -8 
Employee 1 and Employee 4: Impossible
Employee 1 and Employee 5: Already in  same pool
Employee 1 and Employee 6: Impossible
Employee 1 and Employee 7: Same pool
Employee 1 and Employee 8: Impossible
Employee 1 and Employee 9: 0 
Employee 2 and Employer 3: Impossible
Employee 2 and Employee 4: Same Pool
Employee 2 and Employee 5: -7
Employee 2 and Employee 6: Impossible
Employee 2 and Employee 7: -5
Employee 2 and Employee 8: Same Pool
Employee 2 and Employee 9: -2
Employee 3 and Employee 4: Impossible
Employee 3 and Employee 5: Impossible
Employee 3 and Employee 6: Same Pool
Employee 3 and Employee 7: Impossible
Employee 3 and Employee 8: Impossible
Employee 3 and Employee 9: Same Pool
Employee 4 and Employee 5: -8
Employee 4 and Employee 6: Impossible
Employee 4 and Employee 7: 0
Employee 4 and Employee 8: Same Pool
Employee 4 and Employee 9: +7 
Employee 5 and Employee 6: Impossible
Employee 5 and Employee 7: Same Pool
Employee 5 and Employee 8: -7
Employee 5 and Employee 9: Impossible
Employee 6 and Employee 7: Impossible
Employee 6 and Employee 8: Inpossible
Employee 6 and Employee 9: Same Pool
Employee 7 and Employee 8: -4
Employee 7 and Employee 9: Impossible
Employee 8 and Employee 9: -4

	We could exchange employees 4 and 9. That would increase employee satisfaction levels, but it would also increase employee payouts with the result that the budget would exceed the budgetary constraint.

We can see that perhaps the highest possible pay point should have possibly been set at $80. instead of $100. Using the same example with r = 8 and a top pay point of $80. we work out the following:

Here are the employees’ (modified) preference lists:

Employee 1: [(2,80),(2,50),(2,40),(1,50),(1,40),(1,30),(2,30),(2,20),(2,10),(1,20)]
Employee 2: [(3,80),(3,70),(2,60),(2,50),(1,50),(1,40),(1,30),(2,60),(2,50),(2,40)]
Employee 3: [(1,70),(1,60),(1,50),(1,40),(1,30),(1,20),(2,70),(2,60),(2,50),(2,40)]
Employee 4: [(1,80),(1,70),(1,60),(2,80),(2,70),(2,60),(3,80),(3,70),(3,60),(3,50)]
Employee 5: [(2,70),(2,60),(2,50),(2,40),(2,30),(2,20),(3,80),(3,70),(3,60),(3,50)]
Employee 6: [(1,80),(1,70),(1,60),(1,50),(1,40),(1,30),(1,20),(1,10),(2,80),(2,70)]
Employee 7: [(2,60),(2,50),(2,30),(3,80),(3,60),(3,40),(1,80),(1,70),(1,60),(1,50)]
Employee 8: [(3,80),(3,70),(3,60),(3,50),(2,80),(2,70),(2,60),(2,50),(1,80),(1,70)]
Employee 9: [(1,80),(2,80),(3,80),(1,70),(2,70),(3,70),(1,60),(2,60),(3,60),(1,50)]

Proceed with Shift 1: Filled with Employees 3, 4, 6, 9.

Shift 2: Employees 1, 5, 7.

Shift 3: Employees 2 and 8.

Now transfer Employee 4 from  shift 1 to shift 3 and compute the budget.

Then let’s compute the total pay that this assignment would require:

Shift 1: $70. + $80. + $80. =   $230.

Shift 2: $80. + $70. + $60. =   $210.

Shift 3: $80. + $80. + $80. =   $240.
Total    $680.

We are still over our budget of $400. so we proceed with the algorithm. 

Therefore, we consider all those employees who have been given their first choice at the highest pay level and see if they could be given a lower choice in the same pool. All employees except Employee 4 were given their first choice. Of these Employees 1, 2, 6, 8 and 9 were all assigned the highest pay point - $80. So we consider these particular employees to see if their next highest choices will lower the overall budget. In practice we randomly select from these, but for purposes of this example, we will just go in order. 

Employee 1’s next highest (second) choice for shift 2 is $50. Employee 2’s next highest (second) choice is shift 3 is $70. Employee 6’s next highest (second) choice for shift 1 is $70. Employee 8’s next highest (second) choice for shift 3 is $70. Employee 9’s next highest (fourth) choice for shift 1 is $70.

Shift 1: Employees 3,6,9

Shift 2: Employees 1,5,7

Shift 3: Employees 2,4,8

Shift 1: $70. + $70. + $70. = $210.

Shift 2: $50. + $70. + $60. = $180.

Shift 3: $70. + $80. + $70. = $220.
          Total = $610. - Still over budget.

Next we consider Employees 2, 6, and 8. They are at the current highest choice/pay point level. of  $70. There are no other employees whose second choice is at a $70. pay level.  Employee 9 is at 4th choice and $70.  Employee 2 doesn’t have any other choice in Shift 3. Consider Employees 6 and 8. Employee 6 can be moved to his/her third choice at $60., and Employee 8 can be moved to his/her third choice of $60. This brings the budget down to  $590. Moving employees 6 and 8 to their fourth highest choice of $50.  brings the budget down to $570. Employee 8 doesn’t have any other choices in the same shift pool. Employee 6 can be moved to his/her eighth highest choice of $10. bringing the budget down to $530. Then Employee 1 can be moved to his ninth choice at $10. bringing the budget down to $490. Here the process terminates.

Here are the current pay points followed by the choice level in parentheses:

Employee 1: $10. (9)
Employee 2: $70. (2)
Employee 3: $70. (1)
Employee 4: $80. (7)
Employee 5: $70. (1)
Employee 6: $10. (8)
Employee 7: $60. (1)
Employee 8: $50. (4)
Employee 9: $70. (4)
      Total     $490.

Now we’re $80. over budget so if we take $11.43 off the hourly pay of everyone except employees 1 and 6 who are already at a $10. pay point the budget constraint will be met.

Now let’s consider a different algorithm to see if we can improve on the pay/satisfaction levels of the above in which Employee 1 is at a $10./9 satisfaction level and Employee 6 is at a $10./8 satisfaction level. We do this by relaxing the constraint that every employee has to remain in the same shift pool that he/she was originally assigned to. Maybe there is a better way to reassign employees to shift pools. Consider the following. Move the employee from an overfilled to an underfilled pool who will have the highest resulting satisfaction level. In the above example if we moved Employee 9 instead of Employee 4 from shift pool 1 to shift pool 3, the resulting satisfaction levels would be

Employee 4 (1), Employee 9 (3). This would be a higher average satisfaction level than when the shift assignment was for Employee 4 to be shifted to shift pool 3.

Consider the following algorithm. Consider moving an employee from an overfilled pool to an exactly filled pool or another overfilled pool and then another employee from this pool to the underfilled pool. This would be a two or more step reassignment instead of a one step. Choose the reassignment that results in the least reduction of satisfaction  levels and, secondly, total pay. For example, if we reassign Employee 9 from pool 1 to pool 2 and Employee 7 from pool 2 to pool 3, there is 1 satisfaction level reduction for Employee 9 and a 3 satisfaction level reduction for Employee 7 for a total of a 4 satisfaction levels reduction. Our original 1 step reassignment of employee 4 to shift pool 3 resulted in a 6 satisfaction level reduction. Then at each stage of pay level reductions to meet the budget constraint, consider moving employees among shift pools in such a way as to minimize reductions in satisfaction levels and pay reductions.

Let’s do another example with this new algorithm.

Here are the assumptions:

n = 9 employees
s = 3 shifts
r = 6 choices
t = 3 employees/shift
b = $400.
Pay preferences in increments of $10. starting at $10. per hour with $60. maximum

Employee 1: [(2,60),(2,50),(2,40),(1,50),(1,40),(1,30),(2,30),(2,20),(2,10),(1,20)]
Employee 2: [(3,60),(3,50),(2,60),(2,50),(1,50),(1,40),(1,30),(1,20),(2,40),(2,30)]
Employee 3: [(1,60),(1,50),(1,40),(1,30),(1,20),(1,10),(2,60),(2,50),(2,40),(2,30)]
Employee 4: [(1,60),(1,50),(1,40),(2,60),(2,50),(2,40),(3,60),(3,50),(3,40),(3,30)]
Employee 5: [(2,60),(2,50),(2,40),(2,30),(2,20),(2,10),(3,60),(3,50),(3,40),(3,30)]
Employee 6: [(1,60),(1,50),(1,40),(1,30),(1,20),(1,10),(2,60),(2,50),(2,40),(2,30)]
Employee 7: [(2,60),(2,50),(2,40),(3,60),(3,50),(3,40),(1,60),(1,50),(1,40),(1,30)]
Employee 8: [(3,60),(3,50),(3,40),(3,30),(2,60),(2,50),(2,40),(2,30),(1,60),(1,50)]
Employee 9: [(1,60),(2,60),(3,60),(1,50),(2,50),(3,50),(1,40),(2,40),(3,40),(1,30)]

The algorithm proceeds as follows:

Initial assignments: 

		Shift 1: 3,4,6,9
		Shift 2: 1,5,7
		Shift 3: 2,8

Consider the following reassignment options:

1)	Employee 4 to shift 3 – Satisfaction reduction levels: 6, Total pay reduction: 0
2)	Employee 9 to shift 3 – Satisfaction reduction levels: 1, Total pay reduction: 0
3)   Employee 4 to shift 2,  employee 5 to shift 3 – Satisfaction reduction levels: 9, 
Total pay reduction: 0
4)	 Employee 4 to shift 2, employee 7 to shift 3 – Satisfaction reduction levels:6, Total pay reduction: 0
5)	Employee 9 to shift 2, employee 5 to shift 3 – Satisfaction reduction levels: 7, Total pay reduction:  0
6)	Employee 9 to shift 2, employee 7 to shift 3 – Satisfaction reduction levels: 4, Total pay reduction: 0

We should choose option 2 because it minimizes the reduction in satisfaction levels.

Therefore, we have 

			Shift 1: Employees 3,4,6

Shift 2: Employees 1,5,7

Shift 3: Employees 2,8,9

Shift 1: $60. + $60. + $60. = $180.

Shift 2: $60. + $60. + $60. = $180.

Shift 3: $60. + $60. + $60. = $180.
          			          Total = $540.

Now we proceed to cut satisfaction and pay levels. Employees 1,2,3,4,5,6,7,8 have the highest satisfaction levels. They can all be cut by $10., stay in the same pools and be reduced to second satisfaction levels. This brings the total budget down to $460. Since employee 2 cannot have his/her saatisfaction level reduced once more and stay in the  same pool, we reduce the satisfaction levels of Employees 1 and 3-8 one more level reducing the total budget by $70. to $390.

Here are the final pay points followed by the choice levels in parentheses:

Employee 1: $40. (3)
Employee 2: $50. (2)
Employee 3: $40. (3)
Employee 4: $40. (3)
Employee 5: $40. (3)
Employee 6: $40. (3)
Employee 7: $40. (3)
Employee 8: $40. (3)
Employee 9: $60. (3)
        Total     $390.

The question may be asked if it’s fair for employee 8 to be in pool 3 at the same satisfaction level as employees 2 and 9 but at less pay. Arguably, the answer is yes because if we reduced amployee 9’s pay to $50. and increased employee 8’s pay to $50., we will have increased employee 8’s satisfaction level by 1 while reducing employee 9’s satisfaction level by 3 for a net total reduction in satisfaction of 2. It is best to leave the assignment as is. Each employee can be given a slight increase of $1.11 to bring the total budget to $400. which meets the budget constraint exactly.

So the final algorithm is as follows. Assign all employees to their first choice shift pool/pay point. Consider all one and two step transfers of employees from overfilled to underfilled pools. Choose the one(s) that minimize total reductions in satisfaction levels. Then consider reductions in satisfaction levels within pools to bring down total budget within the budget constraint. Do this in such a way as to minimize total reduction in satisfaction levels.

As  a next example, consider this.

n = 9 employees
s = 3 shifts
r = 8 choices
t = 3 employees/shift
b = $400.
Pay preferences in increments of $10. starting at $10. per hour with $80. maximum

In this modified algorithm we consider shifting employees between shift pools at each stage of the process in addition to shifting them downward in satisfaction levels. At each stage consider a switch in shift assignments for an employee if that swap can increase overall satisfaction without increasing the total budget. 

Here are the employees’ (modified) preference lists:

Employee 1: [(2,80),(2,50),(2,40),(1,50),(1,40),(1,30),(2,30),(2,20),(2,10),(1,20)]
Employee 2: [(3,80),(3,70),(2,60),(2,50),(1,50),(1,40),(1,30),(2,60),(2,50),(2,40)]
Employee 3: [(1,70),(1,60),(1,50),(1,40),(1,30),(1,20),(2,70),(2,60),(2,50),(2,40)]
Employee 4: [(1,80),(1,70),(1,60),(2,80),(2,70),(2,60),(3,80),(3,70),(3,60),(3,50)]
Employee 5: [(2,80),(2,70),(2,60),(2,50),(2,40),(2,30),(3,80),(3,70),(3,60),(3,50)]
Employee 6: [(1,80),(1,70),(1,60),(1,50),(1,40),(1,30),(1,20),(1,10),(2,80),(2,70)]
Employee 7: [(2,60),(2,50),(2,30),(3,80),(3,60),(3,40),(1,80),(1,70),(1,60),(1,50)]
Employee 8: [(3,80),(3,70),(3,60),(3,50),(2,80),(2,70),(2,60),(2,50),(1,80),(1,70)]
Employee 9: [(1,80),(2,80),(3,80),(1,70),(2,70),(3,70),(1,60),(2,60),(3,60),(1,50)]

Shift 1: Employees 3,4,6,9
Shift 2: Employees 1,5,7
Shift 3: Employees 2,8

Consider the following reassignment options:

1) Employee 4 to shift 3 – Satisfaction reduction levels: 6, Total pay reduction: 0
2) Employee 9 to shift 3 – Satisfaction reduction levels: 2, Total pay reduction: 0
3) Employee 4 to shift 2,  employee 5 to shift 3 – Satisfaction reduction levels: 9, 
Total pay reduction: 0
      4) Employee 4 to shift 2, employee 7 to shift 3 – Satisfaction reduction levels: 6, 
Total pay reduction: -$20.
      5) Employee 9 to shift 2, employee 5 to shift 3 – Satisfaction reduction levels: 7, 
Total pay reduction:  0
6) Employee 9 to shift 2, employee 7 to shift 3 – Satisfaction reduction levels: 4, 
				Total pay reduction: -$20.

We choose option 2 because it minimizes reduction in total satisfaction levels. Then we have the following assignments:

				Shift 1: Employees 3,4,6
Shift 2: Employees 1,5,7
Shift 3: Employees 2,8,9
The payouts are  as follows:

Shift 1: $70. + $80. + $80. = $230.
Shift 2: $80. + $80. + $60. = $220.
Shift 3: $80. + $80. + $80. = $240.

Total Budget = $690.

Now we proceed to cut satisfaction and pay levels. Employees 1,2 4,5,6,8 all have the highest satisfaction and pay levels. We downgrade each of these one satisfaction level to  come up with the following reassignments. Changes are underlined:

			Employee 1: Shift 2, Satisfaction Level 2, Pay $50
Employee 2: Shift 3, Satisfaction Level 2, Pay $70.
Employee 3: Shift 1, Satisfaction Level 1, Pay $70.
Employee 4: Shift 1, Satisfaction Level 2, Pay $70.
Employee 5: Shift 2, Satisfaction Level 2, Pay $70.
Employee 6: Shift 1, Satisfaction Level 2, Pay $70.
Employee 7: Shift 2, Satisfaction Level 1, Pay $60.
Employee 8: Shift 3, Satisfaction Level 2, Pay $70.
Employee 9: Shift 3, Satisfaction Level 3. Pay $80.

The payouts are  as follows:

Shift 1: $70. + $70. + $70. = $210.
Shift 2: $50. + $70. + $60. = $180.
Shift 3: $70. + $70. + $80. = $220.

Total Budget = $610.

Proceed to reduce 2nd or above Satisfaction Levels @ Pay $70 or above. That would be Employees 2,3,4,5,6,8.
			
			Employee 1: Shift 2, Satisfaction Level 2, Pay $50.
Employee 2: Shift 3, Satisfaction Level 2, Pay $70.
Employee 3: Shift 1, Satisfaction Level 2, Pay $60.
Employee 4: Shift 1, Satisfaction Level 3, Pay $60.
Employee 5: Shift 2, Satisfaction Level 3, Pay $60.
Employee 6: Shift 1, Satisfaction Level 3, Pay $60.
Employee 7: Shift 2, Satisfaction Level 1, Pay $60.
Employee 8: Shift 3, Satisfaction Level 3, Pay $60.
Employee 9: Shift 3, Satisfaction Level 3. Pay $80.

Total Budget = $560.

Employee 2 is at a satisfaction level 2 with a pay rate of $70. but there are no lower pay rates for him in shift 3. So we consider swapping shifts with another employee such that the overall satisfaction levels increase. 

Swap Employee 2 and Employee 3	Result: Impossible
Swap Employee 2 and Employee 4	Result: Lower Overall Satisfaction
Swap Employee 2 and Employee 6	Result: Impossible
Swap Employee 2 and Employee 1 	Result: Impossible
Swap Employee 2 and Employee 5	Result: Lower Overall satisfaction
Swap Employee 2 and Employee 7	Result: Lower Overall Satisfaction

So we leave shift assignments alone.

Proceed to reduce 3rd or above Satisfaction Levels @ Pay $60 or above. That would be Employees 2,3,4,5,6,7,8,9.

Consider swapping Employee 9 since he/she has the largest pay.

Swap Employee 9 and Employee 3	Result: Impossible
Swap Employee 9 and Employee 4	Result: -5
Swap Employee 9 and Employee 6	Result: Impossible
Swap Employee 9 and Employee 1	Result: Impossible
Swap Employee 9 and Employee 5	Result: -6
Swap Employee 9 and Employee 7	Result: -5

So we leave shift assigments alone.

Employee 1: Shift 2, Satisfaction Level 2, Pay $50.
Employee 2: Shift 3, Satisfaction Level 2, Pay $70.
Employee 3: Shift 1, Satisfaction Level 3, Pay $50.
Employee 4: Shift 1, Satisfaction Level 3, Pay $60.
Employee 5: Shift 2, Satisfaction Level 4, Pay $50.
Employee 6: Shift 1, Satisfaction Level 4, Pay $50.
Employee 7: Shift 2, Satisfaction Level 2, Pay $50.
Employee 8: Shift 3, Satisfaction Level 4, Pay $50.
Employee 9: Shift 3, Satisfaction Level 3. Pay $80.

Total Budget = $510.

Consider swapping Employee 9:

Swap Employee 9 with Employee 3: Result: - Impossible
Swap Employee 9 with Employee 4: Result: -2 Satisfaction; Pay Reduction -$20
Swap Employee 9 with Employee 6: Result: Impossible
Swap Employee 9 with Employee 1: Result: Impossible
Swap Employee 9 with Employee 5: Result: -2 Satisfaction; Pay Reduction -$30
Swap Employee 9 with Employee 7: Result: -1  Satisfaction; Pay Reduction -$30

So we leave shift assignments alone.

Proceed to reduce 4th or above Satisfaction Levels @ Pay $50 or above That would be Employees 1,2,3,4,5,6,7,8,9.
.
Employee 1: Shift 2, Satisfaction Level 3, Pay $40.
Employee 2: Shift 3, Satisfaction Level 2, Pay $70.
Employee 3: Shift 1, Satisfaction Level 4, Pay $40.
Employee 4: Shift 1, Satisfaction Level 3, Pay $60.
Employee 5: Shift 2, Satisfaction Level 5, Pay $40.
Employee 6: Shift 1, Satisfaction Level 5, Pay $40.
Employee 7: Shift 2, Satisfaction Level 3, Pay $30.
Employee 8: Shift 3, Satisfaction Level 4, Pay $50.
Employee 9: Shift 3, Satisfaction Level 3. Pay $80.

Total Budget: $450.

Proceed to reduce 5th or above Satisfaction Levels @ Pay $40. That would be all Employees except 7. First consider swapping shift pools. No swaps work to lower total pay without lowering satisfaction levels.

Employee 1: Shift 2, Satisfaction Level 3, Pay $40.
Employee 2: Shift 3, Satisfaction Level 2, Pay $70.
Employee 3: Shift 1, Satisfaction Level 5, Pay $30.
Employee 4: Shift 1, Satisfaction Level 3, Pay $60.
Employee 5: Shift 2, Satisfaction Level 6, Pay $30.
Employee 6: Shift 1, Satisfaction Level 6, Pay $30.
Employee 7: Shift 2, Satisfaction Level 3, Pay $30.
Employee 8: Shift 3, Satisfaction Level 4, Pay $50.
Employee 9: Shift 3, Satisfaction Level 6. Pay $70

Total Budget: $410.

Now if we pay Employees 3 and 6 each $25. an hour, we reach our budget of $400. The final pay/shift schedule is the following:

Employee 1: Shift 2, Satisfaction Level 3, Pay $40.
Employee 2: Shift 3, Satisfaction Level 2, Pay $70.
Employee 3: Shift 1, Satisfaction Level 5.5, Pay $25.
Employee 4: Shift 1, Satisfaction Level 3, Pay $60.
Employee 5: Shift 2, Satisfaction Level 6, Pay $30.
Employee 6: Shift 1, Satisfaction Level 5.5, Pay $25.
Employee 7: Shift 2, Satisfaction Level 3, Pay $30.
Employee 8: Shift 3, Satisfaction Level 4, Pay $50.
Employee 9: Shift 3, Satisfaction Level 6. Pay $70

Total Budget: $400.
The above shift/pay assignment looks realistic in that shift 3 (the least desirable) has the highest pay schedule while shift 1 (the most desirable) has the lowest pay schedule. 

One final example will illustrate the algorithm when swapping among shift pools occurs. We check for potential shift pool swaps when any employee is two or more satisfaction levels and two or more pay levels above the satisfaction/pay level being considered.

As a next to final example, consider this.

n = 9 employees
s = 3 shifts
r = 8 choices
t = 3 employees/shift
b = $400.
Pay preferences in increments of $10. starting at $10. per hour with $80. maximum

In this modified algorithm we consider shifting employees between shift pools at each stage of the process in addition to shifting them downward in satisfaction levels. At each stage consider a switch in shift assignments for an employee if that swap can increase overall satisfaction without increasing the total budget. 

Here are the employees’ (modified) preference lists:

Employee 1: [(2,80),(2,50),(2,40),(1,50),(1,40),(1,30),(2,30),(2,20),(2,10),(1,20)]
Employee 2: [(3,80),(3,70),(2,60),(2,50),(1,50),(1,40),(1,30),(2,60),(2,50),(2,40)]
Employee 3: [(1,70),(1,60),(1,50),(1,40),(1,30),(1,20),(2,70),(2,60),(2,50),(2,40)]
Employee 4: [(1,80),(1,70),(1,60),(2,80),(2,70),(2,60),(3,80),(3,70),(3,60),(3,50)]
Employee 5: [(2,80),(2,70),(2,60),(2,50),(2,40),(2,30),(3,80),(3,70),(3,60),(3,50)]
Employee 6: [(1,80),(1,70),(1,60),(1,50),(1,40),(1,30),(1,20),(1,10),(2,80),(2,70)]
Employee 7: [(2,60),(2,50),(2,30),(3,60),(3,50),(3,40),(1,80),(1,70),(1,60),(1,50)]
Employee 8: [(3,80),(3,70),(3,60),(3,50),(2,80),(2,70),(2,60),(2,50),(1,80),(1,70)]
Employee 9: [(1,80),(2,80),(3,80),(1,70),(2,70),(3,70),(1,60),(2,60),(3,60),(1,50)]

The initial assignments are as follows:

Shift 1: Employees 3,4,6
Shift 2: Employees 1,5,7
Shift 3: Employees 2,8,9

The payouts are as follows:

Shift 1: $70. + $80. + $80. = $230.
Shift 2: $80. + $80. + $60. = $220.
Shift 3: $80. + $80. + $80. = $240.
			Total   $690.

Now we proceed to cut satisfaction and pay levels. Employees 1,2 4,5,6,8 all have the highest satisfaction and pay levels. We downgrade each of these one satisfaction level to  come up with the following reassignments. Changes are underlined:

			Employee 1: Shift 2, Satisfaction Level 2, Pay $50
Employee 2: Shift 3, Satisfaction Level 2, Pay $70.
Employee 3: Shift 1, Satisfaction Level 1, Pay $70.
Employee 4: Shift 1, Satisfaction Level 2, Pay $70.
Employee 5: Shift 2, Satisfaction Level 2, Pay $70.
Employee 6: Shift 1, Satisfaction Level 2, Pay $70.
Employee 7: Shift 2, Satisfaction Level 1, Pay $60.
Employee 8: Shift 3, Satisfaction Level 2, Pay $70.
Employee 9: Shift 3, Satisfaction Level 3. Pay $80.

Total payout: $610.

Proceed to reduce 2nd or above Satisfaction Levels @ Pay $70 or above. That would be Employees 2,3,4,5,6,8.
			
			Employee 1: Shift 2, Satisfaction Level 2, Pay $50.
Employee 2: Shift 3, Satisfaction Level 2, Pay $70.
Employee 3: Shift 1, Satisfaction Level 2, Pay $60.
Employee 4: Shift 1, Satisfaction Level 3, Pay $60.
Employee 5: Shift 2, Satisfaction Level 3, Pay $60.
Employee 6: Shift 1, Satisfaction Level 3, Pay $60.
Employee 7: Shift 2, Satisfaction Level 1, Pay $60.
Employee 8: Shift 3, Satisfaction Level 3, Pay $60.
Employee 9: Shift 3, Satisfaction Level 3. Pay $80.

Total Budget = $560.

Proceed to reduce 3rd or above Satisfaction Levels @ Pay $60 or above. That would be Employees 2,3,4,5,6,7,8,9.

Employee 1: Shift 2, Satisfaction Level 2, Pay $50.
Employee 2: Shift 3, Satisfaction Level 2, Pay $70.
Employee 3: Shift 1, Satisfaction Level 3, Pay $50.
Employee 4: Shift 1, Satisfaction Level 3, Pay $60.
Employee 5: Shift 2, Satisfaction Level 4, Pay $50.
Employee 6: Shift 1, Satisfaction Level 4, Pay $50.
Employee 7: Shift 2, Satisfaction Level 2, Pay $50.
Employee 8: Shift 3, Satisfaction Level 4, Pay $50.
Employee 9: Shift 3, Satisfaction Level 3. Pay $80.

Total Budget = $510.

Now if we switch Employees 2 and 7, we can gain additional pay reductions without lowering either employee below satisfaction level 4. The new assigments are

Employee 1: Shift 2, Satisfaction Level 2, Pay $50.
Employee 2: Shift 2, Satisfaction Level 4, Pay $50.
Employee 3: Shift 1, Satisfaction Level 3, Pay $50.
Employee 4: Shift 1, Satisfaction Level 3, Pay $60.
Employee 5: Shift 2, Satisfaction Level 4, Pay $50.
Employee 6: Shift 1, Satisfaction Level 4, Pay $50.
Employee 7: Shift 3, Satisfaction Level 4, Pay $60.
Employee 8: Shift 3, Satisfaction Level 4, Pay $50.
Employee 9: Shift 3, Satisfaction Level 3. Pay $80.

Total Budget: $500.

Proceed to reduce 4th or above Satisfaction Levels @ Pay $50 or above. That would be Employees 1,2,3,4,5,6,7,8,9.

Employee 1: Shift 2, Satisfaction Level 3, Pay $40.
Employee 2: Shift 2, Satisfaction Level 4, Pay $50.
Employee 3: Shift 1, Satisfaction Level 4, Pay $40.
Employee 4: Shift 1, Satisfaction Level 3, Pay $60.
Employee 5: Shift 2, Satisfaction Level 5, Pay $40.
Employee 6: Shift 1, Satisfaction Level 5, Pay $40.
Employee 7: Shift 3, Satisfaction Level 5, Pay $50.
Employee 8: Shift 3, Satisfaction Level 4, Pay $50.
Employee 9: Shift 3, Satisfaction Level 3. Pay $80.

Total Budget: $450.

Proceed to reduce 5th or above Satisfaction Levels @ Pay $40 or above. That would be Employees 1,2,3,4,5,6,7,8,9.

Employee 1: Shift 2, Satisfaction Level 3, Pay $40.
Employee 2: Shift 2, Satisfaction Level 4, Pay $50.
Employee 3: Shift 1, Satisfaction Level 5, Pay $30.
Employee 4: Shift 1, Satisfaction Level 3, Pay $60.
Employee 5: Shift 2, Satisfaction Level 6, Pay $30.
Employee 6: Shift 1, Satisfaction Level 6, Pay $30.
Employee 7: Shift 3, Satisfaction Level 6, Pay $40.
Employee 8: Shift 3, Satisfaction Level 4, Pay $50.
Employee 9: Shift 3, Satisfaction Level 3. Pay $80.

Total Budget $410.

Finally, we reduce Employee 9 to satisfaction level 6.

Employee 1: Shift 2, Satisfaction Level 3, Pay $40.
Employee 2: Shift 2, Satisfaction Level 4, Pay $50.
Employee 3: Shift 1, Satisfaction Level 5, Pay $30.
Employee 4: Shift 1, Satisfaction Level 3, Pay $60.
Employee 5: Shift 2, Satisfaction Level 6, Pay $30.
Employee 6: Shift 1, Satisfaction Level 6, Pay $30.
Employee 7: Shift 3, Satisfaction Level 6, Pay $40.
Employee 8: Shift 3, Satisfaction Level 4, Pay $50.
Employee 9: Shift 3, Satisfaction Level 6. Pay $70.

Total Budget: $400.

This algorithm has demonstrated both reduction in satisfaction levels and swapping employees between different shift pools in order to bring the final budget within the budget constraint in  such a way as to give employees their choices of shifts and pay rates insofar as is possible.

Conclusions

This paper has shown that there are algorithms available that can allow employees to choose their shifts and pay rates in such a way that an overall budget constraint can be achieved while maximizing employee satisfaction. More complex algorithms which allow for more dimensions of choice and satisfaction could be developed. For instance, location of work assignment could be one parameter. Another could be type of work assuming that the employee is qualified for more than one kind of work.

Computer programs could be written in such a way that the employee can go to his or her home computer and by means of a user friendly graphical user interface input his or her preferences. Increased employee satisfaction will result because the employee has been empowered to make choices regarding his or her work schedule.