# Formulate this scheduling problem as a linear program

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.

• It would probably serve you better to either have a matrix variable $X$ or a series of vector variables $x_k$. – 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$