SPATIO-TEMPORAL APPROACH TO SCHEDULING FIELD OPERATIONS

• US 20140278654A1
• Filed: 03/15/2013
• Published: 09/18/2014
• Est. Priority Date: 03/15/2013
• Status: Active Grant

• Current Assignee: Utopus Insights, Inc. (Vestas Wind Systems A/S)
• Original Assignee: International Business Machines Corporation
• Inventors: Kumar, Tarun, Mahatma, Shilpa N., Candas, Mehmet F., Hampapur, Arun
• Granted Patent: US 11,880,790 B2
• Time in Patent Office: Days
• US Class Current: 705/7.17
• CPC Class Codes: G06Q 10/047 Optimisation of routes or paths, e.g. travelling salesman problem
• CPC Class Codes: G06Q 10/06313 Resource planning in a project environment

Abstract

A method for creating a spatio-temporal schedule includes receiving a set of available work crews and a set of workorders to be scheduled, sequencing the set of workorders, wherein each workorder of the set of workorders is associated with a geographic location, a start time and an end time, and iterating through the set of available work crews, assigning a plurality of workorders of the set of workorders fully allocating a current crew before selecting a next crew, until all work crews are fully allocated and/or all workorders are assigned, wherein the assignment of workorders for a given work crew generates a route comprising the plurality of workorders.

Claims

1. A method for creating a spatio-temporal schedule comprising:

receiving a set of available work crews and a set of workorders to be scheduled;

sequencing the set of workorders, wherein each workorder of the set of workorders is associated with a geographic location, a start time and an end time; and

iterating through the set of available work crews, assigning a plurality of workorders of the set of workorders fully allocating a current crew before selecting a next crew, until at least one of all work crews are fully allocated and all workorders are assigned, wherein the assignment of workorders for a given work crew generates a route comprising the plurality of workorders.

2. The method of claim 1, wherein sequencing the set of workorders comprises maximizing a objective given a super-crew and the set of workorders.

3. The method of claim 2, wherein the maximization of the objective is determined as a maximum sum of priorities of the set of workorders subject to at least one constraint.

4. The method of claim 2, wherein the maximization of the objective is determined as a maximization of a number of workorders that can be assigned to the super-crew subject to at least one constraint.

5. The method of claim 2, wherein the maximization of the objective is subject to at least constraint, and the constraint specifies at least one of, that no overlap in time exist between two of the set of workorders for the super-crew, that travel times for the super-crew are accounted for, that the super-crew starts from a certain geographic location, that the super-crew ends at the certain geographic location, that there are no straggler workorders, and that the super-crew starts from a farthest workorder.

6. The method of claim 1, the route for the given work crew is generated by minimizing a sum of maximum end times of the set of workorders.

7. The method of claim 6, wherein the minimization of the sum of maximum end times of the set of workorders is subject to at least one constraint.

8. The method of claim 7, wherein the constraint includes at least one of minimizing a sum of maximum end time of the set of workorders, all tasks must be scheduled, and work crew capacity, work crew availability.

9. A method for creating a spatio-temporal schedule comprising:

generating a sequence of workorders satisfying an objective, wherein each workorder of the set of workorders is associated with a geographic location, a start time and an end time; and

assigning sequential sets of the workorders to respective work crews of a plurality of work crews, wherein an assignment of a sequential set of the workorders to a respective work crew corresponds to a geographic route.

10. The method of claim 9 wherein the assignment of the sequential sets of workorders fully allocates each successive work crew until all workorders have been assigned.

11. The method of claim 9, wherein generating the sequence of workorders comprises maximizing a objective given a super-crew and the set of workorders.

12. The method of claim 11, wherein the maximization of the objective is determined as a maximum sum of priorities of the sequence of workorders subject to at least one constraint.

13. The method of claim 11, wherein the maximization of the objective is determined as a maximization of a number of workorders that can be assigned to a super-crew subject to at least one constraint.

14. The method of claim 11, wherein the maximization of the objective is subject to at least one constraint, and the constraint specifies at least one of, that no overlap in time exist between two of the sequences of workorders for a super-crew, that travel times for the super-crew are accounted for, that the super-crew starts from a certain geographic location, that the super-crew ends at the certain geographic location, that there are no straggler workorders, and that the super-crew starts from a farthest workorder.

15. The method of claim 9, the geographic route for the respective work crew is generated by minimizing a sum of maximum end times of the sequence of workorders.

16. The method of claim 15, wherein the minimization of the sum of maximum end times of the sequence of workorders is subject to at least one constraint.

17. The method of claim 16, wherein the constraint includes at least one of minimizing a sum of maximum end time of the sequence of workorders, all tasks must be scheduled, and work crew capacity, work crew availability.

18. A computer program product for creating a spatio-temporal schedule, the computer program product comprising:

a computer readable storage medium having computer readable program code embodied therewith, the computer readable program code comprising;

computer readable program code configured to receive a set of available work crews and a set of workorders to be scheduled;

computer readable program code configured to sequence the set of workorders, wherein each workorder of the set of workorders is associated with a geographic location, a start time and an end time; and

computer readable program code configured to iterate through the set of available work crews, assigning a plurality of workorders of the set of workorders fully allocating a current crew before selecting a next crew, until at least one of all work crews are fully allocated and all workorders are assigned, wherein the assignment of workorders for a given work crew generates a route comprising the plurality of workorders.

19. The computer program product of claim 18, wherein sequencing the set of workorders comprises maximizing a objective given a super-crew and the set of workorders.

20. The computer program product of claim 19, wherein the maximization of the objective is determined as a maximum sum of priorities of the set of workorders subject to at least one constraint.

21. The computer program product of claim 19, wherein the maximization of the objective is determined as a maximization of a number of workorders that can be assigned to the super-crew subject to at least one constraint.

22. The computer program product of claim 19, wherein the maximization of the objective is subject to at least constraint, and the constraint specifies at least one of, that no overlap in time exist between two of the set of workorders for the super-crew, that travel times for the super-crew are accounted for, that the super-crew starts from a certain geographic location, that the super-crew ends at the certain geographic location, that there are no straggler workorders, and that the super-crew starts from a farthest workorder.

23. The computer program product of claim 18, the route for the given work crew is generated by minimizing a sum of maximum end times of the set of workorders.

24. The computer program product of claim 23, wherein the minimization of the sum of maximum end times of the set of workorders is subject to at least one constraint.

25. The computer program product of claim 24, wherein the constraint includes at least one of minimizing a sum of maximum end time of the set of workorders, all tasks must be scheduled, and work crew capacity, work crew availability.