I have come across an Optimization question as follows:

There are $n$ jobs that have to be processed on a machine. The machine can process only one job at a time. The time taken to process job $i$ on the machine is $t_i$. For a given sequence of jobs on the machine, the completion time of job $i$ is the time at which the machine finishes processing job $i$. The goal is to find the sequence of jobs which minimises the sum of the squared completion times.

I have attempted to solve it as follows but am not sure if it's correct. In particular I'm unsure about the constraints for the binary variables.

Variables: Let $x_{ij}=1$, for $i \in {1,...,n}$, $j \in 1,...,n$, $j \neq i$ if job $i$ is completed after job $j$, 0 otherwise.
Let $y_i$, $i \in {1,...,n}$ be the completion time for job $i$.

Min. $\sum_{i=1}^n y_i^2$

s.t. $y_i - \sum_{j \neq i} t_j x_{ij} \quad \forall i \in {1,...,n} $

$\quad\; x_{ij} + x_{jk} - 2x_{ik} \leq 1 \quad \forall i \neq j \neq k$

$\quad\; \sum_{i \neq j} x_{ij} = \sum_{m=1}^{n-1}m$

$\quad\; x_{ij} \in {0,1} \quad \forall i \neq j $

$\quad\; y_i \in \mathbb{R}^+$


Hint: If you interchange two jobs, what happens to the objective? Conclude that the jobs should be sorted by ...

  • $\begingroup$ The jobs should be sorted by time? $\endgroup$ – Jack Dec 30 '14 at 10:44

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.