Assigning tasks to minimize cost

Question

I have a set of jobs that must be done on a given day in sequence. $J_1, J_2, J_3$, with deadlines $D_1, D_2, D_3$. There are three workers $W_1, W_2, W_3$ that can execute the tasks each one with varying effects of proficiency $V_1, V_2, V_3$, so a highly proficient worker will do the task in less time, but will also incur a higher cost $C_1, C_2, C_3$. I want to figure out the constraints for a linear program that will execute all tasks within their respective deadline, while minimizing my costs.

I have: $x_{ij}= \begin{cases} 1 &\text{if job $i$ executed by worker $j$},\\ 0 &\text{otherwise} \end{cases}$

and one of the constraints I believe should be the fact that I need to choose one, and only, one worker to do the job, so maybe:

$$\sum_{j=1}^3 X_{ij}=1 \quad \text{for $i\in J$}$$

The next constraints that we should consider is obviously the deadline; time to execute previous jobs plus time for current job, since they must be done in sequence (production line), so maybe:

$$\sum_{i=1}^3 \sum_{j=1}^3 T_{ij}X_{ij}\le D_i$$

$$ T_{ij}, i \in J, j \in W $$ is the time that worker $j$ needs to execute job $i$.

Are these constraints correct, or do they make sense in the first place? If not what should I consider?

Answer 1

First, the deadline constraint as given makes no sense. The summation over $i$ is incorrect.

Given the possibility of a worker doing multiple jobs, one possible fix is as follows. Introduce new variables $L_{ij} \ge 0$, representing the cumulative time worker $j$ spends on any of jobs 1 through $i$ (inclusive) assigned to worker $j$. The values of $L$ are determined by the following constraints (for all workers $j$): \begin{align*} L_{1j} & =T_{1j}X_{2j}\\ L_{2j} & =L_{1j}+T_{2j}X_{2j}\\ L_{3j} & =L_{2j}+T_{3j}X_{3j}. \end{align*} To enforce the deadlines, add the following constraints for all $j$: \begin{align*} L_{1j} & \le D_{1j}\\ L_{2j} & \le D_{2j}+T_{1j}(1-X_{2j})\\ L_{3j} & \le D_{3j}+(T_{1j}+T_{2j})(1-X_{3j}). \end{align*} Those constraints ensure that a worker finishes a task by the task's deadline if the worker is doing the task. You already have constraints to ensure that each task is done by a single worker.

Answer 2

The first constraint should be for $i\in J$ instead of $i\in W$.

The second constraint is missing $i\in J$, and you should not mix $\sum_i$ and $i\in J$. It might help to write this as three separate constraints, one per job. Also, you have not used $V_i$ anywhere.