# Patent

## Title
Method and apparatus for cell-based workforce scheduling

## Abstract

A method for workforce scheduling by a computer system is provided. The method includes receiving a first workforce schedule describing initial assignments of a plurality of workers to a plurality of shifts, each shift comprising one or more work activities, each work activity comprising an activity and a time interval, and storing the first workforce schedule in a memory. The method also includes receiving a cell size associated with each activity, and determining a quantity of workers in each work activity associated with each activity in the first workforce schedule. The method further includes determining cell size violations by dividing the quantity of workers assigned to each work activity by the cell size for the activity associated with the work activity. The method also includes modifying the first workforce schedule to minimize cell size violations, resulting in a second workforce schedule, and storing the second workforce schedule in the memory.

## Background
TECHNICAL BACKGROUND
In many business environments the optimum staffing of employees is variable and complex. For example, some businesses may see seasonal affects in sales, while in other businesses the need for employees may vary throughout the day. As the number of employees increases, the complexity of scheduling these employees for work also increases.
In some environments, employees may work in teams for all or part of a shift, and these teams must be flexible, yet assigned based on the abilities of the employees. Further scheduling complications arise when groups of employees must use certain equipment to perform their tasks. Typically, the quantity of equipment available is limited and its use must be strictly scheduled.
OVERVIEW
In an embodiment, a method for workforce scheduling by a computer system is provided. The method includes receiving, in a processor, a first workforce schedule describing initial assignments of a plurality of workers to a plurality of shifts, each shift comprising one or more work activities, each work activity comprising an activity and a time interval, and storing the first workforce schedule in a memory.
The method also includes receiving a cell size associated with each activity, and determining a quantity of workers in each work activity associated with each activity in the first workforce schedule. The method further includes determining cell size violations by dividing the quantity of workers assigned to each work activity by the cell size for the activity associated with the work activity.
The method also includes modifying the first workforce schedule to minimize cell size violations, resulting in a second workforce schedule, and storing the second workforce schedule in the memory.
In another embodiment, a method for cell scheduling of a workforce to minimize occurrences of broken cells comprises generating a first workforce schedule having a global score and comprising a plurality of cells, each cell requiring a defined number of workers; identifying at least one target cell of the plurality of cells that is broken such that the target cell fails to have the defined number of workers scheduled identifying a plurality of repair solutions to resolve the target cell such that the target cell will have the defined number of workers scheduled; and selecting one of the plurality of repair solutions with which to modify the first workforce schedule based on an impact of each of the plurality of repair solutions on the global score.
In an embodiment, the first workforce schedule is generated using a local search process that evaluates a plurality of assignments of the workforce to shift events, and wherein the plurality of repair solutions comprises a subset of the plurality of assignments, and wherein the method further comprises running the local search process on the subset of the plurality of assignments to identify the impact of each of the plurality of repair solutions on the global score.
In an embodiment, generating the first workforce schedule includes evaluating a first quantity of assignments of the workforce to shift events, and wherein the plurality of repair solutions comprises a second quantity of the assignments of the workforce to the shift events that is less than the first quantity.
In an embodiment, the second quantity is at least two orders of magnitude less than the first quantity.
In an embodiment, the method includes modifying the first workforce schedule using the one of the repair solutions to generate a revised workforce schedule.
In an embodiment, the method includes evaluating each of the repair solutions to determine the impact of each of the plurality of repair solutions on the global score.
In an embodiment, a first repair solution of the plurality of repair solutions comprises deleting the target cell.
In an embodiment, a second repair solution of the plurality of repair solutions comprises swapping activities within the target cell with activities within at least one other cell of the plurality of cells.
In an embodiment, the first repair solution is selected as the one of the repair solutions if the impact of the first repair solution on the global score is less harmful than the impact of the second repair solution on the global score.
In an embodiment, the second repair solution is selected as the one of the repair solutions if the impact of the second repair solution on the global score is less harmful the impact of the second repair solution on the global score.
In an embodiment, a system for cell-based workforce scheduling is provided. The system includes a memory configured for storing workforce schedules, and a processor coupled to the memory. The processor configured to receive a first workforce schedule describing initial assignments of a plurality of workers to a plurality of shifts, each shift comprising one or more work activities, each work activity comprising an activity and a time interval, and store the first workforce schedule in the memory.
The processor is also configured to receive a cell size associated with each activity, and determine a quantity of workers in each work activity associated with each activity in the first workforce schedule. The processor is further configured to determine cell size violations by dividing the quantity of workers assigned to each work activity by the cell size for the activity associated with the work activity, and to modify the first workforce schedule to minimize cell size violations, resulting in a second workforce schedule. The processor stores the second workforce schedule in the memory.
In a further embodiment, a non-transitory, computer-readable medium having instructions stored thereon for operating a processor within a cell-based workforce scheduling system is provided. The instructions, when executed by the processor, direct the processor to receive a first workforce schedule describing initial assignments of a plurality of workers to a plurality of shifts, each shift comprising one or more work activities, each work activity comprising an activity and a time interval, and store the first workforce schedule in a memory.
The instructions also direct the processor to receive a cell size associated with each activity, and determine a quantity of workers in each work activity associated with each activity in the first workforce schedule. The instructions further direct the processor to determine cell size violations by dividing the quantity of workers assigned to each work activity by the cell size for the activity associated with the work activity.
The instructions also direct the processor to modify the first workforce schedule to minimize cell size violations, resulting in a second workforce schedule, and to store the second workforce schedule in the memory.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 illustrates a computer system configured for operating as a cell-based workforce scheduler.
FIG. 2 illustrates a flow chart of a method of operating a cell-based workforce scheduler.
FIG. 3 illustrates an example workforce schedule for use with a cell-based workforce scheduler.
FIG. 4 illustrates an example workforce schedule for use with a cell-based workforce scheduler.
FIG. 5 illustrates an example workforce schedule for use with a cell-based workforce scheduler.
FIG. 6 illustrates an example workforce schedule including station assignments for use with a cell-based workforce scheduler.
FIG. 7 illustrates an example workforce schedule including stations assignments for use with a cell-based workforce scheduler.
FIG. 8 illustrates an example station schedule for use with a cell-based workforce scheduler.
FIG. 9 illustrates a flow chart and data structure of a method of operating a cell-based workforce scheduler.
FIG. 10 illustrates a class diagram for cell-based workforce scheduling software.
FIGS. 11A and 11B illustrate example event bindings within a cell-based workforce scheduler.
FIG. 12 illustrates a flow chart and data structure of a method of operating a cell-based workforce scheduler.
FIG. 13 illustrates a class diagram for cell-based workforce scheduling software including station assignments.
FIG. 14 illustrates a flow chart and data structure for a method of cell-based workforce scheduling including station assignments.
FIG. 15 illustrates a block diagram of a computer system configured to operate as a cell-based workforce scheduler.



DETAILED DESCRIPTION
The following description and associated drawings teach the best mode of the invention. For the purpose of teaching inventive principles, some conventional aspects of the best mode may be simplified or omitted. The following claims specify the scope of the invention. Some aspects of the best mode may not fall within the scope of the invention as specified by the claims. Thus, those skilled in the art will appreciate variations from the best mode that fall within the scope of the invention. Those skilled in the art will appreciate that the features described below can be combined in various ways to form multiple variations of the invention. As a result, the invention is not limited to the specific examples described below, but only by claims and their equivalents.
Industry experts have determined that when performing certain tasks: task activity handle times are about the same, task activities are always handled in the same order, and groups of workers are skilled for all of the activities of the task. Thus, grouping task activities into composite activities or “cells” will increase overall efficiency. This efficiency may be obtained by creating cell-based workforce schedules.
In a cell-based workforce, a task will be completed earlier as the task will not have to wait for someone to come available for the next activity, workers in the cell will all have the ability to perform the next task activity. Worker idle time is reduced as workers do not have to wait to start the next task activity, but may begin as soon as they are able.
In a cell-based workforce schedule, a plurality of workers are assigned to a plurality of shifts. Each shift comprises one or more work activity, and each work activity comprises an activity and a time interval. Typically time intervals constitute one hour, but in some embodiments may be longer or shorter. A cell size constraint is included in the cell-based workforce scheduler. This constraint requires that at any moment in time, the number of workers performing any activity must divide evenly into the “cell size” for the activity.
For example, if an activity requires three workers, it has a “cell size” of three, and only multiples of three workers may be assigned to that activity at any given time without creating a cell size violation. Employees are divided into groups of workers, or cells, all working on the same composite activity. These composite activities may vary throughout the shift as required, and since the composite activities vary, the required cell size may vary throughout a shift.
The goal of a cell-based workforce scheduler is to reduce as much as possible the number of cell size variations within a given cell-based workforce schedule. This optimization may be performed using any of a wide variety of methods. For example, work activities may be shuffled in time during the day to try and minimize cell size violations. Workers may be assigned to different activities to fill out partial cells. Work activities having partially filled cells may be combined to constitute a completely filled cell.
In some work environments, one or more work stations may be provided for various work activities. Typically, these stations are configured to support use by a limited number of workers. If too many workers are assigned to a station at any given time, excess workers will be idle since the other workers will be filling all the possible positions at the work station. This fact further complicates workforce scheduling.
For example, a work activity may require the use of one of two available work stations. If three cells are assigned to the work activity at the same time, the stations are overloaded since two stations are available for use by three cells of workers. In some embodiments, cell-based workforce schedulers are configured to optimize use of work stations and to prevent double-booking any work station.
FIG. 1 illustrates a computer system 100 configured for operating as a cell-based workforce scheduler 102. In this example embodiment, cell-based workforce scheduler 102 includes processor 104 and memory 106. Workforce scheduler 102 receives first workforce schedule 108, a cell size 110 associated with each activity in first workforce schedule 108, and optionally station information 112 related to first work force schedule 108.
These inputs may be stored by workforce scheduler 102 in memory 106. Processor 104 operates on first workforce schedule 108 and cell sizes 110 to produce an optimized cell-based second workforce schedule 114. Second workforce schedule 114 has been produced by workforce scheduler 102 in such a manner as to completely fill all work cells as completely as possible. Methods for optimizing cell-based workforce schedules are described in detail below.
FIG. 2 illustrates a flow chart of a method of operating a cell-based workforce scheduler. In this example embodiment, a cell-based workforce scheduler 102 receives a first workforce schedule 108, (operation 200). First workforce schedule 108 may be received through a communication interface, an input device, a non-transitory memory device, or the like.
Cell-based workforce scheduler 102 stores first workforce schedule 108 in memory 106, (operation 202). Cell-based workforce scheduler 102 receives a cell size 110 associated with each activity in first workforce schedule 108, (operation 204). Cell sizes may be received through a communication interface, an input device, a non-transitory memory device, or the like.
Cell-based workforce scheduler 102 determines a quantity of workers in each work activity associated with each activity in first workforce schedule 108, (operation 206). This determination may be obtained simply by parsing first workforce schedule 108 and adding up how many workers are assigned to each work activity associated with each activity in first workforce schedule 108.
Cell-based workforce scheduler 102 determines if any cell size violations exist, (operation 208). For example, if nine workers are assigned to a work activity having a cell size of four, there is a cell size violation of one worker since one worker is left over when two teams of four are created.
Cell-based workforce scheduler 102 modifies first workforce schedule 108 to reduce cell size violations and produce second workforce schedule 114, (operation 210). This modification of first workforce schedule 108 may be performed using any of a wide variety of methods. For example, work activities may be shuffled in time during the day to try and minimize cell size violations. Workers may be assigned to different activities to fill out partial cells. Work activities having partially filled cells may be combined to constitute a completely filled cell.
Second workforce schedule 114 is stored in memory 106, (operation 212). Second workforce schedule may also be provided to a user through a display, communication interface, or other output device. The format of second workforce schedule 114 may vary greatly according to the requirements of users of cell-based workforce scheduler 102.
FIG. 3 illustrates an example workforce schedule for use with a cell-based workforce scheduler. In this example embodiment, a very simple first workforce schedule is shown. This example schedule includes workforce assignments for 10 cells over one six hour shift. Each of these cells represents one or more workers who perform their jobs together. Each work activity may require a different number of workers at different times to perform an activity associated with each cell at each time. Each block of this schedule represents a work activity which has a cell size requirement and a number of workers currently assigned to the work activity.
This example schedule illustrates a six hour shift starting at 09:00 and ending at 15:00. Each block in the schedule represents one work activity occurring for one hour. Each block contains data of the format (X−Y) where X is the cell size, or the number of workers required to fill a cell for this particular work activity at this particular time, and Y is the number of workers currently assigned to this work activity. Blocks which are cross hatched are not currently assigned to any workers.
In this example, cell—1, representing one or more workers, starts at 09:00 with a work activity requiring four workers, but only one worker is assigned. This is a cell size violation. At 10:00 and 11:00, cell—1 is assigned work activities requiring four workers, with four assigned. These are complete cells since they contain the required number of workers. Cell—1 also has complete cells assigned at 12:00, 13:00, and 14:00 hours, these cells requiring three, two, and two workers respectively.
Cell—2 also represents one or more workers, and has a cell size violation at 11:00 when one worker is assigned to a work activity with a cell size of three. Cell—2 also has a cell size violation at 12:00 where three workers are assigned to a work activity with a cell size of two. Cell—3 has been assigned only work activities requiring four workers, and has four workers assigned to each work activity. Thus, it has no cell size violations and only includes complete cells. Likewise, cell—4 and cell—5 have no cell size violations.
Cell—6 has a cell size violation at 09:00 where one worker is assigned to a work activity having a cell size of two. Cell—7 has only been assigned one work activity for the day requiring two workers.
FIG. 4 illustrates an example workforce schedule for use with a cell-based workforce scheduler. This example workforce schedule shows the workforce schedule of FIG. 3 when all of the work activities having cell size violations have been removed from the workforce schedule, leaving holes in the workforce schedule.
Note that the work activity for cell—1 at 09:00 has been removed, along with the work activities for cell—2 at 11:00 and 12:00, and cell 6 at 09:00. This allows the cell-based workforce scheduler to re-assign these workforce activities in such a manner as to have complete cells.
FIG. 5 illustrates an example workforce schedule for use with a cell-based workforce scheduler. This example workforce schedule shows the results of a cell-based workforce scheduler combining work activities to remove cell size violations from the workforce schedule of FIG. 4.
In this example, the work activities for cell—1, cell—6, and cell—7 at 09:00 have been combined into a work activity for cell—1 at 09:00 with a cell size of four, and with four workers assigned to the activity. The work activities for cell—6 and cell—7 at 09:00 have been canceled.
The work activity for cell—2 at 11:00 has re-appeared, and still has a cell size violation, however the work activity for cell—2 at 12:00 has not re-appeared. In this example, the cell-based workforce scheduler was unable to fill in the required three workers for this particular work activity. While this example illustrates a case where an incomplete cell is allowed to stay in the workforce schedule, other embodiments may be configured to delete all cell size violations from the workforce schedule.
In this example embodiment, understaffing cell size violations are weighed less than overstaffing cell size violations. Thus, some understaffing violations, such as cell—2 at 11:00 are allowed, while the overstaffing violation of cell—2 at 12:00 is not allowed. Other embodiments may weigh overstaffing violations less than understaffing violations, and such an embodiment would allow the overstaffing violation of cell—2 at 12:00, but not the understaffing violation of cell—2 at 11:00.
FIG. 6 illustrates an example workforce schedule including station assignments for use with a cell-based workforce scheduler. In this example, a first workforce schedule has been provided that includes station assignments for each work activity. This example workforce schedule has a six hour shift broken down into six one hour time intervals. Ten different cells of employees are assigned to work activities requiring the use of seven different work stations.
In this example, cell—1 is assigned to station—1 at 09:00, 10:00, and 14:00. Cell—1 is assigned to station—3 at 11:00, 12:00, and 13:00. Other cells are assigned to stations in a similar manner. Note that at 10:00 both cell—1 and cell—4 are assigned to station—1. This is a station violation since it is assumed in this example that each station is configured for operation by only one cell of workers at a time. At 11:00 station—7 is assigned to both cell—9 and cell—10, and at 13:00 station 4 is assigned to both cell—3 and cell—4.
FIG. 7 illustrates an example workforce schedule including stations assignments for use with a cell-based workforce scheduler. In this example, a cell-based workforce scheduler has processed the first workforce schedule from FIG. 6 to remove station violations and has produced the second workforce schedule shown in FIG. 7.
In this example, the cell-based workforce scheduler has swapped a number of work activities to remove station violations. Cell—4 has had its 10:00 work activity swapped with its 13:00 work activity to remove a station violation at station—1. Also cell—10 has had its 11:00 work activity shifted to 12:00 to remove a station violation at station—7.
FIG. 8 illustrates an example station schedule for use with a cell-based workforce scheduler. Workforce schedules may be provided to a user in a wide variety of formats. For example, graphical displays such as those illustrated in FIGS. 3-7 may be used to communicate workforce schedules to a user. Similarly, textual workforce schedules such as shown in FIG. 8 may be provided to a user.
In this example embodiment, a workforce schedule for station—1 on a particular <date> is illustrated. Here station—1 is assigned to activity cell-ops 2 for the entire shift. However, cell—1 is assigned to station—1 at 09:00, 10:00, 13:00, and 14:00, while cell—3 is assigned to station—1 at 11:00 and 12:00. (This corresponds to the schedule of station—1 illustrated in FIG. 7.)
FIG. 9 illustrates a flow chart and data structure of a method of operating a cell-based workforce scheduler. In this example embodiment, a method of assigning work activities to a plurality of employees is illustrated. This example illustrates an exemplary embodiment of data structures within a cell-based workforce scheduler. Other embodiments may use differing data structures to perform the methods of workforce scheduling described herein.
Each work activity variable is examined, (operation 900). If the work activity variable belongs to a cell (i.e., has been assigned to a worker), (operation 902), it is added to intervals in its domain, (operation 904).
For example, employee—1 912 is associated with an interval table 914. Interval table 914 includes a plurality of time intervals, each having one or more work activity variables, and the first one is illustrated here as the 08:00 interval. In this example, employee—1 has not been assigned any work activities.
Employee—2 916 is associated with interval table 918 including a plurality of time intervals, each having one or more work activity variables. In this example, employee—2 916 at time interval 08:00 has associated with it work activities “payments” 920 and “claims” 922. A third interval table 906 is shown with work activities “payments” 908 and “claims” 910. In some embodiments this structure may represent an interval table that has not yet been associated with a particular employee.
FIG. 10 illustrates a class diagram for cell-based workforce scheduling software. This example class diagram illustrates the relationship between various software objects in an embodiment of a cell-based workforce scheduler. Other embodiments may use different software objects having different relationships in performing the methods described herein.
In this example embodiment of a cell-based workforce scheduling system, three software objects are associated with work activities 1006. This example system includes a class named “Variable” 1000. “Variable” includes four operations: Bind, Unbind, IsConsistent, and GetDomain.
The system also includes a class named “Cell” 1004 which is associated with class “Variable” 1000, and work activities 1006. “Cell” 1004 includes four attributes: Activity:ID, start:Interval, duration:number, and work activity variables links:collection. “Cell” 1004 also includes four operations: Bind, Unbind, IsConsistent, and GetDomain.
The system further includes a class named “WorkActivity” 1002 which is associated with class “Variable” 1000, and work activities 1006. “WorkActivity” 1002 includes one attribute: slot:id, along with four operations: Bind, Unbind, IsConsistent, and GetDomain.
FIGS. 11A and 11B illustrate example event bindings within a cell-based workforce scheduler. FIG. 11A illustrates an example embodiment of a cell-based workforce scheduler where three employees are being assigned to process mail from 08:00 to 10:00. In this example data structure Cell-A 1100 represents the work activity “mail” and includes the interval between 08:00 through 10:00.
In this example, employee—1 is associated with a work activity of “mail” 1102, employee—2 is associated with a work activity of “mail” 1104, and employee—3 is associated with a work activity of “mail”. These bindings take place within the exemplary data structure illustrated in FIG. 11A. However, other embodiments may use other data structures to perform these associations.
FIG. 11B illustrates the same binding as FIG. 11A, however, in this example the three employees has already been assigned to process claims or to sort for the interval. Thus, the employee's data structures must first be unbound from their previous assignments before they may be bound to their new assignments.
In this example, employee—1 is unbound from work activity “claims” 1108, and bound to work activity “mail” 1116. Employee—2 is unbound from work activity “claims” 1110, and bound to work activity “mail” 1118. Employee—3 is unbound from work activity “sorting” 1112, and bound to work activity “mail” 1120. In this way, Cell-B 1114 representing the work activity “mail” is staffed with three employees who had previously been assigned to other work activities.
FIG. 12 illustrates a flow chart and data structure of a method of operating a cell-based workforce scheduler. In this example embodiment, until convergence is reached (operation 1200), for each interval (operation 1202), for each cell activity (operation 1204), for each cell length (operation 1206), a cell of type A or type B is built (operation 1208). Type A cells are complete cells, comprising work activity variables of the same activity as the cell, and can represent a cell to add (i.e. a complete hole to fill) or a cell to remove. Type B cells represent incomplete holes. To fill this hole, a smaller cell is removed to make room for this cell.
An ObjectiveFunction 1224 software object is utilized to determine if any improvement is obtained (operation 1210). If there is no improvement, convergence has been reached (operation 1212), otherwise control returns to operation 1200.
In this example, LocalSearch 1214 is performed to optimize the schedule of employee—1. Cell-A 1216 representing a work activity of “mail” from 08:00 to 10:00 is added, and work activities of “mail” for employee—1 1218, employee—2 1220, and employee—3 1222, are bound, unbound, or checked for consistency as necessary. These changes are propagated to ObjectiveFunction 1224 where the service goal and min/max hours for the employees are scored.
FIG. 13 illustrates a class diagram for cell-based workforce scheduling software including station assignments. This example class diagram illustrates the relationship between various software objects in an embodiment of a cell-based workforce scheduler. Other embodiments may use different software objects having different relationships in performing the methods described herein.
In this example embodiment, five software objects are associated in a system for cell-based workforce scheduling including station assignments. This example system includes a class named “Variable” 1300 having four operations: Bind, Unbind, IsConsistent, and GetDomain.
This example system also includes a class named “WorkActivity” 1302 associated with class “Variable” 1300. Class “WorkActivity” 1302 includes one attribute of slot:id and four operations: Bind, Unbind, IsConsistent, and GetDomain.” This system further includes a class named “Cell” 1306 associated with class “Variable” 1300 and class “WorkActivity” 1302. Class “Cell” 1306 includes four attributes: Activity:ID, start:Interval, duration:number, and work activity variables links: collection. Class “Cell” 1306 also includes four operations: Bind, Unbind, IsConsistent, and GetDomain.
This system also includes a class named “StationAssignment” 1304 having three operations: Bind, Unbind, and IsConsistent. The system further includes a class named “Station” 1308 having one attribute of Cell:id, and three operations: Alloc, Dealloc, and IsAvailable.
FIG. 14 illustrates a flow chart and data structure for a method of cell-based workforce scheduling including station assignments. In this example embodiment of a cell-based workforce scheduler including station assignments, a first workforce schedule is sorted by activity and start interval (operation 1400). For each cell (operation 1402) the cell's station assignment is thrown into a local search (operation 1404). LocalSearch (operation 1406) optimizes the current cell's (Cell-A) station assignment. When the station assignment is optimized the method is done (operation 1408).
The cell's station assignment is optimized through LocalSearch 1406 which is associated with the class “Variable” 1410. The class “Variable” 1410 includes four operations: Bind, Unbind, IsConsistent, and GetDomain. The class “Variable” 1410 is associated with the StationAssignment 1412 for the current cell (Cell-A) where the domain is any station.
In this example embodiment, six stations 1414-1426 are available for Cell-A to be assigned to through the operations of Alloc, Dealloc, and IsAvailable from StationAssignment 1412.
FIG. 15 illustrates a block diagram of a computer system configured to operate as a cell-based workforce scheduler 1500. The cell-based workforce scheduler is implemented on workforce scheduler 1500, as shown in FIG. 15. Workforce scheduler 1500 includes communication interface 1502, display 1504, input devices 1506, output devices 1508, processor 1510, and storage system 1512. Processor 1510 is linked to communication interface 1502, display 1504, input devices 1506, output devices 1508, and storage system 1512. Storage system 1512 includes a non-transitory memory device that stores operating software 1514.
Communication interface 1502 includes components that communicate over communication links, such as network cards, ports, RF transceivers, processing circuitry and software, or some other communication devices. Communication interface 1502 may be configured to communicate over metallic, wireless, or optical links. Communication interface 1502 may be configured to use TDM, IP, Ethernet, optical networking, wireless protocols, communication signaling, or some other communication format—including combinations thereof.
Display 1502 may be any type of display capable of presenting information to a user. Displays may include touch screens in some embodiments. Input devices 1506 include any device capable of capturing user inputs and transferring them to workforce scheduler 1500. Input devices 1506 may include a keyboard, mouse, touch pad, or some other user input apparatus. Output devices 1508 include any device capable of transferring outputs from workforce scheduler 1500 to a user. Output devices 1508 may include printers, projectors, displays, or some other user output apparatus. Display 1504, input devices 1506, and output devices 1508 may be external to workforce scheduler 1500 or omitted in some examples.
Processor 1510 includes a microprocessor and other circuitry that retrieves and executes operating software 1514 from storage system 1512. Storage system 1512 includes a disk drive, flash drive, data storage circuitry, or some other non-transitory memory apparatus. Operating software 1514 includes computer programs, firmware, or some other form of machine-readable processing instructions. Operating software 1514 may include an operating system, utilities, drivers, network interfaces, applications, or some other type of software. When executed by processing circuitry, operating software 1514 directs processor 1510 to operate workforce scheduler 1500 as described herein for a cell-based workforce scheduler.
In this example, workforce scheduler 1500 executes a number of methods stored as software 1514 within storage system 1512. The results of these workforce scheduling methods are displayed to a user via display 1504, or output devices 1508. Input devices 1506 allows users to input a variety of data required by the workforce scheduling system.
For example, processor 1510 receives a first workforce schedule, cell sizes, and station information either from communication interface 1502, input devices 1506, or storage system 1512. Processor 1510 then operates on the first workforce schedule, cell sizes, and station information to produce a cell-based optimized second workforce schedule which may be stored in storage system 1512, displayed on display 1504, or output through output devices 1508.
It should be understood that it would be possible to not actually remove station violations. Rather, some implementations could begin with a cell not having any station assignments and a finite number of stations. Then each cell must be assigned a station in a way that does not violate the hard constraints that 1) no two cells may occupy a station at the same time and 2) a station may contain only one cell type (i.e. activity) during a scheduling period. As a result of combinatorial search, either every cell will be assigned a station or we may run out of stations (which can be considered a conflict).
The following briefly describes one implementation of a system for cell-based workforce scheduling. The system comprises a memory configured for storing workforce schedules. The system also comprises a processor coupled to the memory, the processor configured to receive a first workforce schedule describing initial assignments of a plurality of workers to a plurality of shifts, each shift comprising one or more work activities, each work activity comprising an activity and a time interval, store the first workforce schedule in the memory, receive a cell size associated with each activity, determine a quantity of workers in each work activity associated with each activity in the first workforce schedule, determine cell size violations by dividing the quantity of workers assigned to each work activity by the cell size for the activity associated with the work activity, modify the first workforce schedule to minimize cell size violations, resulting in a second workforce schedule, and store the second workforce schedule in the memory.
The processor may be further configured to modify the first workforce schedule to minimize cell size violations by selecting a shift within the first workforce schedule, swapping a pair of work activities within the shift, and determining if the swap reduced the number of cell size violations in the first workforce schedule.
The processor may further configured to assign two or more employees to a cell, where each cell is associated with the two or more employees, an activity, and the time interval of the cell.
The processor may be further configured to modify the first workforce schedule to minimize cell size violations by removing any incomplete cells from the first workforce schedule for each time interval within the first workforce schedule, processing the results of the cell removal to identify any holes in the first workforce schedule, processing the holes in the first workforce schedule to determine if any holes exist that may be filled by a cell, and filling the hole in the schedule by a work activity performed by the cell.
The processor may be further configured to receive a “Prefer Overstaffing” command, and modify the first workforce schedule to minimize cell size violations, but weighing overstaffing violations less than understaffing violations, resulting in a second workforce schedule.
The processor may be further configured to receive a “Prefer Understaffing” command, and modify the first workforce schedule to minimize cell size violations, but weighing understaffing violations less than overstaffing violations, resulting in a second workforce schedule.
The processor may be further configured to receive station assignment information representing physical locations where groups of employees work, determine station assignment violations by processing the first workforce schedule and the station assignment information to find any times where more than one cell is assigned to a single station or more than one cell type is assigned to a single station, and in the processor, modify the first workforce schedule to minimize cell size violations and station assignment violations, resulting in a second workforce schedule.
Advantageously, the system, methods, and software discussed above provide for a single bind/unbind operation during local search results in a reassigning of a plurality of variables (in this case work activity assignments). In prior system a binding during search resulted in the reassignment of a single variable (normally a shift assignment or work activity assignment)—which could be considered a simple repair. The concepts introduced herein consider the notion of search over more complex repairs involving multiple variables (in this case multiple work activity assignments). The granularity of a binding discussed herein is multiple variables, or a complex repair, in contrast with a single variable binding or a simple repair. Previously, the result of local search, particularly when the local search space was a multitude of variables, could be view as a complex repair. However, by making each binding (i.e. each element of search) a more complex repair in itself, the amount of search necessary is greatly reduced.
The above description and associated figures teach the best mode of the invention. The following claims specify the scope of the invention. Note that some aspects of the best mode may not fall within the scope of the invention as specified by the claims. Those skilled in the art will appreciate that the features described above can be combined in various ways to form multiple variations of the invention. As a result, the invention is not limited to the specific embodiments described above, but only by the following claims and their equivalents.

## Claims

1. A computer implemented method for operating a computer system as a cell-based workforce scheduler to minimize occurrences of broken cells, the method comprising:
Generating by means of a processor, a first workforce schedule having a global score and comprising a plurality of cells, each cell requiring a defined number of workers;
Identifying, by means of a processor at least one target cell of the plurality of cells that is broken such that the target cell fails to have the defined number of workers scheduled;
identifying by means of a processor a plurality of repair solutions to resolve the target cell such that the target cell will have the defined number of workers scheduled; and,
selecting by means of a processor one of the plurality of repair solutions with which to modify the first workforce schedule based on an impact of each of the plurality of repair solutions on the global score;
providing to a user by means of a processor, a modified workforce schedule based on the selected repair solution.

2. The method of claim 1 wherein the first workforce schedule is generated using a local search process that evaluates a plurality of assignments of the workforce to shift events, and wherein the plurality of repair solutions comprises a subset of the plurality of assignments, and wherein the method further comprises running the local search process on the subset of the plurality of assignments to identify the impact of each of the plurality of repair solutions on the global score.

3. The method of claim 1 wherein generating the first workforce schedule includes evaluating a first quantity of assignments of the workforce to shift events, and wherein the plurality of repair solutions comprises a second quantity of the assignments of the workforce to the shift events that is less than the first quantity.

4. The method of claim 3 wherein the second quantity is less than one percent of the first quantity.

5. The method of claim 1 further comprising modifying the first workforce schedule using the one of the repair solutions to generate a revised workforce schedule.

6. The method of claim 1 further comprising evaluating each of the repair solutions to determine the impact of each of the plurality of repair solutions on the global score.

7. The method of claim 6 wherein a first repair solution of the plurality of repair solutions comprises deleting the target cell.

8. The method of claim 7 wherein a second repair solution of the plurality of repair solutions comprises swapping activities within the target cell with activities within at least one other cell of the plurality of cells.

9. The method of claim 8 wherein the first repair solution is selected as the one of the repair solutions if the first repair solution reduces the global score less than the second repair solution reduces the global score.

10. The method of claim 9 wherein the second repair solution is selected as the one of the repair solutions if the second repair solution reduces the global score less than the first repair solution reduces the global score.

11. A non-transitory computer readable medium having stored thereon program instructions for cell scheduling of a workforce to minimize occurrences of broken cells, that when executed by a computer processor, direct the computer processor to:
generate a first workforce schedule having a global score and comprising a plurality of cells, each cell requiring a defined number of workers;
identify at least one target cell of the plurality of cells that is broken such that the target cell fails to have the defined number of workers scheduled;
identify a plurality of repair solutions to resolve the target cell such that the target cell will have the defined number of workers scheduled;
select one of the plurality of repair solutions with which to modify the first workforce schedule based on an impact of each of the plurality of repair solutions on the global score; and
provide to a user, a modified workforce schedule based on the selected repair solution.

12. The computer readable medium of claim 11 wherein the first workforce schedule is generated using a local search process that evaluates a plurality of assignments of the workforce to shift events, and wherein the plurality of repair solutions comprises a subset of the plurality of assignments, and wherein the method further comprises running the local search process on the subset of the plurality of assignments to identify the impact of each of the plurality of repair solutions on the global score.

13. The computer readable medium of claim 11 wherein to generate the first workforce schedule the program instructions direct the computer system to evaluate a first quantity of assignments of the workforce to shift events, and wherein the plurality of repair solutions comprises a second quantity of the assignments of the workforce to the shift events that is less than the first quantity.

14. The computer readable medium of claim 13 wherein the second quantity is less than one percent of the first quantity.

15. The computer readable medium of claim 11 wherein the program instructions further direct the computer system to modify the first workforce schedule using the one of the repair solutions to generate a revised workforce schedule.

16. The computer readable medium of claim 11 wherein the program instructions further direct the computer system to evaluate each of the repair solutions to determine the impact of each of the plurality of repair solutions on the global score.

17. The computer readable medium of claim 16 wherein a first repair solution of the plurality of repair solutions comprises deleting the target cell.

18. The computer readable medium of claim 17 wherein a second repair solution of the plurality of repair solutions comprises a swap of activities within the target cell with activities within at least one other cell of the plurality of cells.

19. The computer readable medium of claim 18 wherein the first repair solution is selected as the one of the repair solutions if the first repair solution reduces the global score less than the second repair solution reduces the global score.

20. The computer readable medium of claim 19 wherein the second repair solution is selected as the one of the repair solutions if the second repair solution reduces the global score less than the first repair solution reduces the global score.