Study On Job-Shop Scheduling Problems Based On Bacteria Foraging Optimization Algorithm

The job-shop scheduling problem (JSP) is a very hard but important practical problem in both fields of production management and combinatorial optimization. It is a simplified model of many practical production schedule problems. Efficient methods for solving the JSP have significant effects on profitability and product quality. So it attracts great attention from both the academia and industry. Therefore, the study of JSP is of great theoretical and practical importance. In real job shop scheduling scenarios, resource restriction coexists with process restriction, which makes job shop scheduling problems NP-hard. As a result, there is no effective and widely applicable job shop scheduling methods up to the present.The JSP problem can be described by a set of n jobs which is to be processed on a set of m machines. Each job has an engaged technological sequence of machines to be processed. The according operation time and the operation order of each job on each machine have been known. The time required to complete all the jobs is called the makespan. And the objective when solving or optimizing this general problem is to determine the schedule which minimizes the makespan.The Bacteria Foraging Optimization (BFO) described in the paper is a novel evolutionary computation algorithm only proposed several years ago, and it is based on the foraging behavior of E.coli bacteria living in human intestine. Bacteria Foraging Optimization was proposed by Kevin M. Passino in 2002. And the algorithm consists of three kinds of operators: chemotaxis, reproduction and elimination-dispersal. These operators are realized into inter-nested cycles, the outmost is elimination-dispersal operator, the middle is reproduction operator and inmost is chemotaxis operator.The main research work of this paper is to improve BFO, and to apply it into solving JSP. And the work is described as follows:(1) What we should consider mostly is the based restricted condition of JSPwhen doing research with the scheduling algorithms. Reference to JSP, process time and arranged machine of each operation is known, and the process sequence is prohibited to be changed. The ability of the scheduling algorithm to solve JSP has affinity to whether to satisfy the restricted condition.Several improved methods to BFO are proposed in the paper. The process sequence has been fixed before optimizing, so we should pay more attention to make the sequence of jobs more reasonable. Chemotaxis and elimination-dispersal operations have been modified.(2) In this paper two kinds of search operations, individual - based search and swarm - based search, are presented with regards to the important component ( Chemotaxis ) of BFO.Individual-based search refers that individual adjusts its swimming direction according to the history information, which has been selected since the beginning point by itself. Different individual has different information. So the author divide the search into two methods, which are called search based on normal individual and search based on best-so-far individual.The process of search method based on normal individual is: chose a sequence on the current individual called stable section, and then permute the operations in the unstable section. If the new individual is better then the current one, it will place the current individual.And as to the search based on best-so-far individual, it must arrange the sequence of the operations more logically. So the improved search method is to create a new individual according to the sequence of each job in the best-so-far individual.And swarm-based search is elicited by the following foraging process. In one colony, the individual who is in the position near the food will share the information with the others in the same colony. Compare the differences between the selected individual and the best-so-far individual, and then copy a certainsequence of the best-so-far individual into the selected one.By the competition and sharing mechanism among individuals, the computing resource is utilized more efficiently, and prematurity is overcome effectively. These improve the convergence of the hybrid genetic algorithm.(3) As to the standard elimination-dispersal operation, the represented main improving thinking is to let the working procedure with longer waste time processed as soon as possible.The standard elimination-dispersal operation is to produce a new individual randomly. But in this paper, an intelligent method to create a new individual is proposed.(4) Apply the improved BFO to JSP, and simulation results based on some flow shop scheduling benchmarks show that the algorithm is feasible, efficient and superior to the standard BFO. A best or second best solution is obtained by using the proposed hybrid intelligent algorithm.