3
$\begingroup$

Suppose $n$ jobs are required to be done, $m$ equally capable machines are available, each job takes $t_i$, $i\in{1\ldots n}$ time on chosen machine (this time cannot be split into parts). Some jobs can only be started when preceding ones are finished (binary matrix of precedence $A_{n\times n}$ is given on input). I need the set of at most linear (not quadratic etc.) inequalities on reals / integers / binary numbers which, when fed to the solver, would provide the shortest maximum makespan across all machines.

What I tried was to make an output binary matrix $O_{n\times T}$, where $T=\sum_{i=1}^{n}t_i$ , such that each job would be represented as $t_i$ 1's representing when the job has been done, and constrained to never exceed more than $m$ jobs at once. I'm starting to think this is not the way to go, as matrix of output gives me jobs divided into parts (which is illegal here), and I don't think there exists linear inequality/inequalities which would disallow this.

$\endgroup$

1 Answer 1

3
$\begingroup$

Your problem is called $P\mid\text{prec}\mid C_\text{max}$ in the notation of Graham et al. (1979). You can find MIP models and some computational results in Wang, Parallel machine scheduling with precedence constraints.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .