## 1 Introduction  
The problem that is investigated in this paper is the Distributed Permutation Flow-shop Scheduling Problem (DPFSP), which is an extension of the Permutation Flow-shop Scheduling Problem (PFSP), a variant of the Flow-shop Scheduling Problem (FSP), which, in its turn, is closely related to the Job-shop Scheduling Problem (JSP).  
JSP constitutes a classical combinatorial optimization challenge in production planning and scheduling. It serves as a fundamental abstraction of scheduling tasks in manufacturing and service environments, wherein a finite number of jobs, each comprising a sequence of tasks (also referred to as operations), must be executed on a set of machines. Each task requires a predefined processing time and can only be performed on a specific machine. The objective of JSP is to construct a schedule that optimizes a chosen performance criterion, which is often the minimization of the makespan (i.e., the time it takes to finish all jobs in a given schedule). At the same time, numerous operational constraints must be respected, often precedence constraints that stipulate the order of execution for the tasks within each job.  
FSP closely parallels the JSP in terms of its conceptualization. Within the FSP, a set of jobs is subject to processing on a sequence of machines, each with the same predetermined order of tasks. This sequential constraint differentiates the FSP, which maintains a consistent order of tasks across all jobs and from the JSP, where task sequences can vary among machines. On the other hand, in FSP, the order of jobs executed at each machine can be different.  
PFSP emerges as a variant of the FSP, introducing an additional constraint that states that a fixed order of jobs (i.e., a specific permutation of jobs) should be maintained for all machines. At the same time, as in FSP, all jobs have the same processing order through the machines. PFSP represents an actual requirement of several installations when, for example, a conveyor feeds tasks to the machines. Then, the sequence of jobs each machine should process should be the same for all jobs.  
Finally, DPFSP is a problem introduced in [1] that extends PFSP by allowing more than one identical factories to exist in the problem. So, each factory contains an identical set of machines with other factories. Denoting with \(P_{j\!f}\) as the processing time of job \(j\) on machine \(i\) of factory \(f\), it holds that \(P_{j\!i0}=P_{j\!i1}=P_{j\!i2}=\cdots\). The typical objective of DPFSP is to minimize the makespan.  
The rest of the paper is organized as follows: Section 2 provides a detailed description of DPFSP, alongside a description of publicly available problem instances (i.e., two datasets: one with small problem sizes and one with large ones) that will be used in the experiments. The next section (Section 3) presents the related work. The following section (Section 4) presents the approach employed for solving the DPFSP. It starts with a subsection for the heuristic used to produce good initial solutions. Then, a detailed description of a Constraint Programming model of DPFSP follows. A second model is then presented that drops the same permutation for all machines of the same factory constraint, which essentially changes the problem and now becomes DFSP. Then, a novel heuristic is presented, capable of generating good lower bounds. Section 5 presents results firstly about the efficacy of the lower-bound heuristic. Then, results are shown for the small dataset, where all problem instances are solved to optimality. In the next subsection, results are presented for the first group of large problem instances (i.e., the first 30 problem instances for each category defined by the number of factories, which are 2, 3, 4, 5, 6, and 7). These 180 problem instances are also solved optimally for most of the cases. Then, Section 6 discusses the paper's findings. Finally, the last section (Section 7) presents the conclusions. Tables with detailed results are included in the paper's Appendix A.