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

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 $$\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.

• about (*): I guess this means that "every task has to be fulfilled by some machine, than the sum should run to m instead of n. Jun 15, 2022 at 8:52
• about (**) I would interpret the meaning of this constraint as "every machine has to do at least one task". Which leads me to some follow-ups: Is this interpretation correct? If so, why is it necessary? I think if there are way more tasks than machines any optimal solution would use as many machines as possible anyways, particularly when the time to complete a task does not depend on the machine... Jun 15, 2022 at 8:55
• Firstly, your problem rather looks like a bin packing problem rather than a scheduling problem, as you only assign tasks to machines and you do not consider the schedule. Secondly, I do not understand your last new constraint: If $i = k$ and $z_{i,i}=1$, then you are just summing over $t_i$. Jun 15, 2022 at 11:16
• If you are attempting to eliminate the $x$ variables and use only the $z$ variables, that cannot work, because the $z$ variables tell you nothing about which machine each task is using. So you would need a triply indexed variable $z_{i,j,m}$, where 1 means tasks $i$ and $j$ are both on machine $m.$
– prubin
Jun 15, 2022 at 15:37
• @TimVarelmann () You are correct. The sum is from 1 to m. Thank you. (*) Yes, that interpretation is correct. I add that equation only in cases with "negative time", but it is not necessary in Multiprocessor Scheduling Problem (only for more general problems). Jun 15, 2022 at 17:52

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.
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).