0
$\begingroup$

I originally posted the problem in stackoverflow but later on it become clear that it is more of a math problems then coding.

Example:

We have company doing support work on 3 projects (P1, P2, P3); In the company there are 4 workers (w1,w2,w3,w4) and each of them got some special preferences described below.

On Monday morning the company receives the following tasks for the day:
P3: tasks for 16 man-hours* , with dead-line=13:00.
P2: tasks for 16 man-hours* , with dead-line=17:00.
P1: tasks for 30 man-hours* , NO dead-line (as much as you can make).

Lets say the working schedule of all(see w2) workers is 08:00-12:00, 13:00-17:00.
w1: can work on P1, P2;
w2: can work on P1, P2, P3, but works will work only 4 hours today (08:00-12:00);
w3: can work on P1, P2, P3, and has Double performance on P2;
w4: can work on P2, P3, and has Double performance on P3;

*Man-Hours: P2 needs 16h so it will take 2 normal workers for 8 hours to be complete.
w3 is specially trained for this project and can make it alone for 8 hours.

The goal is: to create a schedule so that P3, and P2 are done in time and P1 should be done as much as possible (it is impossible to finish it).
Edit: each worker can change his current project at 1 hour intervals.

This scenario is easy to solve and is just for example. In the real scenario there are 20+ projects and 50+ workers with random dead-lines, working hours and performance speed.

I m looking for algorithms and methods how to solve this type of relations. By now I have reviewed:
Greedy Algorithms
Knapsack Problems
Simplex method

But the problem involves more then this... any ideas?

$\endgroup$
  • 1
    $\begingroup$ Is it possible that someone switches between project he is working on? $\endgroup$ – Listing Jan 28 '14 at 11:29
  • $\begingroup$ yes the, the tasks are "liquid". In the real scenario there should be a minimum of lets say "20 min" chunks of work on a project. $\endgroup$ – d.raev Jan 28 '14 at 11:33
  • $\begingroup$ For P1 is $30$ hours a minimum? I'm just trying to clarify exactly what "at maximum possible" means. $\endgroup$ – Geoff Pointer Jan 28 '14 at 11:39
  • $\begingroup$ P1 30 hours is the maximum, it is in fact not possible to copmlate it and the goal is to do as much as possible from P1 (but with the other two projects done in time) $\endgroup$ – d.raev Jan 28 '14 at 11:42
  • $\begingroup$ Thanks. That makes sense now that you've explained it but it's not clear in the question on first reading. $\endgroup$ – Geoff Pointer Jan 28 '14 at 11:49
1
$\begingroup$

We have a number of jobs $j_1,\ldots,j_n$ and a number of workers $w_1,\ldots,w_m$. Efficiency multipliers $\alpha_{i,j}$ which say how fast worker $i$ can work on job $j$ (can be $0$ if he can't work on the job). Let $r_i$ denote the length of job $j_i$.

Let us assume for simplicity that the deadline $d_i$ of the job $j_i$ is a natural number (or $\infty$ if there is no deadline), denoting after how many hours the job should be done. We fix some simulation time $T \in \mathbb{N}$ until which we want to generate a schedule. And $T \geq d_i$ for all $i$.

Now we can introduce variables $x_{t,i,j}$, for $t \in \{1,2,\ldots,T\}, i \in \{1,\ldots,m\}$ and $j \in \{1,\ldots,n\}$ which corresponds to the amount of time worker $i$ has worked on job $j$ in the time $[t-1,t)$.

We have linear constraints: $0\leq x_{t,i,j} \leq 1$ for all $t,i,j$.

Every worker works at most $1$ hour: $\forall i \in \{1,\ldots,m\}\forall t \in \{1,2,\ldots,T\}: \sum_{j=1}^{n}x_{t,i,j}\leq 1$

All jobs with deadline get done before the deadline: $\forall j \in \{1,2,\ldots,n\} \text{ s.t. }d_i<\infty: \sum_{t=1}^{d_i}\sum_{i=1}^m \alpha_{i,j}x_{t,i,j}\geq r_i$

We want to maximize the amount of work done on the jobs without a deadline:

$\max \sum_{j \in \{1,2,\ldots,n\} \text{ s.t. }d_i=\infty}\sum_{t=1}^{T}\sum_{i=1}^m \alpha_{i,j}x_{t,i,j}$.

This is a linear program with a polynomial amount of variables and inequalities and can be solved in polynomial time.

Note that what makes this easy is that the tasks are "liquid", i.e. a worker can work on all tasks in one time step. If you want them to be not liquid you could increase the time steps and make the $x_{t,i,j}$ integer variables, which would potentially not admit a polynomial time algorithm.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for nice definitions, can you point me out to the method/algorithm how to actually solve it ? $\endgroup$ – d.raev Jan 28 '14 at 12:06
  • $\begingroup$ @d.raev the most commonly used algorithm to solve linear programs is the simplex algorithm. But there are many solvers freely available which will perform much better than your own implementation. $\endgroup$ – Listing Jan 28 '14 at 12:08
  • $\begingroup$ so all it takes is to properly define the restrictions and maximization values. Thanks a lot will try it later. $\endgroup$ – d.raev Jan 28 '14 at 12:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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