## 2 Generate Initial Solutions to PFSP Using a Deep Reinforcement Learning Method  
### The Formulations of PFSP  
The PFSP consists of \(m\) machines \(M=\{M_{1},M_{2},\ldots,M_{m}\}\) and \(n\operatorname{ jobs}J=\{J_{1},J_{2},\ldots,J_{n}\}\). Let \(n\) jobs are to be scheduled on \(m\) machines in the same technological order. The schedule needs to satisfy the following assumptions. The jobs must be processed in the same order on each machine, each job needs to be processed on all machines, a machine can only process one job at a time and a job can be processed only after the release date. Other specific assumptions for the problem can be found in [31] and [32]. The symbols and definitions used to formulate the PFSP as an RL problem are described below. The processing time of the operation on each machine of the job is used as the feature vector of the current job,\(x_{i}=\left\{r_{i},d_{i},o_{i}^{s},o_{i}^{1},..,o_{i}^{m}\right\}\), where \(x_{i}\) is the feature vector of the \(i\)-th job, \(o_{i}^{m}\) is the processing time of the operation of the \(i\)-th job on the \(m\)-th machine, \(o_{i}^{s}=\sum_{k=1}^{m}o_{i}^{k}\), \(r_{i}\), and \(d_{i}\) are the release date and due date of job \(i\), respectively. The late work can be calculated using the following formulas:  
\[C\Big{(}\pi_{(1)},i\Big{)}=r_{\pi_{(1)}}+\sum_{p=1}^{i}o_{\pi_{(1)}}^{p},i=1,2, \ldots,m \tag{1}\]  
\[C\Big{(}\pi_{(k)},0\Big{)}=r_{\pi_{(k)}},k=1,2,\ldots,n \tag{2}\]  
\[C\Big{(}\pi_{(k)},i\Big{)}=max\Big{\{}C\Big{(}\pi_{(k)},i-1\Big{)},C\Big{(}\pi_ {(k-1)},i\Big{)}\Big{\}}+o_{\pi_{(k)}}^{i},k=2,3,\ldots,n;i=1,2,\ldots,m \tag{3}\]  
\[Y_{\pi_{(k)}}=\sum_{p=1}^{m}\min\Big{\{}\max\Big{\{}C\Big{(}\pi_{(k)},m\Big{)} -d_{\pi_{(k)}},0\Big{\}},o_{\pi_{(k)}}^{p}\Big{\}} \tag{4}\]  
\[Object\ function\ :Y=\min\Big{\{}\sum_{k=1}^{n}Y_{\pi_{(k)}}\Big{\}} \tag{5}\]  
where \(\pi=\left\{\pi_{(1)},\ldots,\pi_{(n)}\right\}\) is the scheduling order of jobs, \(C\Big{(}\pi_{(k)},i\Big{)}\) represents the completion time of job \(J_{\pi_{(k)}}\) on machine \(M_{i}\), \(C\Big{(}\pi_{(k)},0\Big{)}\) is the completion time of \(J_{\pi_{(k)}}\) on the virtual machine \(0\), which also represents the release time of the job. Equation (1) constrains the order in which the first job is processed on adjacent machines. Equation (2) indicates that the job can be processed after the release date has arrived. Equation (3) shows the recursive calculation of the completion time. Equation (4) illustrates how the late work is calculated for each operation. The late work means the tasks that have not yet been processed after the dues date has been arrived. The objective function of this problem is \(Y=\min\Big{\{}\sum_{k=1}^{n}Y_{\pi_{(k)}}\Big{\}}\), which means to minimize the total late work of each operation of all jobs. According to the tri-field representation, the problem can be expressed as \(F|r_{i}|Y\)[18]. To illustrate the PFSP and the late work objective function more clearly, Table 1 gives an example of the problem. Figure 1 represents the Gantt chart when the scheduling sequence is 1-2-3, where the shaded part represents the late work after the arrival of the due dates, \(Y_{1}=0\), \(Y_{2}=5\), \(Y_{3}=2\). A total of three operations are delayed, the total late work objective function value is 7. Since the scheduling order of jobs on each machine must be the same in the PFSP, the scheduling results can be abbreviated to a sequence of jobs. A job whose order has been  
\begin{table}
\begin{tabular}{c c c c c c c} \hline \hline
**Job No (i)** & \(r_{i}\) & \(d_{i}\) & \(o_{i}^{s}\) & \(o_{i}^{1}\) & \(o_{i}^{2}\) & \(o_{i}^{3}\) \\ \hline
1 & 0 & 14 & 12 & 3 & 4 & 5 \\
2 & 4 & 12 & 12 & 2 & 6 & 4 \\
3 & 4 & 20 & 12 & 4 & 3 & 5 \\ \hlinedetermined is called a scheduled job, and the job that has not been determined is called unscheduled job. Similar to the traveling salesman problem (TSP), nodes (jobs) that are not scheduled are continually expanded until all nodes (jobs) are expanded.