1
$\begingroup$

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$

$\endgroup$
8
  • $\begingroup$ Yes, Set Cover looks to be the way to go: each worker is represented by the set of abilities they have, and if there is a set cover of size at most your slot count then you have a feasible solution. Side note: there seems to be no material distinction between "skill" and "ability". $\endgroup$ Dec 19, 2016 at 14:23
  • $\begingroup$ Yes they are similar in common concept. But "skill" and "ability" in this specific application are two sets of factors to account for, separately. 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 stuffs like photoshop. $\endgroup$ Dec 19, 2016 at 14:49
  • $\begingroup$ Exact cover looks like a reasonable way to go if there aren't too many valid combinations of workers that can be assigned to each job. For instance, if there are one billion valid subsets of workers that could be assigned to job 1 to meet its requirements, then exact cover is going to have to deal with an input containing one billion sets, and it'll probably be very slow. (Cc: @j_random_hacker) $\endgroup$
    – D.W.
    Dec 19, 2016 at 15:14
  • $\begingroup$ @JackeyCheung: My point is that, from the program's point of view, a what you call a "skill" and what you call an "ability" are just properties that a worker either must have, or should preferably have, with how preferable it is to have that property measured being measured by a numeric score. So, IIUC, if you were to rename all your current "skills" to "abilities" or vice versa, nothing would need to change in the program except for some printf()s or GUI labels. In that case it only complicates matters (for readers like me) to distinguish these things. $\endgroup$ Dec 19, 2016 at 15:23
  • $\begingroup$ @D.W. We've just have a few hundred workers & a few dozen jobs, I think it's ok to assume that the valid combination of a job won't be big number. $\endgroup$ Dec 19, 2016 at 15:33

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Thanks for the suggestion. This seems to be a Job-shop scheduling approach, worker as machine and skill as requirements. Doing so would end up making a complete job assignment plan, right? $\endgroup$ Dec 19, 2016 at 8:13
  • $\begingroup$ btw, i've updated the question according to your answer $\endgroup$ Dec 19, 2016 at 8:15
  • $\begingroup$ There is some resemblance to job-shop scheduling, but I think it's different. Your problem is partly easier: here each day you assign workers to some jobs, and each day is separate/independent (you don't have to worry about a requirement that it will take a worker 2 days to complete the job and so they must be assigned to the job on 2 consecutive dates). Your problem is also partly harder: in job-shop scheduling a job is assigned to a multiple machine at a time; in your problem, we can/must assign multiple workers to the same job simultaneously. I edited my answer to address the "slots". $\endgroup$
    – D.W.
    Dec 19, 2016 at 15:11
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.