Abstract: For the permutation Flow Shop scheduling problem,a new algorithm named DRPFSP,which is based on the study of the classic heuristic algorithms,was proposed in this paper.The algorithm normalizes the matrix A of processing times firstly.Secondly,it transforms the original problem containing m machines into a new problem containing 2 machines by introducing a probability matrix P2×m and a corresponding dimension reduction function f_p(A)=PA.Thirdly,it uses the Johnson algorithm to solve the new problem and finds a scheduling sequence π⁰.Finally,it processes π⁰ with the insert neighborhood fast evaluation method to obtain a scheduling scheme π for the original problem.The experiment results show that,compared with the classical heuristic algorithms,DRPFSP algorithm is more effective for the permutation Flow Shop scheduling problem.

Key words: Permutation Flow Shop scheduling problem,Data normalization,Dimensionality reduction