## 4 Materials and Methods
### A Novel Heuristic for Achieving Lower Bounds  
This section presents a heuristic for computing lower bounds of problem instances that apply to DPFSP and DFSP. Let \(i\in\mathbb{M}\) be the index of the \(i^{th}\) machine in a series of machines that is replicated across all factories. The heuristic evenly distributes the total process time of all jobs at machine \(i\) of a factory. This should ideally occur when the total process time of all jobs at machine \(i\) is divided by the number of factories, giving value \(AVE_{i}\). The lower bound is computed by examining each machine \(i\) in the series of machines in turn. For each machine \(i\), two values are computed: the shortest total execution time of a job for machines that precede machine \(i\), and the shortest total execution time of a job for the machines that come after machine \(i\). Potential lower bounds are calculated by adding these two minimum values to \(AVE_{i}\). Finally, the maximum of the potential lower bounds for all machines is the lower bound. Algorithm 1 describes the procedure in pseudo-code. Input: A DPFSP problem instance  
Output: A lower bound for the makespan of all possible schedules  
```
1:for\(i\gets 0\ldots|\mathbb{M}|-1\)do
2:\(AVE_{i}\leftarrow\) Average process time of all jobs at machine \(i\)
3:endfor
4:\(A\leftarrowAVE_{0}+\) minimum total execution time at machines \(1\ldots|\mathbb{M}|-1\) from a single job
5:\(B\leftarrowAVE_{|\mathbb{M}|-1}+\) minimum total execution time at machines \(0\ldots|\mathbb{M}|-2\) from a single job
6:\(C\leftarrow\emptyset\)
7:for\(i\gets 1\ldots|\mathbb{M}|-2\)do
8:\(L_{i}\leftarrow\) minimum total execution time at machines \(0\ldots i-1\) from a single job
9:\(R_{i}\leftarrow\) minimum total execution time at machines \(i+1\ldots|\mathbb{M}|-1\) from a single job
10:\(C\leftarrow\)\(C\cup\{L_{i}+AVE_{i}+R_{i}\}\)
11:endfor
12:return\(\max(A,B,\max(C))\)
```  
**Algorithm 1** Lower Bound Heuristic  
The main idea behind the computation of the lower bound is depicted in Figure 5, where at the left of the figure, the situation is shown where machine \(i\) is the first machine; in the right of the figure, the situation of machine \(i\) is the last machine is depicted; and in the middle of the figure, the situation is depicted where the machine \(i\) is any machine in between. Figure 5: Makespan lower bounds considering execution of all jobs without gaps at each machine in turn. A proof of the validity of the lower bound follows:  
Proof of the Validity of the Lower Bound. : For computing the lower bound we assume that at a certain machine \(i\), all jobs are scheduled without any gaps between them. This naturally occurs at machine 0, but it can also occur at other machines too. Note that gaps might occur for each machine \(i\in 1\ldots M-1\) because the start of a job at this machine must be postponed until the same job finishes at machine \(i-1\) and the job that was previously processed at machine \(i\) has finished its execution. Let \(AVE_{i}\) be the average process time of all jobs at machine i (\(AVE_{i}\) is computed by totaling the process times of all jobs at machine \(i\) and dividing it by the number of factories). Then, let \(L_{i}\) be the minimum sum of process times for machines that precedes machine \(i\), among all jobs, by a single job. Likewise, let \(R_{i}\) be the minimum sum of process times for machines that come after machine \(i\), among all jobs, by a single job. Clearly, when machine \(i\) is the first machine, \(L_{0}\) will be zero, and when machine \(i\) is the final machine, \(R_{M-1}\) will be zero. We assert that the maximum \(L_{i}+AVE_{i}+R_{i}\) among all machines will be a lower bound for the problem. Let us assume that we know the optimal solution, where for each machine, the jobs are scheduled as dictated by a specific permutation of jobs, with possible gaps in between consecutive jobs.