2
$\begingroup$

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

$\endgroup$
1

2 Answers 2

2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ Yes, flexible job shop scheduling is what I'm looking for, but specifically a variant where the processing time of a job depends on the machine doing the job, and the previous job completed by the machine. The problem is small to medium size, so MIP/CP should both work. $\endgroup$
    – tphillips
    Dec 3, 2020 at 16:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.