# mixed integer programming formulation for n jobs on m machines with preceding constraints

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.

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.