3
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ 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. $\endgroup$ Commented Jun 15, 2022 at 8:52
  • 2
    $\begingroup$ 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... $\endgroup$ Commented Jun 15, 2022 at 8:55
  • $\begingroup$ 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$. $\endgroup$
    – PeterD
    Commented Jun 15, 2022 at 11:16
  • $\begingroup$ 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.$ $\endgroup$
    – prubin
    Commented Jun 15, 2022 at 15:37
  • $\begingroup$ @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). $\endgroup$ Commented Jun 15, 2022 at 17:52

1 Answer 1

3
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thanks @prubin. I lost my login account for a long time. I take your answer into consideration but I replaced some details using some disagregated constraints like $y_i + y_j + z_{ij} \leq 2$. $\endgroup$ Commented May 3 at 23:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.