Multiprocessor Scheduling Problem: How to modify some constraints after variable changing?

Question

I am thinking about classic problems concerning partitions as the Multiprocessor Scheduling Problem (or Bin Packing or Number Partitioning):

Given $n$ tasks, with times $\{t_i\}_{i\in I_n}$, and $m$ machines. The goal is to assign each task to a machine such that the maximum time to finish all tasks is minimized. ($I_n = \{1,2,3,...,n\}$)

It is possible to build a mathematical model for Multiprocessor Scheduling Problem as follows:

\begin{eqnarray} \min && \label{b1} T \\ \mbox{suj. a} && \label{b2} \sum_{i=1}^{n}t_i x_{i,j} \leq T, \quad \forall j\in I_m \\ && \label{b3} \sum_{j=1}^{m} x_{i,j} = 1, \quad \forall i\in I_n \quad (*)\\ && \label{b4} \sum_{i=1}^{n} x_{i,j} \geq 1, \quad \forall j\in I_m \quad (**)\\ && \label{b5} x_{i,j} \in\{0,1\}, \quad \forall (i,j)\in I_n\times I_m\\ && \label{b6} T \in \mathbb{R}_{+} \end{eqnarray}

Where the variable $x_{i,j}$ indicates if the task $i$ is assigned in the machine $j$, or not. Assume that we change the variable $x_{i,j}$ by $z_{i,k}$ which means the tasks $i$ and $k$ are both assigned in the same machine ($z_{i,i}=1$, task $i$ is alone in a machine). In another words,

$$z_{i,k}=\sum_{j=1}^{m} x_{i,j}.x_{k,j}, \quad \forall (i,k): 1\leq i\leq k \leq n$$

I know how to ensure the transitivity relationship and calculate the total time in each machine

$$z_{ij} + z_{jk} - z_{ik}\leq 1, \quad \forall (i,j,k): 1\leq i<j<k\leq n$$ $$ \sum_{i=k}^{n}t_i z_{i,k} \leq T $$

I do not know how to translate (*) and (**). I am thinking about how to do it. Thank you for any tip you share with me.

Answer 1

The condition (*), that every job is assigned to exactly one machine, simply requires $$\sum_{i=k}^n z_{i,k} \ge 1 \quad \forall i=1,\dots,n.$$ That ensures that every job belongs to a cluster. It cannot belong to two clusters, because transitivity would force those two clusters to be the same.

The condition (**), that every machine is assigned at least one job, is unnecessary. In the unlikely event that the optimal solution leaves a machine unused, you can manually adjust the solution by taking a job off any machine tied for longest cycle time and parking that job on the idle machine. (There would have to be a tie, else the minimum cycle time would not actually be minimal.)

Now the bad news: You need a constraint enforcing the rule that at most $m$ clusters of jobs can be constructed. I do not see a way to do that with just the $z$ variables. A workaround would be to introduce more binary variables $y_1,\dots,y_n$ with the constraints $$ z_{i,k} \le 1-y_i\quad \forall i, \, \forall k < i$$ $$ y_i \le \sum_{k\ge i} z_{i,k} \quad \forall i$$ and $$ \sum_{k < i} z_{i,k} \ge 1- y_i\quad \forall i.$$ We interpret $y_i=1$ to mean that $i$ is the lowest indexed job on whatever machine gets it. If $y_i=1,$ the first constraint blocks any lower indexed job for being in its cluster, the second constraint forces at either $i$ or at least one higher indexed job to be in its cluster, and the third constraint is nonbinding. If $y_i =0,$ the first two constraints are nonbinding and the third constraint forces at least one lower index job to be in the cluster containing $i$.

Armed with this, you can limit the number of machines used (equal to the number of clusters created) with $$\sum_i y_i \le m$$ (or force all machines to be used by making it an equality).

More (albeit mild) bad news: So far, nothing stops $z_{1,1} = z_{1,2} = 1$ occurring. So your interpretation of $z_{i,i}=1$ as task $i$ being alone on a machine is on somewhat thin ice. Again, this can be fixed manually when editing the solution. The solver has a disincentive to choose a solution like this if it increases the cycle time on a machine tied for maximum cycle time, but on a machine that gets done "early" the solver might pick this.

Finally (and perhaps I should have led with this), your calculation of machine cycle time is wrong. You wrote $$\sum_{i=k}^n t_i z_{i,k} \le T,$$which I assume was meant to apply for all $k=1,\dots,n.$ Suppose that jobs 1, 2 and 3 (only) are assigned to a machine. When $k=1$, the left side becomes $$t_1 z_{1,1} + t_2 z_{2,1} + t_3 z_{3,1} + \dots = t_2 + t_3,$$ which is less than the actual cycle time by the amount $t_1.$ For $k=2$ you get $$t_2 z_{2,2} + t_3 z_{3,2} + \dots = t_3,$$ which is even further off. For $k=3$ the left side is zero. If you include the $y$ variables and add $t_k y_k$ to the left side of your constraint and start the summation at $i=k+1$ (to avoid double-counting if $y_1=1=z_{i,i}$), I think it works (but someone should check it).