## 2 Generate Initial Solutions to PFSP Using a Deep Reinforcement Learning Method
### Training Method  
The object function of the policy is \(J(\theta\big{|}s)=-\mathbb{E}_{\pi\sim p_{\theta}(\Gamma)}\big{[}L(\pi,S) \big{]}\). Based on the REINFORCE algorithm [39], the gradient of the policy is expressed as:  
\[\
abla_{\theta}J(\theta\mid s)=\mathbb{E}_{\pi\sim p_{\theta}(\cdot\mid s)}[( L(\pi\mid s)-b(s))\
abla_{\theta}logp_{\theta}(\pi\mid s)] \tag{15}\]  
Figure 8: RL learning environment interaction.  
where \(b(s)\) denotes a baseline function that estimates the late work of the expected scheduling sequence to reduce the variance of the gradients. In actual training, based on Monte Carlo sampling [20], the gradient can also be approximated as:  
\[\
abla_{\theta}J(\theta)=\frac{1}{B}\sum_{i=1}^{B}\left[(\sum_{i=1}^{n}r(s_{i,t},a_{i,t})-b_{i})\times(\sum_{i=1}^{n}\
abla_{\theta}logp_{\theta}(a_{i,t}|s_{i, t}))\right] \tag{16}\]  
where \(B\) is the batch size, \(r\) is the reward function, \(b_{i}\) is the baseline for a problem instance in the current batch (late work value obtained by the baseline), \(\sum_{i=1}^{n}r(s_{i,t},a_{i,t})\) is equal to the late work value of the solution, \(p_{\theta}(a_{i,t}|s_{i,t})\) denotes the probability that each action in the action sequence is selected (output by policy network). On the basis of Equation (16), the parameters \(\theta\) can be optimized by gradient descent using the update rule \(\theta\leftarrow\ \theta+\alpha\
abla_{\theta}J(\theta)\).  
The algorithm similar to self-critic [40] is used as the baseline. The main idea is to use the results when the model is tested as the estimated scheduling sequence. Furthermore, during the training phase, samples will be taken from the generated probability distribution. In order to increase the model's exploration ability and avoid falling into the local optimum. The sampling operation allows the model to trade-off between 'exploitation' and 'exploration'. In the testing phase, the action with the highest probability in the probability distribution at each step is selected until the complete scheduling sequence is obtained. It is also possible to sample the probability distribution to search for a better solution, but at the expense of some computational time. The self-critic baseline \(b_{i}\) is expressed as:  
\[b_{i}=\sum_{i=1}^{n}(r(\tilde{s}_{i,t},\tilde{a}_{i,t}))+\left[\frac{1}{B}\sum _{i=1}^{n}\sum_{j=1}^{B}(r(s_{i,t},a_{i,t})-r(\tilde{s}_{i,t},\tilde{a}_{i,t}))\right] \tag{17}\]  
where the action \(\tilde{a}_{i,t}\sim Greedy(p_{\theta})\) is sampled greedily from the policy. The right-hand part of the plus sign of Equation (17) is the gap between the rewards obtained by sampling and greedy. If the sampling result is better than the baseline, the gradient of some of the better actions will increase. Eventually, the probability of a good action being selected will be increased, while the probability of a poor action being selected will be decreased. The final optimization process is shown in Algorithm 1. In order to improve the quality of the solutions obtained by RL, an improved hybrid iterative greedy method is proposed in the next section.  
```
variable declaration: Training set \(T\), training steps \(S\), batch size B, learning rate \(\alpha\)
1. Initialize network parameters \(\theta\)
2.for\(s=1\) to \(S\)do
3.\(x_{i}=Sample(T)\) for \(i\in\{1,\dots,B\}\)
4.\(a_{i,t}=Sample(p_{\theta}(\cdot|\tilde{s}_{i,t}))\)
5.\(\tilde{a}_{i,t}=Greedy(p_{\theta}(\cdot|\tilde{s}_{i,t}))\)
6. Calculate \(J(\theta),\ \
abla_{\theta}J(\theta)\)
7.\(\theta\leftarrow\ \theta+\alpha\
abla_{\theta}J(\theta)\)
8.return\(p_{\theta}\)
```  
**Algorithm 1** Policy Gradient Optimization