Parallel scheduling with precedence constraints and variable job length

Question

I have $N$ jobs and $M$ machines and want to minimize the makespan, i.e. the total time to finish all jobs. Some jobs have precedence constraints and can only be started once other jobs are finished. Not all machines can do all of the jobs. So far I have a working solution implemented in ortools based on a problem formulation from this StackOverflow answer.

However I would like to modify the problem, and this is where it gets more tricky. Before, it was assumed that the time it takes a machine $m$ to do job $n$ is a fixed function $t(m,n)$. However, I would like to modify the problem such that the time it takes machine $m$ to do job $n$ is also a function of the previous job completed by machine $m$ (or a "dummy job" if the machine hasn't done any jobs yet). Something like: $t'(m, n, n_{prev})$

I am struggling to add this to the problem formulation. Any suggestions, or links to relevant papers, would be appreciated. I am envisioning a $t_{m}$ matrix for each machine $m$ where $t_{m,i,j}$ is the time for machine $m$ to complete job $j$ if the previous job it did was $i$.

Answer 1

If you search for literature on job shop scheduling with sequence-dependent setups, I think you will find what you want. As the phrase suggests, sequence-dependent setups refer to lost time and/or additional cost incurred during a transition of a machine from one job to another. Although setup times are typically viewed as separate from processing times, you could treat a processing time $t_{m,i,j}$ as the sum of a base processing time $\tau_{m,j} = \min_i t_{m,i,j}$ and a "setup" time $s_{m,i,j}=t_{m,i,j}-\tau_{m,j}$.

Answer 2

First of all, if in the problem there is a specific precedence constraint for each job, let's say each job has its specific route, your problem sounds like (flexible) job shop scheduling which is different from parallel scheduling problem. There are some ways to tackle this problem, e.g. using MIP, CP or (meta) heuristics methods. In the first case (MIP), as this problem is well known as a hard problem class, for the real world-class problems it takes a too long time to solve efficiently. CP or heuristic is an excellent way to do that. There are many resources that you can read by googling. Is it what you are looking for?