Sorry if this very silly, but I am somewhat new to optimization theory:

We have $m$ identical machines and $n$ jobs. A job $j$ can be done in any of the identical machines in $p_{j}$ time units. The jobs can be divided between the machines. i.e., every arbitrary part of a job can be done by any of the machines. Let $x_{i,j} \in \mathbb{Z}$ be the processing time of the job $j$ in the machine $i$. The target is to minimize $$\max_{i \in \{1,2,..,m\}} \sum_{j=1}^{n}x_{ij}$$

I need just to formulate this problem in the language of linear programming.

Here is what I did:

We have $m \cdot n$ integer variable satisfying the following:

$\sum_{i=1}^{i=m}x_{ij}=p_{j}$ for every $j=1,...,n$

which can be rewritten as:

$\;\;\;\sum_{i=1}^{i=m}x_{ij}\leq p_{j}$ for every $j=1,...,n$

$-\sum_{i=1}^{i=m}x_{ij}\leq -p_{j}$ for every $j=1,...,n$

and also:

$x_{ij}\geq 0$ for every $i=1,..,m$ and $j=1,..,n$

My question: if $X$ is the vector of all variables $x_{ij, }$ what should the vector $c$ be in the formula $\max\{\;c^{T}X\}$, so that the translation is complete.

Thanks in advance

  • $\begingroup$ It would probably serve you better to either have a matrix variable $X$ or a series of vector variables $x_k$. $\endgroup$ – Ross B. Jun 3 '13 at 16:48

Ok, simply we just add a variable $y\in \mathbb{Z}$ and $m$ conditions which are:

$\sum_{j=1}^{j=n}x_{ij} \leq y$ for every $i\in\{1,2,...,m\}$

and then we should minimize $y$ :)

i.e.we take $X^{t}=(y,x_{11},x_{12},....,x_{mn})$ and $C^{t}=(1,0,...,0)$ with $m*n$ zero's.

So, now the target is to minimize $Z:=C^{t}X$


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.