What is a good algorithm for priority allocation of work duties?

Question

I am currently doing a project (in PHP) that has the following requirements:

1. There is a list of people, sorted in a certain priority. Work should be allocated to them by this priority. e.g. If the list is T1, T2, T3, T1 should be allocated work, before T2. And T2 is allocated work before T3. In the event that are only 2 pieces of work, only T1 and T2 are allocated.
2. Each piece of work has certain time requirements. So even if it is T1's turn to be allocated work, if none of the work is suitable for T1, T1 will be skipped and no work will be assigned to T1.
3. Some work is more suitable for some people. E.g. There are two work, W1 and W2. If T1 is more suitable for W2, W2 will be assigned to T1.

My current idea is to allocate work based on the people list, and use a A* Search to identify what is the best way to allocate the work to each person. But I thought that my reqt 1 and reqt 3 seems to have some conflicts.

Is this a sensible algorithm or are there problems with it that I don't see at this point?

Answer 1

The problem you have here in general is called the Scheduling Problem and in its general form is NP-complete. In other words, it is a well-known problem for which there exists no efficient algorithm (yet, or maybe never).

The linked page (already mentioned in a comment before) refers to one specific variant called job shop scheduling. There are many different scheduling problems, which all come down to be NP-complete in some way.

In your case, however, I would seriously rethink about the need to have priorities. Job scheduling problems usually have hard dependencies (like job A needs to be finished for job B to be able to start). Priorities are a whole different problem dimension and will complicate your task tremendously - something which may not be worth it. It is hard enough, if you simply say that task T1 can only be performed by workers W1 or W2 - without the need to prefer W1.

One note if you check the literature: what in your case are workers are typically machines in the literature - think automation factories where T1,...,Tn tiles are produced by M1,...,Mm machines.

Also one of the first things to check is if you need to find the perfect solution at all. Generally, NP-completeness stems from the requirement that the best solution has to be found. In your description you write things like T1 will be skipped, which is normally not possible in the theoretical scheduling problem formulations. Given that you have no need to schedule all tasks, you may also not have a requirement to solve the problem optimally. In that case, you can either try to write a Greedy-like algorithm yourself or look at the research being done on approximation algorithms for scheduling. These algorithms have the advantage of being fast, but the disadvantage of not necessarily finding an optimal solution.

Answer 2

I would model this as a Constraint Satisfaction Problem where your goal is to find a configuration of assignments that fulfills your requirements. This is generally an NP-complete problem, but depending on the size of your data set it could be possible to find a solution.

Here's a description of how to go about solving that problem with a Backtracking-style algorithm

• Let W be a set of work assignments such as { W1, W2, ..., Wn }
• For every assignment, assign the worker most suitable to it (as per requirement 2)
• For all remaining assignments, attempt to schedule it to the highest priority available worker
• Continue to the next unassigned assignment until they are all assigned or until no workers are available at that time
• If no solution was found, go back one step and try again with the next available worker

It's very similar to how Sudoku grids are solved, which are often modeled as CSPs themselves. This is only possible because assignments are not prerequisites to each other according to your description, which makes it less relevant to model the problem as a scheduling problem.

Good luck!