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$
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$

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.