# A Reinforcement Learning Method for a Hybrid Flow-Shop Scheduling Problem
## 1 Introduction  
The traditional flow shop scheduling problem can be described as \(n\) workpieces to be processed on \(m\) machines, each workpiece has to be machined in \(m\) machines, and each machining stage must be worked on different machines. The order of \(n\) workpieces processed on \(m\) machines is the same, and the goal of the problem is to find the machining order of each workpiece on each machine [1]. HFSP is the integration of traditional flow shop scheduling and parallel machine scheduling [2; 3]. With the characteristics of flow shop and parallel machine, HFSP is difficult to solve and even the two-stage HFSP is also an NP-hard (non-deterministic polynomial, NP) problem [4].  
Based on the different type of parallel machines, HFSP can be divided into three categories: the same parallel machine HFSP, the uniform parallel machine HFSP, and the unrelated parallel machine HFSP [5]. In the same parallel machine HFSP, any workpiece has the same processing time on any parallel machine at each stage. The machining time of any workpiece on any parallel machine at each stage is inversely proportional to the processing speed of the machine in the uniform parallel machine HFSP. Explicitly, the working time of any workpiece on two parallel machines at each stage is not correlated with each other in the unrelated parallel machine HFSP, which is the focus of this paper.  
HFSP has a strong engineering background and widely exists in chemical industry, metallurgy, textile, machinery, semiconductor, logistics, construction, papermaking and other fields. The research of HFSP is full of important academic significance and application value, for which HFSP has been widelystudied and applied up to now. To solve the HFSP, exact algorithms [6; 7], heuristic algorithms [8], and intelligent algorithms [9; 10; 11] are mainly taken into account. Though the exact algorithms can get the optimal solution theoretically, its computation time is usually unacceptable, resulting in it only being suitable for solving small-scale HFSP. Heuristic algorithms, which are usually based on specific heuristic rules, can quickly obtain the solution of the problem; it is difficult, however, to guarantee the quality of the solution. In the past few years, an array of intelligent algorithms has been proposed and can be applied to solve HFSP effectively.  
RL is an algorithmic method for solving sequential decision problems where an agent learns through trial and error interacting with its environment. As such, the agent is connected to the environment via perception and action such that the agent seeks to discover a mapping of system states to optimal agent actions. Having been a research hotspot in the field of machine learning in recent years, RL is widely adopted in industrial manufacturing [12], simulation [13], robot control [14], optimization and scheduling [15; 16], game [17; 18] and other fields, and achieves impressive performances.  
Q-Learning [19], one of the most popular algorithms of RL, is used in this paper. In the Q-learning algorithm, the goal is to find a state-action pair value, which represents the long-term expected reward for each pair of state and action. The optimal state-action values for a system, proven to converge to the optimal state-action values, represent the optimal policy that an agent intends to learn.  
To the best of the authors' knowledge, there has not been any reported research focused on HFSP with the RL method before. In this paper, the solution methods of HFSP and RL method are described in detail in the literature review section. The solving model is established in Section 3 and is attributed to the MDP framework in Section 4. In Section 5, the reinforcement learning for HFSP is verified on scheduling in the metal processing workshop of an automobile engine factory. Then, the method is utilized to the sortie scheduling of carrier aircraft in Section 6 and the concluding remarks are contained in the last section.