## 3 ISP-MCTS Algorithm Design
### HFSSP Model  
According to Markov decision processes (MDP), the model of HFSSP is established [40,41]: (1) \(s\) is a series of state matrix of the HFSSP, describing the relationship between the job state and stage. \(s_{1}\) and \(s_{\text{goal}}\) represent the initial state and completion state in the HFSSP. \(s_{1}\), \(s_{2}\),..., \(s_{\text{goal}}\) are used to describe the job production process through various stages. (2) \(a\) is the set of scheduling policies in each state s, the scheduling policy sets \(a_{1}\), \(a_{2}\),..., \(a_{\text{v}}\) are extracted under each state s\({}_{1}\), s\({}_{2}\),..., \(s_{\text{goal}}\). A is the current scheduling policy selected from set \(a\). Therefore, A\({}_{1}\), A\({}_{2}\),..., A\({}_{\text{v}}\) are the policies corresponding to each state of \(s_{1}\) to \(s_{\text{goal}}\), selected from the policy sets of \(a_{1}\), \(a_{2}\),..., \(a_{\text{v}}\). (3) T(s, A, s') = 1, the scheduling policy A is selected, and the probability that the state is converted from s to s' is 1. According to the design methodology of the above MDP model, the relationship between the HFSSP field environment and the model state is established. The matrix model S\({}_{n\times m}\) satisfies the following conditions: (1) \(n\) represents the number of jobs, and \(m\) represents the number of stages. (2) The first column and the \(m\) th column of the matrix are on-line stage and offline stage respectively, the second to the \(m\)-1 th columns represent the processing stages. (3) The number of jobs being processed must be less than or equal to the number of parallel machines in the stage. (4) The job in the same row is processed according to the sequence of stages, so the job in the next column cannot be started until the job in the current column is completed. (5) For any job, there is P\({}_{11}\) = 0, P\({}_{\text{im}}\) = \(\infty\). In Figure 1, S is a \(4\times 4\) state matrix, which is the problem of four jobs and four-stage HFSSP. In this matrix, stage 1 and stage 4 are the online stage and offline stage, respectively, and stage 2 and stage 3 have two parallel processing machines. When the state is searched to the \(k\) th state matrix, the element  
Figure 1: Schematic of the hybrid flow shop scheduling problem (HFSSP) state evolution. \(s_{k(i,j)}=0\) means the job \(i\) is not in the machine of the stage \(j\), and \(s_{k(i,j)}=1\) represents that the job \(i\) is processing in the stage \(j\). \(s_{k(i,j)}=2\) represents that the job \(i\) has finished processing in the \(j\) th stage and waits for scheduling. \(a_{kx}\) represents the scheduling policy set (A\({}_{k1}\), A\({}_{k2}\),... A\({}_{ku}\)) in the \(s_{k}\) state. If the element A\({}_{k1(i,j)}=1\), it represents that the job \(i\) is dispatched from the machine in the stage \(j\) to the processing machine in the stage \(j+1\). As shown in Figure 1, the HFSSP coding model was designed according to the above description. The specific model evolution process is described as follows:  
* Construct the \(n\times m\) matrix of the initial state \(s_{1}\) and the completion state \(s_{\text{goal}}\). In Figure 1, M is 1: the number of parallel machines in each stage, M\({}_{1}\) is the number of idle machines in each stage during the process, and the matrix evolves from \(s_{1}\) to \(s_{\text{goal}}\). * According to the state of the job and the occupancy of the machine, the available scheduling policy
* set has \(a_{k}=(A_{k\gamma}\), A\({}_{k\beta}\),..., A\({}_{k\delta})\) during searching for the \(k\)-floor shop state node \(s_{k}\). Meanwhile, the search method is selected on the basis of the traversal times N(\(s_{k}\)) of the state node \(s_{k}\).