WORKFORCE SCHEDULING BASED ON PROBLEM DECOMPOSITION

1 . A method, comprising:

identifying, by a processing device, a plurality of variables associated with scheduling a plurality of workers to perform a plurality of jobs during a plurality of time periods;

identifying a plurality of constraints associated with the plurality of variables;

identifying a principal scheduling problem for optimizing a principal objective function defined on a principal subset of a plurality of variables subject to a principal subset of the plurality of constraints, wherein each variable of the principal subset is associated with a worker schedule of a corresponding worker;

determining a tentative solution of the principal scheduling problem;

identifying one or more sub-problems, each sub-problem associated with a subset of constraints that are not satisfied by a tentative schedule defined by the tentative solution;

identifying, by solving the one or more sub-problems, one or more candidate variables improving a value of the principal objective function;

modifying the principal scheduling problem by appending the one or more candidate variables to the principal scheduling problem; and

generating, by solving the modified principal scheduling problem, a schedule to assign at least the plurality of workers to perform at least the plurality of jobs during at least the plurality of time periods.

2 . The method of claim 1 , wherein the schedule is represented by a finite set of n-tuples, each n-tuple specifying at least one of: a shift identifier, a job identifier, or a worker identifier.

3 . The method of claim 1 , wherein the principal objective function reflects a chosen quality metric associated with the schedule.

4 . The method of claim 1 , wherein the principal subset of the plurality of constraints specifies global constraints.

5 . The method of claim 1 , wherein solving the sub-problem further comprises:

performing neighborhood search in a vicinity of a known solution of the principal problem.

6 . The method of claim 1 , wherein each sub-problem of the one or more sub-problems is generated responsive to identifying a corresponding sub-schedule of the tentative solution of the principal problem, wherein a value of a chosen quality metric of the corresponding sub-schedule exceeds a predefined threshold value.

7 . The method of claim 1 , wherein each sub-problem of the one or more sub-problems is solved by a dedicated execution environment provided by one of: a processing thread, a physical server, or a virtual machine.

8 . A system, comprising:

a memory; and

a processing device coupled to the memory, the processing device configured to:

identify a plurality of variables associated with scheduling a plurality of workers to perform a plurality of jobs during a plurality of time periods;

identify a plurality of constraints associated with the plurality of variables;

identify a principal scheduling problem for optimizing a principal objective function defined on a principal subset of a plurality of variables subject to a principal subset of the plurality of constraints, wherein each variable of the principal subset is associated with a sub-schedule of a corresponding worker;

determine a tentative solution of the principal scheduling problem;

identify one or more sub-problems, each sub-problem associated with a subset of constraints that are not satisfied by a tentative schedule defined by the tentative solution;

identify, by solving the one or more sub-problems, one or more candidate variables improving a value of the principal objective function;

modify the principal scheduling problem by appending the one or more candidate variables to the principal scheduling problem; and

generate, by solving the modified principal scheduling problem, a schedule to assign at least the plurality of workers to perform at least the plurality of jobs during at least the plurality of time periods.

9 . The system of claim 8 , wherein the schedule is represented by a finite set of n-tuples, each n-tuple specifying at least one of: a shift identifier, a job identifier, or a worker identifier.

10 . The system of claim 8 , wherein the principal objective function reflects a chosen quality metric associated with the schedule.

11 . The system of claim 8 , wherein the principal subset of the plurality of constraints specifies global constraints associated with each variable of the principal subset of the plurality of variables.

12 . The system of claim 8 , wherein solving the sub-problem further comprises:

performing neighborhood search in a vicinity of a known solution of the sub-problem.

13 . The system of claim 8 , wherein each sub-problem of the one or more sub-problems is generated responsive to identifying a corresponding sub-schedule of the tentative solution of the principal problem, wherein a value of a chosen quality metric of the corresponding sub-schedule exceeds a predefined threshold value.

14 . The system of claim 8 , wherein each sub-problem of the one or more sub-problems is solved by a dedicated execution environment provided by one of: a processing thread, a physical server, or a virtual machine.

15 . A computer-readable non-transitory storage medium comprising executable instructions that, when executed by a processing device, cause the processing device to:

identify a plurality of variables associated with scheduling a plurality of workers to perform a plurality of jobs during a plurality of time periods;

identify a plurality of constraints associated with the plurality of variables;

identify a principal scheduling problem for optimizing a principal objective function defined on a principal subset of a plurality of variables subject to a principal subset of the plurality of constraints, wherein each variable of the principal subset is associated with a worker schedule of a corresponding worker;

determine a tentative solution of the principal scheduling problem;

identify one or more sub-problems, each sub-problem associated with a subset of constraints that are not satisfied by a tentative schedule defined by the tentative solution;

identify, by solving the one or more sub-problems, one or more candidate variables improving a value of the principal objective function;

modify the principal scheduling problem by appending the one or more candidate variables to the principal scheduling problem; and

generate, by solving the modified principal scheduling problem, a schedule to assign at least the plurality of workers to perform at least the plurality of jobs during at least the plurality of time periods.

16 . The computer-readable non-transitory storage medium of claim 15 , wherein the schedule is represented by a finite set of n-tuples, each n-tuple specifying at least one of: a shift identifier, a job identifier, or a worker identifier.

17 . The computer-readable non-transitory storage medium of claim 15 , wherein the principal objective function reflects a chosen quality metric associated with the schedule.

18 . The computer-readable non-transitory storage medium of claim 15 , wherein the principal subset of the plurality of constraints specifies global constraints associated with each variable of the principal subset of the plurality of variables.

19 . The computer-readable non-transitory storage medium of claim 15 , wherein solving the sub-problem further comprises:

performing neighborhood search in a vicinity of a known solution of the sub-problem.

20 . The computer-readable non-transitory storage medium of claim 15 , wherein each sub-problem of the one or more sub-problems is generated responsive to identifying a corresponding sub-schedule of the tentative solution of the principal problem, wherein a value of a chosen quality metric of the corresponding sub-schedule exceeds a predefined threshold value.