A Study Of Job-shop Scheduling Problem Based On Ant Colony Optimization And Election Campaign Algorithm And Theirs Comparison

Scheduling technologies in producing process would affect product produce period, product cost and efficiency. Optimizing scheduling problems in produce process could improve the level of management and manufacturing automatization, which would help manufacturing corporations increase the competition power. Job-shop scheduling problem (JSP) was a simplified model of many practical problems. It was also a core problem corporations could be inevitable to face. But the existing scheduling technologies had different kinds of limitations when they were applied to solve JSPs. So, to improve existing scheduling methods or find new scheduling technologies to solve JSPs accurately and quickly would be provided with an important academic value and practical significance.Ant Colony Optimization (ACO) analogized the social behavior of seeking food of ant colonies, which was good for solving combinational optimization problems, such as Traveling Salesman Problem (TSP), but its study in JSP field was few, the optimization result was not very good, and there was not regular rule to be used. Election Campaign Algorithm (ECA) simulated the pursuit of highest support rate in election activities. At present, ECA was almost used in engineering fields.In order to solve JSPs, this paper designed a new pheromone update rule; an improved ECA was designed to explore new scheduling technologies to solve JSPs. And then these two algorithms were compared in many aspects. The conclusions this paper had gotten followed as:Firstly, this paper presented the characters of ACO and JSP separately. Then this paper introduced the ideas and principles of two classic improved ACO, Ant Colony System (ACS) and Max-Min Colony System (MMAS). This paper proposed an improved ACO based on the characters of ACS and MMAS. And then the improved ACO was applied to solve JSPs and more complicated Production Scheduling problems, Flexible Job-shop Scheduling Problems (FJSPs) mentioned in references. The results demonstrated that the improved ACO could improve the quality and efficiency of solutions after compared the results with the solutions that the other heuristic algorithm got.Secondly, this paper introduced the basic idea, principle and compute process about ECA. ECA has been applied to solve practical engineering problems in many fields. But it would be improved to solve discrete problems. This paper expressed the JSP solution based on operation expression method, and generated local voter based on critical path method neighbor search technology, which was the key technology for the design of improved ECA. This paper Applied the improve ECA to solve instances of FT06, LA01, LA03, LA04 and LA05 and LA15. The results showed the improved ECA could get good optimization solutions in less computing time.Thirdly, this paper programmed to complete the scheduling operations for both algorithms using Matlab 7, and then this paper developed a toolbox to solve JSPs.Fourthly, this paper had an analysis by comparing these two improved algorithms in some characters, such as search efficiency, computational complexity.