Selecting best crew combination that meets requirements of a variety of jobs

Question

I am developing an application, which performs combinatorial function as described below. Could anyone point out a suitable algorithm (or direction)?

== Basic scheme: ==

There are fixed amount of slots (say air tickets), a few hundreds of workers, and a few dozens of jobs. Every time, a bunch of workers (the "crew") are sent to complete jobs. The number of workers sent are determined by the available slots. The crew must finish all appointed jobs by themselves.

Each job requires a combination of skills that were possessed by workers. Besides skills, some jobs may optionally require the worker to possess certain ability. Further, some of those jobs with ability requirements imposed as must-have.

Example:

1. A worker, possesses the skill "software engineering", but lacks "maths" ability;
2. There are 3 jobs that require "software engineering" skill;
3. Job A is a simple programming job;
4. Job B is a programming job involves basic "maths" processing, but since it's basic processing, "maths" ability is optional;
5. Job C is a programming job involves advance "maths" processing, so the "maths" ability is a must.

We say:

1. The worker fulfills Job A.
2. The worker fulfills Job B, but not the best candidate. Any worker possess "software engineering" skill and "maths" ability is better candidate to the job;
3. The worker cannot fulfill Job C, due to lack of "maths" ability.

On the server, calculation is done every night (or twice daily), to find out the best combination of workers to sent out:

1. Can finish all jobs;
2. No more than the available slots;
3. (Optional) With least head count.
4. (Optional) A crew list with highest rating;
5. (Optional) Best score to head count ratio;
6. (Optional) The algorithm should be portable to mobile platform.

== Update 2 ==

TL;DR;

The available slots is a constraint (relatively speaking, a constant), which confines the crew size we can sent out. After receiving a contract, the number of workers we'll be sending out is determined, hence the slot constraint. Theoretically, sending out less worker would be more profitable, and exceeding that may be an out-of-budget alarm.

The words "skill" and "ability" are similar in common concept. But they are two sets of factors to account for in this specific application, separately. These two words are actually come from the up-stream system, which generates the base data set. Maybe it's better put them as: "skill" could be accountants, programmers, etc. While "ability" could be "maths" as accountant & programmers both could possess maths ability; or "graphic" could be an ability of programmer who is making computer software like photo editors. These are well defined in the up-stream system.

While working on the program, before reaching this "combinatorial" portion, we have done some extra work on job & worker classifications. During job & worker classification, a few information is calculated and stored, and will be transferred to mobile device:

1. Lists of suitable worker to each job are generated, and attached to job records;
2. Each worker is given a "score", which is:
   • the total number of jobs he/she can finish;
   • plus the total number of jobs with optional ability requirements he/she can finish;
   • plus the total number of jobs with must-have ability requirements he/she can finish.

At the time of computation, no worker is actually occupied. The contract consists of various jobs, unique and/or repetitive. How to assign workers to jobs is left to the on-site manager's decision. So any worker could be assigned multiple jobs during the contract period, and is out of this application's scope. We just provide a team of workers that is capable of finishing all jobs.

== Update ==

I'm planning to do this the "brute force" way on the server, due to its limited probabilities. However, this process will be moved to mobile (phones, etc.) platforms eventually, since worker availability may change in reality. It seems performing such computation on mobile platform is not feasible.

It seems to me not a knack-sack problem, nor a linear problem. I can't find a way to place variable worker & job constraints to the formulas.

With this question, I'm hoping to have some better options that can come out with the result with as few iterations as possible.

---

So, as we enter this function, there will be a few constants & variables:

let $U$ to be all of our available workers;

let $Z$ to be the constant of the maximum crew size (slot);

let $V_{w}$ to be the score of each worker, could be used as weight;

let $L_{j}$ to be the list of suitable workers to a job, which in turn are subsets of our available workers, where $L_{j} \in U$

Answer 1

One strategy would be to formulate this as a mixed integer linear programming problem, and solve it with an off-the-shelf ILP solver.

You can create a zero-or-one variable $x_{i,j}$ that indicates whether worker $i$ is assigned to job $j$. The requirement that job $j$ requires at least one worker with some skill can be expressed as the linear inequality $\sum_{i \in S} x_{i,j} \ge 1$ where $S$ is the set of workers with that skill. If the job requires multiple skills, then you can add multiple linear inequalities. Also, add the inequalities $\sum_j x_{i,j} \le 1$ (each worker is assigned to at most one job). You can minimize the head count by minimizing $h = \sum_{i,j} x_{i,j}$. You can take into account the "slots" constraint like this: if you want to send at most $m_j$ people to job $j$, then add the inequality $\sum_i x_{i,j} \le m_j$. Then, feed this entire linear program to an off-the-shelf ILP solver.

If you want to search for a solution with the best score to head count ratio, you can use the following technique. Let $s$ denote the total score; note that this is a linear function of the $x_{i,j}$'s, namely $s = \sum_{i,j} s_i x_{i,j}$ where $s_i$ represent worker $i$'s score. Let $r$ denote the score to head count ratio you want to achieve; let's treat $r$ as a constant, and our goal is to see whether ratio $r$ is achievable. Then we can add the linear inequality $s \ge hr$ and see whether the resulting linear program is solvable, and then either increase or decrease $r$ accordingly. Finally, use binary search on $r$ to find the largest ratio $r$ such that the resulting linear program is feasible.

While ILP is intractable in general (in the worst case), for the size of problem you have, it's possible that existing ILP solvers might be able to find reasonably good solutions. At least, I expect this will be superior to brute force.

I don't really understand twhat is meant by the rating of a crew, so you'll have to figure out whether that can be represented them in an ILP -- I don't know how to help you there.

Your problem is related to the assignment problem, but with additional restrictions, so I don't expect the literature on that problem to necessarily be of any assistance to you.

Answer 2

UPDATE

I haven't figured out other options to this problem. So I've broken up the process to offline mobile computations.

First, I've done everything on the server. Calculating all fundamental statistics, and work out a basic solution to the allocation.

Then all those results are pushed to mobile devices. When the basic solution doesn't fit the final requirement, mobile devices use the stats data from server to work out a final solution.

** Original **

Please allow me to address the set cover problem approach in a new answer, so the question won't introduce more confusions. I would update this answer as I venture through this path.

And first, I have to explain myself a bit more. I've deserted maths for a decade more (not intentionally though). So my maths ability drops to every-day-maths capable. I'm picking stuffs up as I progress.

It seems I have made a wrong choice regarding $L_{j}$. As my goal is to select crew that can fulfill all jobs, $L_{j}$ won't help here. Instead list of doable jobs per worker should be the one to get.

$U \leftarrow$ all jobs

$W \leftarrow$ all workers

$L_w \leftarrow$ jobs can be done by worker $w$ (where $w \in W$ and $L_w \in U$)

Grep the set cover ILP from wiki: $$ \mathrm{minimize} \sum_{j \in L_w} x_j $$

for all $e \in U$ $$ \sum_{j_{:e} \in L_w} x_j \ge 1 $$

for all $j \in L_w$ $$ x_j \in \{0,1\} $$

now we have the combination of workers (first part solved), correct?

---

Below stuffs were turned out unused.

$Z \leftarrow$ slots

$n_u = |U|$

$u_j \in U$ (where $1 \le j \le n_u$)

$n_w = |W|$

$w_i \in W$ (where $1 \le i \le n_w$)

$S \leftarrow$ all skills & abilities

$s_j \leftarrow$ job $j$ skills, $s_j \in S$ (where $1 \le j \le n_u$)

$S' \in S$ (all skills used in jobs) where: $$ S' = \bigcup_{j=1}^{n_u} s_j $$

$s_i \leftarrow$ worker $i$ skills, $s_i \in S' \in S$ (where $1 \le i \le n_w$)

$L_j \leftarrow$ suitable workers to job $j$ (where $j \in U$)

$v_i \leftarrow$ worker $i$ score