Decomposition of multisite heterogeneous workforce scheduling problems

A computerized apparatus having a processor, the processor being adapted to perform the steps of:

• obtaining an instance of a multisite heterogeneous workforce scheduling problem comprising a set of work items and a set of technicians;
• calculating a measure of likelihood that a pair of work items belong to the same sub-problem in a decomposition of the problem instance into a plurality of sub-problems such that a union of solutions to the plurality of sub-problems is a solution to the problem, said calculating comprises calculating one or more components indicating a relation between the pair of work items and technicians potentially scheduled to execute either of them;
• and
• generating a solution to the problem by solving the plurality of sub-problems in the decomposition obtained based on a partitioning of the set of work items induced by the measure and aggregating solutions to the plurality of sub-problems.

The computerized apparatus of claim 13, wherein the relation is based on one or more spatiotemporal parameters associated with each of the work items selected from the group consisting of:

• location;
• estimated duration;
• time frame during which the work item is to be executed;
• or any combination thereof.

A computer program product comprising a non-transitory computer readable storage medium retaining program instructions, which program instructions when read by a processor, cause the processor to perform a method comprising:

• obtaining an instance of a multisite heterogeneous workforce scheduling problem comprising a set of work items and a set of technicians;
• calculating a measure of likelihood that a pair of work items belong to the same sub-problem in a decomposition of the problem instance into a plurality of sub-problems such that a union of solutions to the plurality of sub-problems is a solution to the problem, said calculating comprises calculating one or more components indicating a relation between the pair of work items and technicians potentially scheduled to execute either of them;
• and
• generating a solution to the problem by solving the plurality of sub-problems in the decomposition obtained based on a partitioning of the set of work items induced by the measure and aggregating solutions to the plurality of sub-problems.