1
$\begingroup$

I have a binary variable $x_{ijt}^k$ that is $1$ iff job $i$ is assigned to machine $j$ at time $t$ using processor $k$. I would like to express the following constraints:

  • If job $i$ is assigned to machine $j$ at time $t$ using processor $k$ then job $i$ cannot be assigned to machine $j'\neq j$.
  • If job $i$ is assigned to machine $j$ at time $t$ using processor $k$ then job $i$ cannot be assigned to machine $j$ at time $t'\neq t$ using processor $k'\neq k$.

In other words, both constraints say that once job $i$ is assigned to a machine, it must be assigned using the same processor on that machine.

For the first constraint, I write it as $x_{ijt}^k+x_{ij't'}^{k'}\leq 1$, for all $i,j'\neq j, k, k',t,t'$.

For the second constraint, I write it as $x_{ijt}^k+x_{ijt'}^{k'}\leq 1$, for all $i,j, k\neq k',t\neq t'$.

Can I improve this formulation?

$\endgroup$
  • $\begingroup$ What's wrong with the formulation you already have? I don't see how anyone could answer the question with either a "yes" (how would we know that some other formulation is better? there are no rules that guarantee that anyone formulation is better than another) or "no" (for the same reason), so the question doesn't seem likely to be answerable to me. $\endgroup$ – D.W. Sep 24 '18 at 0:20
  • $\begingroup$ @D.W. I thought that a formulation with many constraints like mine is not good that's why. $\endgroup$ – zdm Sep 24 '18 at 13:52
  • $\begingroup$ It's not clear to me why you thought that. $\endgroup$ – D.W. Sep 24 '18 at 14:47
  • $\begingroup$ Because the complexity of the problem will increase as the number of constraints increases. A "better" formulation to me is one that uses fewer constraints and fewer variables if possible. $\endgroup$ – zdm Sep 24 '18 at 15:03
2
$\begingroup$

Here is a different way to formulate the situation, which is simpler conceptually and which might be implemented more easily, although the number of variables is still the same (which can be not reduced fundamentally, anyway).

"Once job $i$ is assigned to a machine, it must be assigned using the same processor on that machine". It looks like it is assumed that a processor is attached to the same machine regardless of the job or time. That means there is only one degree of freedom about the variable $j$ and $k$.

Let us use a new index $p=(j,k)$ to denote a pair of machine and a processor on it. Let binary variable $x_i^{pt}$ be $1$ iff job $i$ is assigned to processor $p$ at time $t$ (the index $t$ and $p$ is put together since they represent the resources). Then we can express the constraints as a single inequality, $$x_i^{pt}+x_i^{p't'}\leq 1\quad \text{ for all }p\neq p',t,t', i$$

In the actual programming, we can pack $j$ and $k$ side by side to form $p$ as the union structure in C/C++. For example, let $p$ be a 32-bit unsigned integer whose upper 16 bits is $j$ and whose lower 16 bits is $k$. We can also use a hash table with $p$ as keys and $(j,k)$ as values.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

If your measure of "better" is number of variables or number of constraints, I don't believe it is possible to do better. You obviously can't use fewer variables as all of them are already defined; your formulation hasn't added any new variables. You have one inequality per constraint, so I don't see how you would expect to have fewer inequalities.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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