Abstract: Aiming at the scheduling problem of non-close- joining operations in the practical production, a new scheduling strategy is put forward. Through further study of lateness constraints among operations, the concepts of the standard operations, the lateness operations and the expansion processing tree are proposed. A dynamic Job-Shop scheduling algorithm with non-close-joining operations is put forward by improving allied critical path method (ACPM) and best fit scheduling method (BFSM): The lateness operations are scheduled firstly, and the standard operations are scheduled by ACPM and BFSM and are compact on the key machine as soon as possible. The experiment shows that the algorithm not only can solve dynamic Job-shop scheduling problem with non-close-joining operations better but also can be expanded to solve the dynamic Job-shop scheduling problem with close-joining operations.

Key words: Allied critical path method, Expansion processing tree, Job-shop scheduling, Lateness operation, Non-close-joining operation