Abstract: The flexible job shop scheduling problem with random job arrivals is widely encountered in real-world manufacturing environments. Traditional scheduling algorithms often rely on frequent rescheduling when new jobs arrive, resulting in low responsiveness and difficulty in meeting the demands of high-paced production scenarios. To address this issue, this paper proposes an efficient job insertion algorithm specifically designed to handle 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 to guide the selection process, followed by a backtracking mechanism to recover the globally optimal insertion sequence after the search is completed. 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 higher scheduling efficiency and stability in both stages, and outperforms benchmark algorithms in terms of makespan and response time.