Improved Ant Colony Algorithm Research Based On Constraint Satisfaction In Job-shop Scheduling Problem

The problems of research on Scheduling are task time assignment of limited resource, in order to achieve some objective. And scheduling problems in real life are mostly complicated combinatorial optimization problems, such as job-shop scheduling problem (JSP), is the typical NP hard problem, which can't find out the best solution in its complicated polynomial time. As research on JSP has academic and practical significance, it is hot spot all along, and also, aporia. At present the research on JSP is focused on modern intelligent algorithms and their improved hybrid algorithms to get approximation solutions. Integrated with constraint satisfaction, this paper applies the rising ant colony optimization (ACO) algorithm to solve JSP.As its robustness, positive feedback, simultaneousness, ACO algorithm has already obtained promising effect on solving many combinatorial optimization problems, and has high efficiency; but there are defects of slow convergence and easy stagnancy. Fully based on its advantages, the paper revises ACO algorithm of adopting strategy that updates the whole and local pheromone to avoid early stagnancy; for slow convergence, the approach applies constraint satisfaction techniques to reduce the search space, accelerating search rate and enhancing efficiency. And the parameters of ACO algorithm are analyzed in detail as they affect its performance.As a method of solving large combinatorial optimization problems, constraint satisfaction techniques can reduce the search space, so the frequency and time of searching are enormously decreased. Consistency enforcing techniques and constraint propagation techniques can remove the domains of violating constraints dynamically in the course of searching, making that all variables and values aren't searched, just keeping local consistency.The hybrid algorithm takes full advantage of both:constraints satisfaction techniques heighten its efficiency further and the approach finds out the solution and the best scheme faster. The feasibility tests are given in this paper and the standard job shop scheduling instance is simulated, and the result proves that the hybrid algorithm has feasibility and high efficiency, compared with other algorithms. Besides, simultaneous machine scheduling problems are realized as well, which is greatly fit for practical producing.In the end, a job shop scheduling system is exploited using C++Builder and Microsoft SQL Server 2000. It realizes the information management of job shop resources, and the hybrid optimization algorithm for scheduling is integrated into the system.