## 2 Generate Initial Solutions to PFSP Using a Deep Reinforcement Learning Method
### Policy Network Architecture  
The PFSP can be viewed as a sequence-to-sequence problem [33], where the input is a random sequence of all jobs and the output is a well-designed sequence that makes the late work as small as possible, which is similar to the machine translation task, where the input and output are word vectors. The encoder encodes the input sequence into an intermediate vector, then the intermediate vector is decoded multiple times by the decoder to generate the output sequence. Since the encoding and decoding of a sequence need to consider the effect of the order of elements in the sequence, the long short-term memory (LSTM) networks with long and short-term memory are generally used as encoders and decoders. The structure of the encoder-decoder model is shown in Figure 2. In the decoding process, the output of a certain time step may depend on some specific parts of the input sequence rather than the whole input sequence, the attention mechanisms are introduced to learn to find the most valuable parts of the input sequence, which in turn improves the effectiveness of the model. The improved method aggregates the output hidden vector of the decoder of the current time step with the encoder's encoding result of each job using the attention mechanism. The output of the next time step is obtained by weighted aggregation of the encoded vectors of each job.  
Figure 2: The sequence-to-sequence network structure.  
The encoder-decoder network based on the attention mechanism has performed well on the sequence-to-sequence problem. However, directly applying it to solve the PFSP problem suffers from the following two issues.  
1. The output of the PFSP is heavily dependent on the input, the output of each step is one of the inputs, unlike the machine translation problem where the output is a completely different vector from the input.
2. In the PFSP, it is inaccurate to assume that the model input is a sequence of jobs. In fact, the input sequence should have no effect on the output of the model regardless of the order of the jobs in the input. However, the encoder is an LSTM structure, the input jobs are entered and encoded one by one, taking into account unnecessary positional relationships.  
Therefore, this study designed a policy network based on the idea of PtrNet, it turns the weights after the aggregation of the attention mechanism into a probability distribution directly through the softmax layer, the probability distribution points to the elements in the input sequence, which solves the first problem. The network structure of the PtrNet is shown in Figure 3. The network structure is redesigned by combining the graph neural network to solve the second problem mentioned above. The improved network structure is shown in Figure 4, which consists of two encoders (a job encoder and a graph encoder), and a decoder with the attention mechanism. The two encoders are responsible for encoding the input sequence information, converting the input into an intermediate vector form. The intermediate vector is then decoded by the decoder, the output is a probability distribution over the input elements.