# A Reinforcement Learning Method for a Hybrid Flow-Shop Scheduling Problem
## 3 Description of the Hybrid Flow-Shop Scheduling Problem  
In this section, HFSP is introduced, and its standard model is established.  
A typical HFSP is shown in Figure 1, there are S stages in total in the process of HFSP, and \(m_{1}\), \(m_{2}\),..., \(m_{\text{S}}\) machines are included in each stage, respectively. Every workpiece must be worked in all stages in a certain order. In each stage, however, any one machine can be selected for each workpiece. For instance, the sequence [_start_, \(M_{12}\), \(M_{24}\),..., \(M_{53}\), stop] can be one of an order of a workpiece being machined.  
In HFSP, several assumptions are usually made as follows: first, once a workpiece starts to be worked, it cannot be interrupted; second, a machine can only process one workpiece at a time; third, a workpiece can only be processed on one machine at a time; fourth, workpieces can be machined on any machine at each stage; fifth, there is unlimited storage capacity between any two stages (i.e., a workpiece can wait for any time between the two processes).  
HFSP is divided into the determined initial sequence HFSP and the non-determined initial sequence HFSP in this paper, according to whether the initial sequence of the workpiece is deterministic or not. Knowing the processing time in each stage of the workpiece on each machine, the purpose of HFSP is to determine the distribution of each workpiece on the machines at each stage to minimize the maximum completion time for the former. For the latter, the ordering of all workpieces is necessary to define additionally.  
\(j_{i}(i=1,2,\ldots,n)\) indicates the workpieces needed to be worked, in which \(n\) is the total number of workpieces. \(m_{j}(j=1,2,\ldots,S)\) is the number of machines in each stage. \(t_{i,j,l}\) is the machining time of the workpiece \(j_{i}\) at stage \(j\), machine \(l\). \(ct_{j,l+1}(j=1,2,\ldots,S-1)\) is the time cost on the way from  
Figure 1: Flow chart of a typical HFSP.  
stage \(j\) to stage \(j+1(j=1,2,\ldots,S-1)\). \(AT_{i,j,j}\) is the arrival time of workpiece \(J_{i}\) at stage \(j\), machine \(l\). Correspondingly, \(ST_{i,j,l}\) and \(ET_{i,j,l}\) indicate the starting and ending times of workpiece \(J_{i}\) which is machined at stage \(j\), machine \(l\). \(BT_{j,l}\) and \(FT_{j,l}\) reveal the time when the machine \(l\) at stage \(j\) starts to work and stops working. The standard mathematical model of HFSP is as follows:  
\[\text{minmax}\big{\{}ET_{i,j,l}\big{\}}\;i=1,2,\ldots,n;j=S;l=1,2,\ldots,m_{S}, \tag{1}\]  
\[\text{s.t.}\sum_{l=1}^{m_{j}}y_{i,j,l}=1\;i=1,2,\ldots,n;j=1,2,\ldots,S, \tag{2}\]  
where \(y_{i,j,l}=1\) if workpiece \(J_{i}\) is worked at stage \(j\), machine \(l\), else \(y_{i,j,l}=0\)  
\[ST_{i,j,l}=\max\big{\{}AT_{i,j,l},FT_{j,l}\big{\}}\;i=1,2,\ldots,n;j=1,2,\ldots,S;l=1,2,\ldots,m_{j}, \tag{3}\]  
\[ET_{i,j,l}=ST_{i,j,l}+t_{i,j,l}\;i=1,2,\ldots,n;j=1,2,\ldots,S;l=1,2,\ldots,m_ {j}, \tag{4}\]  
\[AT_{i,j+1,l}=ET_{i,j,l}+ct_{j,j+1}\;i=1,2,\ldots,n;j=1,2,\ldots,S-1, \tag{5}\]  
\[BT_{j,l}=ST_{i,j,l}\;j=1,2,\ldots,S;l=1,2,\ldots,m_{j}, \tag{6}\]  
if workpiece \(J_{i}\) is the first one machined at stage \(j\), machine \(l\) and without interruption.  
\[FT_{j,l}=BT_{j,l}+t_{i,j,l}, \tag{7}\]  
if workpiece \(J_{i}\) is worked at stage \(j\), machine \(l\).  
Equation (1) is the objective function, minimizing the maximum ending time of all workpieces in the last stage S. Equation (2) ensures that there is only one workpiece at any machine in any stage. Equation (3) clears the time limitation of arrival and start. Equation (4) shows the relationship between the completion time and the start time of the process at the same stage. Equation (5) calculates the arrival time on the next stage utilizing the end time of the previous stage. Equations (6) and (7) reveal the time when the machine \(l\) at stage \(j\) starts to work and stops working.