Abstract: The flexible job shop scheduling problem with random job arrivals is widely encountered in real-world manufacturing environments. Traditional scheduling algorithms often require frequent rescheduling when new jobs arrive, resulting in poor responsiveness and difficulty in satisfying the demands of fast-paced production environments. To address this issue, this paper proposes an efficient job insertion algorithm for handling unexpected job arrivals during the scheduling process. The algorithm constructs a two-dimensional evaluation vector based on minimum scheduling delay and residual scheduling flexibility to jointly assess potential insertion positions for each operation. A non-dominated sorting mechanism is employed to identify a set of promising insertion candidates, which are further evaluated using a tailored evaluation function. During the construction of the insertion plan, an A*-inspired greedy search strategy is adopted, and a backtracking mechanism is subsequently applied to obtain the globally optimal insertion plan. Finally, the proposed algorithm is applied to both the initial scheduling stage and the dynamic rescheduling stage involving randomly arriving jobs. Experimental results demonstrate that the proposed method achieves high scheduling efficiency and stability in both stages, and outperforms benchmark algorithms in terms of makespan and response time.