# A Hybrid Discrete Memetic Algorithm for Solving Flow-Shop Scheduling Problems
## 2 The Flow-Shop Problem  
Flow-shop scheduling for manufacturing is a production planning and control technique used to optimize the sequence of operations that each job must undergo in a manufacturing facility. In a flow-shop environment, multiple machines are arranged in a specific order, and each job must pass through the same sequence of operations on these machines. The objective of flow-shop scheduling is to minimize the total time required to complete all jobs (makespan) or to achieve other performance measures such as minimizing the total completion time, total tardiness, or maximizing resource utilization. The storage buffer between machines is considered to be infinite. If the manufactured products are small in physical size, it is often easy to store them in large quantities between operations [19]. Permutation flow shop is a specific type of flow-shop scheduling problem in manufacturing where a set of jobs must undergo a predetermined sequence of operations on a series of machines. In the permutation flow shop, the order of operations for each job remains fixed throughout the entire manufacturing process. However, the order in which the jobs are processed on the machines can vary, resulting in different permutations of jobs [20]. Consider a flow-shop environment, where \(N_{J}\) denotes the number of jobs and \(N_{R}\) is the number of resources (machines). A given permutation \(j_{i}\), \(i\in\{1,2,\ldots,N_{J}\}\), where \(i\) is the index of the job, \(p_{j,r}\) represents the processing times, \(r\in\{1,2,\ldots,N_{R}\}\) is the \(r\)th resource in the manufacturing line, \(S_{j,r}\) is the starting times of job \(j_{i}\) on machine \(r\), and \(C_{r,j_{k}}\) is the completion time of job \(j_{k}\) on resource \(r\), has the following constraints:  
A resource can only process one job at a time; therefore, the start time of the next job must be equal to or greater than the completion time of its predecessor on the same resource:  
\[C_{j,r}\leq S_{j_{i+1},r}\qquad r=1,2,\ldots,N_{R};\ i=1,2,\ldots,N_{J}-1. \tag{1}\]  
A job can only be present on one resource at a given time; therefore, the start time of the same job on the next resource must be greater then or equal to the completion time of its preceding operation:  
\[C_{j,r}\geq C_{j,r+1}\qquad r=1,2,\ldots,N_{R}-1;\ i=1,2,\ldots,N_{J}. \tag{2}\]  
The first scheduled job does not have to wait for other jobs and is available from the start. The completion time of the first job on the current machine is the sum of its previous operations on preceding machines in the chain and its processing time on the current machine:  
\[C_{j_{1},r}=\sum_{k=1}^{r}p_{j_{1},k}\qquad i=1,\ldots,N_{R}. \tag{3}\]  
Figure 1 shows how the first scheduled job has only one contingency: its own operations on previous machines. Jobs on the first resource are only contingent on jobs on the same resource; therefore, the completion time of the job is the sum of the processing times of previously scheduled jobs and its own processing time:  
\[C_{j,1}=\sum_{k=1}^{i}p_{j,1}\qquad j=1,\ldots,N_{J}. \tag{4}\]  
Figure 2 shows how there is only on contingency on the first machine; therefore, operations can follow each other without downtime. When it comes to subsequent jobs on subsequent machines, (\(i>1,\ r>1\)) the completion times depend on the same job on previous machines (Equation (2)) and previously scheduled jobs on previous machines in the chain (Equation (1)):  
\[ \begin{split} C_{j,r}&=\max\big{(}C_{j,r-1},C_{j,-1,r}\big{)}+p_{j,r},\\ r&=2,\ldots,N_{R};\quad i=2,\ldots,N_{J}.\end{split}  \tag{5}\]  
Figure 3 shows the contingency of jobs. \(j_{2,2}\) is contingent upon \(j_{1,2}\) and \(j_{2,1}\), where it has to wait for \(j_{2,1}\) to finish despite the availability of machine 2. \(j_{2,3}\) is contingent upon \(j_{2,2}\) and \(j_{1,3}\), where it has to wait for machine 3 to become available despite being completed on machine 2. The completion time of the last job on the last resource is to be minimized and is called the makespan.