Research And Realization Of Job-Shop Scheduling Algorithm Based On ACPM And BFSM

Considering the NP-complete problem, how to get the approximate optimized scheme of Job-Shop scheduling, and aimed at improving the efficiency of products and taking good advantage of concurrence, asynchronism, distributing and juxtaposition in multi-products and devices processing, we could divide the working procedures into the attached one which has the only precursor and subsequence and unattached one by analyzing working flow chart of Job-Shop, that is the working procedures are divided into two types, then the BF and the FF methods about memory scheduling in OS are applied, therefore a new approximate optimized scheme is presented in the paper which could solve the common Job-Shop scheduling. Namely, the ACPM and the BFSM are applied to the classified and grouped working procedures considering the compact of the procedures and practical examples approved it. The results we analyzing and tested show that it is better than the heuristic algorithm common used, for less restriction terms, more satisfying algorithm complexity and better optimized results.When the approximate optimized scheme of common Job-Shop scheduling discussed in the paper is applied to the practice, it could make some parts of working procedures of processing product be the tail end of the tree that working procedures of this product makes, that is, these parts of working procedures still makes a tree like the whole process. During the processing of one product, if another product needed to be processed, we could process it with the mentioned method solving static Job-Shop scheduling. Therefore, a new method to solve dynamic Job-Shop scheduling is put forward and validated by practice.New research ways to solve the common Job-Shop scheduling are presented in the paper, which have important value both in practice and theory.