## 2 The Relaxed Flexible Flow Shop Problem Model with Sequence-Dependent Setup Times (RFFSP) Methods
### Simulated Annealing Algorithm
Once the correction is made, the new neighboring solution is available:

\[O_{121}\to O_{131}\to O_{211}\to O_{122}\to O_{212}\to O_{232}\to O_{123} \to O_{133}\to O_{213}\]

## 4 Experimental Results

In this section are the experimental results of the hybrid genetic algorithm in grid environment (HGAG). ### Platform of Experimentation

Grid Morelos is one of the first Mexican grids [31]. This grid is a homogenous platform constituted by two high-performance computer clusters, geographically distant (14.37 km) between them, and placed in the Morelos State. The main elements of the grid are the Cuexcomate and Texcal clusters. The Cuexcomate cluster is located at the Autonomous University of Morelos State (UAEM) in Cuernavaca Morelos, Mexico. The Texcal cluster is located at the Polytechnic University of Morelos State (UPEMOR), in Jiutepec, Morelos, Mexico. An open virtual private network integrates the clusters in a grid environment. Each cluster has its nodes, but the cluster Cuexcomate and the cluster Texcal have similar characteristics. The communication between these clusters is via a wireless WAN link between institutions implemented via a point-to-point microwave link with ISM frequency bands with 30 Mbps bandwidth. The grid software includes an OS Centos Linux 5.5, 64 bits, a gcc 4.1.2 compiler, an OpenMPI 1.8, an MPICH2, an Intel compiler MPI 12.0, a Ganglia 3.1.7, NFS-utils 1.0.9, VLAN, and Torque + Maui. The cluster communication uses a Switch 3 COM 24/10/100/1000, a Switch InfiniBand Mellanox, 18 ports, 40 Gb/s QDR, and each cluster node uses an InfiniBand card 40 Gb/s. Each cluster has a master node with two Intel Xeon, Six-Core 3.06 GHz (12 cores), 12 MB cache, 6 HD 7200 RPM, 12 TB, 24 GB RAM. Furthermore, each cluster has four slave nodes with a two Intel Xeon Six-core 3.06 GHz (12 cores), 12 MB cache, 1 HD 7200 RPM, 500 GB, 24 GB RAM, InfiniBand card 40 Gb/s. In summary, the Grid Morelos has ten nodes and 120 cores. ### Generation of Test Instances

When searching the existing literature, no instances were found with which the algorithm proposed in this manuscript could be compared. This is because the optimization model used in the present work is an adaptation of that defined in [23]. To the best of our knowledge, there is no similar algorithmic approach to comparing results. The model most similar to the one presented in [23] only analyzes a small-size instance that uses restrictions for machine blocking, this set of restrictions does not apply in this work in the optimization model that is resolved. Therefore, medium-size and large-size instances of the optimizationmodel were generated, which allowed us to evaluate the performance of the HGAG in a high-performance computing environment and above 120 parallel processes. According to the number of jobs, the benchmarks used are classified in the literature as small, medium, and large instances [32,33]. This work randomly generates benchmarks to solve the RFFSP described in Section 2. Based on [33], these benchmarks are also randomly generated using a proprietary program codified in the C language. The benchmarks are generated with the following characteristics:

* Five groups of jobs \(N=\{\)20, 40, 60, 80, 140\(\}\);
* Three groups of stages K = {2, 4, 8};
* Four groups of machines M = {2, 3, 4, 5};
* Processing times p\({}_{\rm jk}\) uniformly distributed in the range (1-99);
* Setup times ST\({}_{\rm jk}\), uniformly distributed in the ranges (1-25), (1-50), (1-00), and (1-125). These values correspond to 25%, 50%, 100% and 125% of ratio, according to the processing times.