Dispatching prioritized jobs at multiple locations to workers

• US 8,799,046 B2
• Filed: 12/27/2006
• Issued: 08/05/2014
• Est. Priority Date: 12/27/2006
• Status: Active Grant

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Inventors: Schneur, Rina R., Tobin, Roger Lee, Sivaraman, Raghavendran
• Primary Examiner(s): FEENEY, BRETT A
• Application Number:
  US11/616,634
• Publication Number:
  US 20080162242A1
• Time in Patent Office: 2,778 Days
• US Class Current: 705/7.17
• CPC Class Codes: G06Q 10/06 Resources, workflows, human or project management; Enterprise or organisation planning; Enterprise or organisation modelling
• CPC Class Codes: G06Q 10/0631 Resource planning, allocation, distributing or scheduling for enterprises or organisations
• CPC Class Codes: G06Q 10/06311 Scheduling, planning or task assignment for a person or group
• CPC Class Codes: G06Q 10/063112 Skill-based matching of a person or a group to a task
• CPC Class Codes: G06Q 10/063118 Staff planning in a project environment
• CPC Class Codes: G06Q 10/06316 Sequencing of tasks or work
• CPC Class Codes: G06Q 10/1097 Task assignment

Abstract

A system, method and computer program product are provided for assigning prioritized jobs at multiple locations to workers with the objective of maximizing the number of higher priority jobs assigned, with secondary objectives of minimizing worker travel time between locations and of balancing workload across workers. In doing so, the system, method and computer program product consider job data including job location, skills required, time required and additional job constraints, as well as resource data including worker location, worker skills, worker time constraints and additional worker constraints. The system, method and computer program product also consider travel time between various pairs of job locations and worker locations in order to optimize work assignments while minimizing travel time.

Claims

1. A system comprising:

at least one database configured to store job data and resource data, wherein said job data comprises data for a plurality of jobs including a priority level, skills required and a job location for each of said plurality of jobs, and wherein said resource data comprises data for a plurality of workers including skills and a resource location for each of said plurality of workers, a maximum number of locations that each worker of said plurality of workers can visit within a predefined period of time, and a number of available workers of said plurality of workers; and

an optimization engine configured to;

select jobs having a first priority level and determine a first maximum number of jobs that can be filled by said plurality of workers at said first priority level, wherein the first maximum number of jobs is determined based at least in part on minimizing;

in which t is a set of available workers, j is a set of the plurality of jobs of the first priority level, and x_tj is a decision variable that is assigned a value of 1 if job j is assigned to worker t and is 0 otherwise;

optimize assignment of one or more of said plurality of workers to specific ones of said first priority jobs, said specific first priority jobs totaling said first maximum number of jobs, and

concurrently with said optimized assignment, perform at least one of;

minimizing total travel time between respective resource locations of said one or more workers and job locations associated with said specific first priority jobs;

or

ensuring that each of said one or more assigned workers is assigned approximately the same amount of work.

2. The system of claim 1, wherein:

said optimization engine is further configured to;

select jobs having a second priority level and determine a second maximum number of jobs that can be filled by said plurality of workers at said second priority level, wherein the second maximum number of jobs is determined based at least in part on minimizing;

in which t is a set of available workers, j is a set of the plurality of jobs of the second priority level, and x_tj is a decision variable that is assigned a value of 1 if job j is assigned to worker t and is 0 otherwise, while maintaining said first maximum number of jobs; and

optimize assignment of one or more of said plurality of workers to specific ones of said second priority jobs, said specific second priority jobs totaling said second maximum number of jobs.

3. The system of claim 2, wherein:

said optimization engine is further configured to;

select jobs having a third priority level and determine a third maximum number of jobs that can be filled by said plurality of workers at said third priority level, wherein the third maximum number of jobs is determined based at least in part on minimizing;

in which t is a set of available workers, j is a set of the plurality of jobs of the third priority level, and x_tj is a decision variable that is assigned a value of 1 if job j is assigned to worker t and is 0 otherwise, while maintaining said first and second maximum number of jobs; and

optimize assignment of one or more of said plurality of workers to specific ones of said third priority jobs, said specific third priority jobs totaling said third maximum number of jobs.

4. The system of claim 1, wherein:

said resource data further comprises sets of workers, wherein each set defines a group of workers having substantially similar skills; and

ensuring that each of said one or more assigned workers is assigned approximately the same amount of work comprises ensuring that each worker within a respective set of workers is assigned approximately the same amount of work as other workers within said set.

5. The system of claim 4, wherein said amount of work is measured in increments of time.

6. The system of claim 1, wherein said optimization engine is further configured to compile said assignments into a schedule and present said schedule to a user via a computing device.

7. The system of claim 1, wherein said optimization engine comprises:

a travel-time module in communication with said assignment module, said travel-time module being configured to;

determine job locations corresponding to said first priority jobs and resource locations for said plurality of workers; and

determine a travel time between each first priority job location and each resource location; and

wherein said optimization engine is configured to receive said travel time from said travel-time module in order to minimize said total travel time.

8. The system of claim 1, wherein:

if job j cannot be done by the worker t x_tj=0;

each job j can be done by at most one worker

Σ

x_tj≦

1;

the worker can do job j only if they visits the location l of the job, x_tj≦

v_tl wherein v_tl is a decision variable that takes the value 1 if worker t visits location l, but is 0 otherwise;

the worker t visits a location l only if they travels to that location

Σ

r_tlm=v_tl

Σ

r_tml=v_tl

wherein m is a set of all locations, r_tlm is a decision variable that describes a route that the worker t takes and that takes the value 1 if the worker travels from origin location 1 to destination location m, but is 0 otherwise;

the worker t visits the location b she starts out of v_tb=1;

for every priority class i higher that k, n[i] number of jobs must be assigned

9. A method comprised of:

providing access to job data comprising a priority level, skills required and a job location for each of a plurality of jobs;

providing access to resource data comprising skills, a resource location for each of a plurality of workers, a maximum number of locations that each worker of said plurality of workers can visit within a predefined period of time, and a number of available workers of said plurality of workers;

determining via an optimization engine a first maximum number of jobs of a first priority level that can be assigned to one or more of said plurality of workers, said determination being made by assigning a decision variable x_tj a value of 1 when job j of the plurality of jobs of the first priority level is assigned to worker t of the available workers and a value of 0 otherwise for each of the plurality of jobs of the first priority level and available workers and minimizing a summation of x_tj for each of jobs j and workers t; and

generating assignments via the optimization engine of said one or more workers to specific ones of said plurality of jobs, said specific jobs totaling said first maximum number of jobs, and said assignment generation being constrained to assign said one or more workers while minimizing total travel time between the resource locations of assigned workers and respective assigned job locations.

10. The method of claim 9, further comprising:

determining a second maximum number of jobs of a second priority level that can be assigned to one or more of said plurality of workers by assigning a decision variable x_tj a value of 1 when job j of the plurality of jobs of the second priority level is assigned to worker t of the available workers and a value of 0 otherwise for each of the plurality of jobs of the second priority level and available workers and minimizing a summation of x_tj for each of jobs j and workers t, wherein said first maximum number of jobs is maintained when determining said second maximum number of jobs; and

wherein said job assignments generated total said first maximum number of jobs and said second maximum number of jobs.

11. The method of claim 10, further comprising:

determining a third maximum number of jobs of a third priority level that can be assigned to one or more of said plurality of workers by assigning a decision variable x_tj a value of 1 when job j of the plurality of jobs of the third priority level is assigned to worker t of the available workers and a value of 0 otherwise for each of the plurality of jobs of the third priority level and available workers and minimizing a summation of x_tj for each of jobs j and workers t, wherein said first and second maximum number of jobs are maintained when determining said third maximum number of jobs; and

wherein said job assignments generated total said first maximum number of jobs, said second maximum number of jobs and said third maximum number of job.

12. The method of claim 10, wherein said second priority level designates jobs of less importance than jobs at said first priority level.

13. The method of claim 9, wherein:

providing access to said job data further comprises providing access to a respective average time required to perform each of said plurality of jobs;

providing access to said resource data comprises providing access to a respective time constraint for each of said plurality of workers; and

said determination of said first maximum number of jobs is based further on said average time required to perform said plurality of jobs and said time constraint of said plurality of workers.

14. The method of claim 9, wherein:

providing access to said resource data further comprises providing access to designated sets of workers, wherein each set defines a group of workers having substantially similar skills; and

said assignment generation is further constrained to assign said one or more workers to said first priority jobs while ensuring that each worker within a respective set of workers is assigned approximately the same amount of work as other workers within said respective set.

15. The method of claim 9, further comprising:

compiling said generated assignments into a schedule; and

presenting said schedule to a user.

16. The method of claim 9, further comprising:

providing access to a respective travel time between each job location of said plurality of jobs and each resource location of said plurality of workers; and

generating said assignments based in part on said stored travel times.

17. A computer program product comprising:

a non-transitory computer readable memory having computer readable code embodied therein, for execution by a computing device having at least a processor and a memory, said code comprising;

a first executable code portion configured to provide access to job data comprising a priority level, skills required and a job location for each of a plurality of jobs;

a second executable code portion configured to provide access to resource data comprising skills, a resource location for each of a plurality of workers, a maximum number of locations that each worker of said plurality of workers can visit within a predefined period of time, and a number of available workers of said plurality of workers;

a third executable code portion configured to determine a first maximum number of jobs of a first priority level that can be assigned to one or more of said plurality of workers, said determination being made based at least in part on minimizing;

in which t is a set of available workers, j is a set of the plurality of jobs of the first priority level, and x_tj is a decision variable that is assigned a value of 1 if job j is assigned to worker t and is 0 otherwise;

a fourth executable code portion configured to generate assignments of said one or more workers to specific ones of said plurality of jobs, said specific jobs totaling said first maximum number of jobs, and said assignment optimization being constrained to assign said one or more workers while minimizing total travel time between the resource locations of assigned workers and respective assigned job locations.

18. The computer program product of claim 17, the code further comprising:

a fifth executable code portion configured to determine a second maximum number of jobs of a second priority level that can be assigned to one or more of said plurality of workers, wherein the second maximum number of jobs is determined based at least in part on minimizing;

in which t is a set of available workers, j is a set of the plurality of jobs of the second priority level, and x_tj is a decision variable that is assigned a value of 1 if job j is assigned to worker t and is 0 otherwise, wherein said first maximum number of is maintained when determining said second maximum number of jobs, and wherein the fifth executable code portion is executable prior to said fourth executable code portion; and

wherein said specific jobs assigned by said fourth executable code portion total said first maximum number of jobs and said second maximum number of jobs.

19. The computer program product of claim 18, the code further comprising:

a sixth executable code portion configured to determine a third maximum number of jobs of a third priority level that can be assigned to one or more of said plurality of workers, wherein the third maximum number of jobs is determined based at least in part on minimizing;

in which t is a set of available workers, j is a set of the plurality of jobs of the third priority level, and x_tj is a decision variable that is assigned a value of 1 if job j is assigned to worker t and is 0 otherwise, wherein said first and second maximum numbers of jobs are maintained when determining said third maximum number of jobs, and wherein said sixth executable code portion is also executable prior to said fourth executable code portion; and

wherein said specific jobs assigned by said fourth executable code portion total said first maximum number of jobs, said second maximum number of jobs and said third maximum number of jobs.

20. The computer program product of claim 18, wherein said second priority level designates jobs of less importance than jobs of said first priority level.

21. The computer program product of claim 17, wherein:

said first executable code portion is further configured to provide access to a respective average time required to perform each of said plurality of jobs;

said second executable code portion is further configured to provide access to a respective time constraint for each of said one or more workers; and

said third executable code portion is further configured to determine said first maximum number of jobs further based on said average time required to perform said one or more jobs and said time constraint of said one or more workers.

22. The computer program product of claim 17, wherein:

said second executable code portion is further configured to provide access to designated sets of workers, wherein each set defines a group of workers having substantially similar skills; and

said fourth executable code portion is further constrained to assign said one or more workers to said first priority jobs while ensuring that each worker within a respective set of workers is assigned approximately the same amount of work as other workers within said respective set.

23. The computer program product of claim 17, the code further comprising:

a fifth executable code portion configured to compile said generated assignments into a schedule; and

a sixth executable code portion configured to present said schedule to a user via a computing device.

24. The computer program product of claim 17, the code further comprising:

a fifth executable code portion configured to provide access to a respective travel time between each job location of said plurality of jobs and each resource location of said plurality of workers; and

wherein said fourth executable code portion is configured to generate said assignments based in part on said stored travel times.