System and method for agent scheduling using mixed integer linear programming
A computer implemented method for agent scheduling using a Mixed Integer Programming (MILP) model, and a Mixed Integer Programming and Search Heuristic (MILP&SH) algorithm. The MILP model of the invention comprises of an objective function, decision variables, and constraints expressing tour group and shift template rules and required staffing levels as equations and inequalities. The MILP&SH algorithm comprises of an MILP solution algorithm and a search heuristic. The MILP solution algorithm applied to the MILP model to generate a plurality of solutions. If a solution generated by the MILP solution algorithm is an integer feasible solution, the search heuristic generates agent schedules. If a solution is not an integer feasible solution, the steps of the search heuristic are executed to find an integer feasible solution. The search heuristic compares the objective function value for an integer feasible solution found with the objective value for the best solution. If the integer feasible solution has a better objective function value, the best solution is replaced with the integer feasible solution. The MILP&SH algorithm iterates to generate integer feasible solutions, and updating the best solution and associated agent schedules. The MILP&SH algorithm terminates with a best solution found when one or more stopping conditions are satisfied.
1. A computer implemented method for agent scheduling for a plurality of agents, where agents' schedules are partly defined using tour groups comprising rules and templates, the method comprising:
a. acquiring, by a computer, from one or more computer systems scheduling environment information including a schedule period, intervals during the schedule period agents can work, tour groups wherein each tour group includes a minimum and maximum number of work days constraint during the schedule period for all agent schedules created using the tour group, shifts templates, minimum and maximum number of agents to schedule using each tour group, and schedule period;
b. acquiring, by the computer, from one or more computer systems required staffing levels for the intervals during the scheduling period;
c. acquiring, by the computer, from one or more computer systems an objective criterion and a direction for optimization as minimization or maximization of the objective function value;
d. formulating, by the computer, a Mixed Integer Linear Program model with decision variables, an objective function based on the objective criterion acquired and constraints to enforce the tour group and shift template rules, wherein the objective function value evaluated for an integer feasible solution with the objective function of the Mixed Integer Linear Program model provides a measure to compare a plurality of integer feasible solutions to determine a best solution, and the requirement for meeting required staffing levels in a solution of the Mixed Integer Linear Program model;
e. executing, by the computer, the steps of a Mixed Integer Linear Program and Search Heuristic algorithm to generate integer feasible solutions to the Mixed Integer Linear Program model until one or more stopping conditions are satisfied, wherein the Mixed Integer Linear Program and Search Heuristic algorithm repeats the steps of the Mixed Integer Linear Program solutions algorithm to find a plurality of solutions to the Mixed Integer Linear Program model and executes, for each said solution by the Mixed Integer Linear Program solution algorithm, the steps of the search heuristic to find an integer feasible solution to the Mixed Integer Linear Program model;
f. generating, by the computer, agent schedules based on the Mixed Integer Linear Program model found by the Mixed Integer Linear Program and Search Heuristic algorithm; and
g. inputting, by the computer, the agent schedules to one or more computer systems for rostering.
2. The computer implemented method for agent scheduling recited in claim 1 wherein the minimum and maximum number of work days specified by a tour group are either equal or the minimum number of work days is less than the maximum number of work days.
3. The computer implemented method for agent scheduling recited in claim 1 wherein the minimum and maximum number of work days specified by a tour group are satisfied by selecting the work patterns over the schedule period that have the number of work days greater than or equal to the minimum work day constraint for the tour group, and less than or equal to the maximum work day constraint for the tour group.
4. The computer implemented method for agent scheduling recited in claim 1 wherein each shift template in a tour group includes a minimum and a maximum number of work days to be scheduled using the shift template.
5. The computer implemented method for agent scheduling recited in claim 4 wherein the minimum and a maximum number of work days to be scheduled using the shift template are greater than or equal to the minimum number of work days specified for the tour group and less than or equal to the maximum number of work days specified for the tour group for all agent schedules created using the tour group.
6. The computer implemented method for agent scheduling recited in claim 4 wherein either the minimum and maximum number of work days to be scheduled using the shift template are either equal or the minimum number of work days is less than the maximum number of work days.
7. The computer implemented method for agent scheduling recited in claim 4 wherein the minimum and maximum number of work days to be scheduled using a shift template are included in the Mixed Integer Linear Program model as a plurality of constraints.
8. The computer implemented method for agent scheduling recited in claim 1 wherein the Mixed Integer Linear Program and Search Heuristic algorithm comprises a Mixed Integer Linear Program solution algorithm and a search heuristic.
9. The computer implemented method for agent scheduling recited in claim 1 wherein the Mixed Integer Linear Program and Search Heuristic algorithm calculates the objective function value for an integer feasible solution found and compares it with the objective function value for the best solution to determine if the integer feasible solution has an objective function value to replace the best solution.
10. A system for agent scheduling comprising:
a computer;
memory;
non-transitory computer implemented code with access to the memory, which, when executed, configures the computer to:
a. acquire from one or more computer systems scheduling environment information including a schedule period, intervals during the schedule period agents can work, tour groups wherein each tour group includes a minimum and maximum number of work days constraint during the schedule period for all agent schedules created using the tour group, shifts templates, minimum and maximum number of agents to schedule using each tour group, and schedule period;
b. acquire from one or more computer systems required staffing levels for the intervals during the scheduling period;
c. acquire from one or more computer systems an objective criterion and a direction for optimization as minimization or maximization of the objective function value;
d. formulate a Mixed Integer Linear Program model with decision variables, an objective function based on the objective criterion acquired and constraints to enforce the tour group and shift template rules, wherein the objective function value evaluated for an integer feasible solution with the objective function of the Mixed Integer Linear Program model provides a measure to compare a plurality of integer feasible solutions to determine a best solution, and the requirement for meeting required staffing levels in a solution of the Mixed Integer Linear Program model;
e. execute the steps of a Mixed Integer Linear Program and Search Heuristic algorithm to generate integer feasible solutions to the Mixed Integer Linear Program model until one or more stopping conditions are satisfied, wherein the Mixed Integer Linear Program and Search Heuristic algorithm repeats the steps of the Mixed Integer Linear Program solutions algorithm to find a plurality of solutions to the Mixed Integer Linear Program model and executes, for each said solution by the Mixed Integer Linear Program solution algorithm, the steps of the search heuristic to find an integer feasible solution to the Mixed Integer Linear Program model;
f. generate agent schedules based on the Mixed Integer Linear Program model found by the Mixed Integer Linear Program and Search Heuristic algorithm; and
g. input the agent schedules to one or more computer systems for rostering.
11. A computer program product for agent scheduling comprising:
non-transitory computer implemented code, which, when executed, configures a computer to:
a. acquire from one or more computer systems scheduling environment information including a schedule period, intervals during the schedule period agents can work, tour groups wherein each tour group includes a minimum and maximum number of work days constraint during the schedule period for all agent schedules created using the tour group, shifts templates, minimum and maximum number of agents to schedule using each tour group, and schedule period;
b. acquiring from one or more computer systems required staffing levels for the intervals during the scheduling period;
c. acquire from one or more computer systems an objective criterion and a direction for optimization as minimization or maximization of the objective function value;
d. creating formulate a Mixed Integer Linear Program model with decision variables, an objective function based on the objective criterion acquired and constraints to enforce the tour group and shift template rules wherein the objective function value evaluated for an integer feasible solution with the objective function of the Mixed Integer Linear Program model provides a measure to compare a plurality of integer feasible solutions to determine a best solution, and the requirement for meeting required staffing levels in a solution of the Mixed Integer Linear Program model;
e. execute the steps of a Mixed Integer Linear Program and Search Heuristic algorithm to generate integer feasible solutions to the Mixed Integer Linear Program model until one or more stopping conditions are satisfied, wherein the Mixed Integer Linear Program and Search Heuristic algorithm repeats the steps of the Mixed Integer Linear Program solutions algorithm to find a plurality of solutions to the Mixed Integer Linear Program model and executes, for each said solution by the Mixed Integer Linear Program solution algorithm, the steps of the search heuristic to find an integer feasible solution to the Mixed Integer Linear Program model;
f. generate agent schedules based on the Mixed Integer Linear Program model found by the Mixed Integer Linear Program and Search Heuristic algorithm; and
g. input the agent schedules to one or more computer systems for rostering.
12. The system for agent scheduling recited in claim 10 wherein the minimum and maximum number of work days specified by a tour group are either equal or the minimum number of work days is less than the maximum number of work days.
13. The system for agent scheduling recited in claim 10 wherein the minimum and maximum number of work days specified by a tour group are satisfied by selecting the work patterns over the schedule period that have the number of work days greater than or equal to the minimum work day constraint for the tour group, and less than or equal to the maximum work day constraint for the tour group.
14. The system for agent scheduling recited in claim 10 wherein each shift template in a tour group includes a minimum and a maximum number of work days to be scheduled using the shift template.
15. The system for agent scheduling recited in claim 14 wherein the minimum and a maximum number of work days to be scheduled using the shift template are greater than or equal to the minimum number of work days specified for the tour group and less than or equal to the maximum number of work days specified for the tour group for all agent schedules created using the tour group.
16. The system for agent scheduling recited in claim 14 wherein either the minimum and maximum number of work days to be scheduled using the shift template are either equal or the minimum number of work days is less than the maximum number of work days.
17. The system for agent scheduling recited in claim 14 wherein the minimum and maximum number of work days to be scheduled using a shift template are included in the Mixed Integer Linear Program model as a plurality of constraints.
18. The system for agent scheduling recited in claim 10 wherein the Mixed Integer Linear Program and Search Heuristic algorithm comprises a Mixed Integer Linear Program solution algorithm and a search heuristic.
19. The system for agent scheduling recited in claim 10 wherein the Mixed Integer Linear Program and Search Heuristic algorithm calculates the objective function value for an integer feasible solution found and compares it with the objective function value for the best solution to determine if the integer feasible solution has an objective function value to replace the best solution.