added 898 characters in body
Source Link
RobPratt
  • 19k
  • 1
  • 26
  • 60

You can model this with a binary variable $x_{i,j}$ to indicate whether task $i$ is assigned to worker $j$, and a binary variable $y_{i,j}$ to indicate whether task $i$ is the first task assigned to worker $j$ in the current batch. The number of switches is then $\sum_{i\ge 2} \sum_j y_{i,j}$ because this sum counts the number of times that any worker starts a new batch of tasks (except the first batch that contains task $i=1$). The constraints are: \begin{align} \sum_j x_{i,j} &= 1 &&\text{for all $i$}\\ x_{1,j} &= y_{1,j} &&\text{for all $j$} \\ x_{i,j} - x_{i-1,j} &\le y_{i,j} &&\text{for $i\ge 2$ and all $j$} \\ y_{i,j} &\le x_{i+k,j} &&\text{for $k\in\{0,\dots,2\}$}\\ \end{align}\begin{align} \sum_j x_{i,j} &= 1 &&\text{for all $i$}\\ x_{1,j} &= y_{1,j} &&\text{for all $j$} \\ x_{i,j} - x_{i-1,j} &\le y_{i,j} &&\text{for $i\ge 2$ and all $j$} \\ y_{i,j} &\le x_{i+k,j} &&\text{for $k\in\{0,1,2\}$}\\ \end{align} The first constraint assigns each task to exactly one worker. The second constraint forces task 1 to start a new batch. The third constraint enforces the logical implication that, if task $i$ is assigned to worker $j$ and task $i-1$ is assigned to a different worker, then task $i$ starts a new batch for worker $j$; that is, $(x_{i,j}=1 \land x_{i-1,j}=0) \implies y_{i,j}=1$. The fourth constraint enforces the logical implication that, if task $i$ start a new batch for worker $j$ tasks, then tasks $i$ through $i+2$ (3 consecutive tasks) must be assigned to worker $j$; that is, $y_{i,j}=1 \implies x_{i+k,j}=1$.

You specified a quadratic objective, so you could use an MIQP solver. Or you could change the objective to $$\left|\sum_i v_i x_{i,2} - 0.7V\right| + c \cdot m,$$ linearize the absolute value and use an MILP solver.

You can model this with a binary variable $x_{i,j}$ to indicate whether task $i$ is assigned to worker $j$, and a binary variable $y_{i,j}$ to indicate whether task $i$ is the first task assigned to worker $j$ in the current batch. The number of switches is then $\sum_{i\ge 2} \sum_j y_{i,j}$ because this sum counts the number of times that any worker starts a new batch of tasks (except the first batch that contains task $i=1$). The constraints are: \begin{align} \sum_j x_{i,j} &= 1 &&\text{for all $i$}\\ x_{1,j} &= y_{1,j} &&\text{for all $j$} \\ x_{i,j} - x_{i-1,j} &\le y_{i,j} &&\text{for $i\ge 2$ and all $j$} \\ y_{i,j} &\le x_{i+k,j} &&\text{for $k\in\{0,\dots,2\}$}\\ \end{align} The first constraint assigns each task to exactly one worker. The second constraint forces task 1 to start a new batch. The third constraint enforces the logical implication that, if task $i$ is assigned to worker $j$ and task $i-1$ is assigned to a different worker, then task $i$ starts a new batch for worker $j$; that is, $(x_{i,j}=1 \land x_{i-1,j}=0) \implies y_{i,j}=1$. The fourth constraint enforces the logical implication that, if task $i$ start a new batch for worker $j$ tasks $i$ through $i+2$ must be assigned to worker $j$; that is, $y_{i,j}=1 \implies x_{i+k,j}=1$.

You specified a quadratic objective, so you could use an MIQP solver. Or you could change the objective to $$\left|\sum_i v_i x_{i,2} - 0.7V\right| + c \cdot m,$$ linearize the absolute value and use an MILP solver.

You can model this with a binary variable $x_{i,j}$ to indicate whether task $i$ is assigned to worker $j$, and a binary variable $y_{i,j}$ to indicate whether task $i$ is the first task assigned to worker $j$ in the current batch. The number of switches is then $\sum_{i\ge 2} \sum_j y_{i,j}$ because this sum counts the number of times that any worker starts a new batch of tasks (except the first batch that contains task $i=1$). The constraints are: \begin{align} \sum_j x_{i,j} &= 1 &&\text{for all $i$}\\ x_{1,j} &= y_{1,j} &&\text{for all $j$} \\ x_{i,j} - x_{i-1,j} &\le y_{i,j} &&\text{for $i\ge 2$ and all $j$} \\ y_{i,j} &\le x_{i+k,j} &&\text{for $k\in\{0,1,2\}$}\\ \end{align} The first constraint assigns each task to exactly one worker. The second constraint forces task 1 to start a new batch. The third constraint enforces the logical implication that, if task $i$ is assigned to worker $j$ and task $i-1$ is assigned to a different worker, then task $i$ starts a new batch for worker $j$; that is, $(x_{i,j}=1 \land x_{i-1,j}=0) \implies y_{i,j}=1$. The fourth constraint enforces the logical implication that, if task $i$ start a new batch for worker $j$, then tasks $i$ through $i+2$ (3 consecutive tasks) must be assigned to worker $j$; that is, $y_{i,j}=1 \implies x_{i+k,j}=1$.

You specified a quadratic objective, so you could use an MIQP solver. Or you could change the objective to $$\left|\sum_i v_i x_{i,2} - 0.7V\right| + c \cdot m,$$ linearize the absolute value and use an MILP solver.

added 898 characters in body
Source Link
RobPratt
  • 19k
  • 1
  • 26
  • 60

You can model this with a binary variable $x_{i,j}$ to indicate whether task $i$ is assigned to worker $j$, and a binary variable $y_{i,j}$ to indicate whether task $i$ is the first task assigned to worker $j$ in the current batch. The number of switches is then $\sum_{i\ge 2} \sum_j y_{i,j}$ because this sum counts the number of times that any worker starts a new batch of tasks (except the first batch that contains task $i=1$). The constraints are: \begin{align} \sum_j x_{i,j} &= 1 &&\text{for all $i$}\\ x_{1,j} &= y_{1,j} &&\text{for all $j$} \\ x_{i,j} - x_{i-1,j} &\le y_{i,j} &&\text{for $i\ge 2$ and all $j$} \\ y_{i,j} &\le x_{i+k,j} &&\text{for $k\in\{0,\dots,2\}$}\\ \end{align} The first constraint assigns each task to exactly one worker. The second constraint forces task 1 to start a new batch. The third constraint enforces the logical implication that, if task $i$ is assigned to worker $j$ and task $i-1$ is assigned to a different worker, then task $i$ starts a new batch for worker $j$; that is, $(x_{i,j}=1 \land x_{i-1,j}=0) \implies y_{i,j}=1$. The fourth constraint enforces the logical implication that, if task $i$ start a new batch for worker $j$ tasks $i$ through $i+2$ must be assigned to worker $j$; that is, $y_{i,j}=1 \implies x_{i+k,j}=1$.

You specified a quadratic objective, so you could use an MIQP solver. Or you could change the objective to $$\left|\sum_i v_i x_{i,2} - 0.7V\right| + c \cdot m,$$ linearize the absolute value and use an MILP solver.

You can model this with a binary variable $x_{i,j}$ to indicate whether task $i$ is assigned to worker $j$, and a binary variable $y_{i,j}$ to indicate whether task $i$ is the first task assigned to worker $j$ in the current batch. The number of switches is then $\sum_{i\ge 2} \sum_j y_{i,j}$. The constraints are: \begin{align} \sum_j x_{i,j} &= 1 &&\text{for all $i$}\\ x_{1,j} &= y_{1,j} &&\text{for all $j$} \\ x_{i,j} - x_{i-1,j} &\le y_{i,j} &&\text{for $i\ge 2$ and all $j$} \\ y_{i,j} &\le x_{i+k,j} &&\text{for $k\in\{0,\dots,2\}$}\\ \end{align}

You can model this with a binary variable $x_{i,j}$ to indicate whether task $i$ is assigned to worker $j$, and a binary variable $y_{i,j}$ to indicate whether task $i$ is the first task assigned to worker $j$ in the current batch. The number of switches is then $\sum_{i\ge 2} \sum_j y_{i,j}$ because this sum counts the number of times that any worker starts a new batch of tasks (except the first batch that contains task $i=1$). The constraints are: \begin{align} \sum_j x_{i,j} &= 1 &&\text{for all $i$}\\ x_{1,j} &= y_{1,j} &&\text{for all $j$} \\ x_{i,j} - x_{i-1,j} &\le y_{i,j} &&\text{for $i\ge 2$ and all $j$} \\ y_{i,j} &\le x_{i+k,j} &&\text{for $k\in\{0,\dots,2\}$}\\ \end{align} The first constraint assigns each task to exactly one worker. The second constraint forces task 1 to start a new batch. The third constraint enforces the logical implication that, if task $i$ is assigned to worker $j$ and task $i-1$ is assigned to a different worker, then task $i$ starts a new batch for worker $j$; that is, $(x_{i,j}=1 \land x_{i-1,j}=0) \implies y_{i,j}=1$. The fourth constraint enforces the logical implication that, if task $i$ start a new batch for worker $j$ tasks $i$ through $i+2$ must be assigned to worker $j$; that is, $y_{i,j}=1 \implies x_{i+k,j}=1$.

You specified a quadratic objective, so you could use an MIQP solver. Or you could change the objective to $$\left|\sum_i v_i x_{i,2} - 0.7V\right| + c \cdot m,$$ linearize the absolute value and use an MILP solver.

Source Link
RobPratt
  • 19k
  • 1
  • 26
  • 60

You can model this with a binary variable $x_{i,j}$ to indicate whether task $i$ is assigned to worker $j$, and a binary variable $y_{i,j}$ to indicate whether task $i$ is the first task assigned to worker $j$ in the current batch. The number of switches is then $\sum_{i\ge 2} \sum_j y_{i,j}$. The constraints are: \begin{align} \sum_j x_{i,j} &= 1 &&\text{for all $i$}\\ x_{1,j} &= y_{1,j} &&\text{for all $j$} \\ x_{i,j} - x_{i-1,j} &\le y_{i,j} &&\text{for $i\ge 2$ and all $j$} \\ y_{i,j} &\le x_{i+k,j} &&\text{for $k\in\{0,\dots,2\}$}\\ \end{align}