Research Of Flow Shop Scheduling Based On Improved Bacteria Foraging Optimization Algorithm

In the21st century, Advanced Manufacturing System(AMS), which combines various techniques, such as management technology, optimization technology, computer technology and automation technology, has become an important production mode and wins more and more attention in modern enterprises. As the core of AMS, production scheduling is the foundation and key point to raise productivity, reduce production cost, and even improve company’s comprehensive competitiveness. Flow-shop scheduling problem(FSP), which is the main type of production scheduling problem, has attracted widespread attentions both in academic circles and engineering field. Relevant data shows that about25%manufacturing systems or assembly lines can reduced to flow-shop problems, hence the FSP has a strong background in engineering application. On the other hand, FSP has been proved to be a NP-hard problem, so the research on its effective algorithm also has the academic value.Based on the work of reviewing various production scheduling methods or algorithms, meanwhile, considered the advantages that Swarm Intelligence Optimization Algorithm had shown when solving complicated combinatorial optimization problem, this paper proposed to apply a new solution named Improved Bacteria Foraging Optimization Algorithm (IBFO) to solve flow-shop scheduling problem. Compared to Bacteria Foraging Optimization Algorithm (BFO),3modifications were added in IBFO:In the chemotaxis process, introduced a crossover operator which acted a role to make individuals in the population to communicate and convey information each others, as a result, the excellent ones wound lead the whole population swam to the optimal area. During the process of reproduction, applied a hybrid strategy based on both health degree and target value of the bacterium, while BFO only considered health degree when copying, this measure can prevent the loss of those individuals with good target value but a bad health degree; And for elimination process, put forward a self-adaption probability instead of a constant data which could reduce the probability of dying of the elite individual.Then aimed at two types of FSP:Permutation Flow-shop Scheduling Problem (PFSP) and No-idle Flow-shop Scheduling Problem (PFSP), and set makespan as optimization target, tested IBFO through calculating typical flow-shop scheduling problems by MATLAB, the results indicated that IBFO is feasible and effective. Further, in order to testing the algorithm’s robustness to initial value, two methods are applied to get the initial bacterium population:random and NEH method, then the data shows IBFO has a good robustness to initial value in the small and medium sized problems.