Automatic solution to a scheduling problem

• US 10,430,739 B2
• Filed: 01/26/2016
• Issued: 10/01/2019
• Est. Priority Date: 01/26/2016
• Status: Active Grant

• Current Assignee: Workday Incorporated
• Original Assignee: International Business Machines Corporation
• Inventors: Katz, Michael, Lipets, Vladimir, Masin, Michael, Moshkovich, Dany, Wasserkrug, Segev E
• Primary Examiner(s): Singh, Gurkanwaljit
• Application Number:
  US15/006,133
• Publication Number:
  US 20170213181A1
• Time in Patent Office: 1,344 Days
• Field of Search: None
• CPC Class Codes: G05B 19/41865 characterised by job scheduling, process planning, material flow
• CPC Class Codes: G06F 2009/4557 Distribution of virtual machine instances; Migration and load balancing
• CPC Class Codes: G06F 9/455 Emulation; Interpretation; Software simulation, e.g. virtualisation or emulation of application or operating system execution engines
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues
• CPC Class Codes: G06N 3/006 based on simulated virtual individual or collective life forms, e.g. social simulations or particle swarm optimisation [PSO]
• CPC Class Codes: G06N 5/01 Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound
• CPC Class Codes: G06Q 10/063114 Status monitoring or status determination for a person or group
• CPC Class Codes: G06Q 10/063116 Schedule adjustment for a person or group
• CPC Class Codes: Y02P 90/02 Total factory control, e.g. smart factories, flexible manufacturing systems [FMS] or integrated manufacturing systems [IMS]

Abstract

A method comprising obtaining a scheduling problem comprising: a set of agents and a set of tasks to be performed by the set of agents, wherein solving the scheduling problem using an automated solver is not feasible using available predetermined resources. The method comprises automatically generating a plurality of alternative scheduling problems, wherein a solution to each such alternative scheduling problem defines a solution to the scheduling problem and determining a solution to the scheduling problem by applying the automated solver to solve, while using the available predetermined resources, an alternative problem of the plurality of alternative scheduling problems to determine a solution to the alternative problem and by mapping the solution to the alternative problem to the scheduling problem, whereby determining the solution.

Claims

1. A method comprising:

obtaining a scheduling problem comprising;

a set of agents and a set of tasks to be performed by the set of agents, wherein solving the scheduling problem using an automated solver is not feasible using available predetermined resources, and wherein the scheduling problem is defined in a planning domain description language;

automatically generating a plurality of alternative scheduling problems, wherein each alternate scheduling problem is created by providing additional restrictions to the scheduling problem, wherein a solution to each such alternative scheduling problem defines a solution to the scheduling problem, and wherein the additional restrictions comprise requiring a subset of the set of tasks to be performed by a same agent within the set of agents and restricting a subset of the set of agents that are capable of performing a task in the set of tasks to a smaller subset;

determining a solution to the scheduling problem by applying the automated solver to solve, while using the available predetermined resources, an alternative problem of the plurality of alternative scheduling problems to determine a solution to the alternative problem and by mapping the solution to the alternative problem to the scheduling problem, wherein the available predetermined resources comprise predetermined computation power and predetermined computation time, and the automated solver is a mixed-integer linear programming (MILP) solver; and

sending alerts to the set of agents based on the solution to the scheduling problem.

2. The method of claim 1, wherein said automatically generating comprises:

generating a modifications graph, wherein the modifications graph comprises nodes that represent scheduling problems and edges between a source node and a one or more target nodes, each such edge represents applying a modification to a scheduling problem represented by the source node to obtain an alternative scheduling problem that is represented by the one or more target nodes; and

wherein the modification graph is generated by initializing the modification graph to include a root node representing the scheduling problem and by iteratively applying one or more predetermined modifications on nodes of the modifications graph that do not have associated outgoing edges to generate the plurality of alternative scheduling problems, wherein for each generated alternative scheduling problem, a node is added to the modifications graph.

3. The method of claim 2, wherein said determining a solution comprises searching the modifications graph to determine a set of one or more alternative scheduling problems that are solvable by the solver using the available predetermined resources, solutions of the set of one or more alternative scheduling problems are mapped to the solution to the scheduling problem.

4. The method of claim 2, wherein the one or more predetermined modifications comprises:

a first modification that introduces a restriction to an original scheduling problem, whereby a solution of a modified scheduling problem is the solution to the original scheduling problem; and

a second modification that splits an original scheduling problem into two or more sub-problems, wherein each of the two or more sub-problems comprises a disjoint subset of the set of agents and a disjoint subset of the set of tasks, wherein each agent of the set of agents is comprised by exactly one disjoint subset of the set of agents, wherein each task of the set of tasks is comprised by exactly one disjoint subset of the set of tasks, whereby unifying two or more solutions to the sub-problems provides the solution to the original scheduling problem.

5. The method of claim 1, wherein said generating comprises:

determining a planning problem, wherein the planning problem comprises an initial state representing the scheduling problem and a description of a set of possible actions, wherein each possible action corresponding to a modification of a problem to a modified problem; and

utilizing an automated planner to determine a solution to the planning problem, the solution comprises a sequence of actions to modify the scheduling problem into the plurality of alternative scheduling problems, each of which can be solved independently by the automated solver using the available predetermined resources.

6. The method of claim 1, wherein the scheduling problem is a mobile workforce scheduling problem, wherein each agent of the set of agents is a mobile agent.

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

obtaining a scheduling problem comprising;

a set of agents and a set of tasks to be performed by the set of agents, wherein solving the scheduling problem using an automated solver is not feasible using available predetermined resources, and wherein the scheduling problem is defined in a planning domain description language;

automatically generating a plurality of alternative scheduling problems, wherein each alternate scheduling problem is created by providing additional restrictions to the scheduling problem, wherein a solution to each such alternative scheduling problem defines a solution to the scheduling problem, and wherein the additional restrictions comprise requiring a subset of the set of tasks to be performed by a same agent within the set of agents and restricting a subset of the set of agents that are capable of performing a task in the set of tasks to a smaller subset;

determining a solution to the scheduling problem by applying the automated solver to solve, while using the available predetermined resources, an alternative problem of the plurality of alternative scheduling problems to determine a solution to the alternative problem and by mapping the solution to the alternative problem to the scheduling problem, wherein the available predetermined resources comprise predetermined computation power and predetermined computation time, and the automated solver is a mixed-integer linear programming (MILP) solver; and

sending alerts to the set of agents based on the solution to the scheduling problem.

8. The computerized apparatus of claim 7, wherein said automatically generating comprises:

generating a modifications graph, wherein the modifications graph comprises nodes that represent scheduling problems and edges between a source node and a one or more target nodes, each such edge represents applying a modification to a scheduling problem represented by the source node to obtain an alternative scheduling problem that is represented by the one or more target nodes; and

wherein the modification graph is generated by initializing the modification graph to include a root node representing the scheduling problem and by iteratively applying one or more predetermined modifications on nodes of the modifications graph that do not have associated outgoing edges to generate the plurality of alternative scheduling problems, wherein for each generated alternative scheduling problem, a node is added to the modifications graph.

9. The computerized apparatus of claim 8, wherein said determining a solution comprises searching the modifications graph to determine a set of one or more alternative scheduling problems that are solvable by the solver using the available predetermined resources, solutions of the set of one or more alternative scheduling problems are mapped to the solution to the scheduling problem.

10. The computerized apparatus of claim 8, wherein the one or more predetermined modifications comprises:

a first modification that introduces a restriction to an original scheduling problem, whereby a solution of a modified scheduling problem is the solution to the original scheduling problem; and

a second modification that splits an original scheduling problem into two or more sub-problems, wherein each of the two or more sub-problems comprises a disjoint subset of the set of agents and a disjoint subset of the set of tasks, wherein each agent of the set of agents is comprised by exactly one disjoint subset of the set of agents, wherein each task of the set of tasks is comprised by exactly one disjoint subset of the set of tasks, whereby unifying two or more solutions to the sub-problems provides the solution to the original scheduling problem.

11. The computerized apparatus of claim 7, wherein said generating comprises:

determining a planning problem, wherein the planning problem comprises an initial state representing the scheduling problem and a description of a set of possible actions, wherein each possible action corresponding to a modification of a problem to a modified problem; and

utilizing an automated planner to determine a solution to the planning problem, the solution comprises a sequence of actions to modify the scheduling problem into the plurality of alternative scheduling problems, each of which can be solved independently by the automated solver using the available predetermined resources.

12. The computerized apparatus of claim 7, wherein the scheduling problem is a mobile workforce scheduling problem, wherein each agent of the set of agents is a mobile agent.

13. 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 a scheduling problem comprising;

a set of agents and a set of tasks to be performed by the set of agents, wherein solving the scheduling problem using an automated solver is not feasible using available predetermined resources, and wherein the scheduling problem is defined in a planning domain description language;

automatically generating a plurality of alternative scheduling problems, wherein each alternate scheduling problem is created by providing additional restrictions to the scheduling problem, wherein a solution to each such alternative scheduling problem defines a solution to the scheduling problem, and wherein the additional restrictions comprise requiring a subset of the set of tasks to be performed by a same agent within the set of agents and restricting a subset of the set of agents that are capable of performing a task in the set of tasks to a smaller subset;

determining a solution to the scheduling problem by applying the automated solver to solve, while using the available predetermined resources, an alternative problem of the plurality of alternative scheduling problems to determine a solution to the alternative problem and by mapping the solution to the alternative problem to the scheduling problem, wherein the available predetermined resources comprise predetermined computation power and predetermined computation time, and the automated solver is a mixed-integer linear programming (MILP) solver; and

sending alerts to the set of agents based on the solution to the scheduling problem.