Assigning jobs to workers

Question

There are N plumbers, and M jobs for them to do, where M > N in general.

If N > M then it's time for layoffs! :)

Properties of a job:

1. Each job should be performed in a certain time window which can vary per-job.
2. Location of each job varies per-job.
3. Some jobs require special skill. Skills needed to complete the job can vary per-job
4. Some jobs have higher priority than others. The "reward" for some jobs is higher than others.

Properties of a plumber:

1. Plumbers have to drive from one job to the next which takes time. Say it's known what the travel time from each job to every other job site is.
2. Some plumbers have skills that others don't have.

The task is to find the optimal assignment of jobs to plumbers, so that the reward is maximized.

It's possible that not all jobs can be completed. For example, with one plumber and two jobs, it's possible that if they are doing job A, they can't do job B because there's not enough time to get from A to B once they are done with A and B is supposed to begin. In that case, optimal is to have the plumber do the job with the biggest reward and we are done.

I am thinking of a greedy algorithm that works like this:

sort jobs by reward
while true:
  for each job:
    find plumbers that could potentially handle this job
      make a note of the association, used in next loop
    if each plumber is associated with a different job, break
  for each job that can be handled by a plumber:
    assign job to a plumber:
      if more than one plumber can handle this job, break tie somehow:
        for instance if plumber A can do jobs X,Y but 
        plumber B can only do X, then give X to B.
        else just pick a plumber to take it
    remove assigned job from further consideration
  if no jobs got assigned:
    break out of "while true" loop 

My question: is there a better way? Seems like an NP-hard problem but I have no proof of that. :)

I guess it's similar to the Assignment Problem.

Seems it's a bit different though because of the space/time wrinkle: plumber could do either A or B, but not both because of the distance between them (can't get to B in time after finishing A). And jobs must be completed in certain time windows.

Also a plumber might not be able to take both jobs if they are too close in time (even if they are close in space). For example if B must be started before time_A_finished + time_to_travel_A_to_B, then B can't be done after A.

Thanks for any ideas! Any pointers on good stuff to read in this area is also appreciated.

Answer 1

Even routing just one plumber between jobs is as hard as the NP-hard traveling salesman problem.

I can suggest two general approaches for improving on your greedy algorithm. The first is local search. After obtaining a greedy solution, see if there are any small improvements to be made by assigning/reassigning/un-assigning a few jobs. Repeat until there are no obvious improvements or CPU time runs out.

Another approach is linear programming with column generation. This is more powerful but a lot more involved. The idea is to set up a master program where we try to capture as much reward as possible by choosing to use or not use every feasible plumber schedule, subject to the packing constraints of only doing a job once and not using more plumber skills than are available. At each stage of solving the master program, the dual values corresponding to jobs and plumbers reflect the opportunity cost of doing a particular job/using a particular plumber. The subproblem is figuring how out to route a plumber so as to capture more (adjusted) reward than the plumber "costs". This subproblem is NP-hard (per the note above), but it may be amenable itself to dynamic programming or further linear programming techniques depending on how many jobs there are. You'll quickly bump into the outer limits of academic operations research following this path.