Workflow Optimization

Question

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?

Answer 1

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.