Research On Job Shop Scheduling Problem Based On Improved Ant Colony Algorithm

Job shop scheduling problem(JSSP)is the simplification of the production scheduling model,the objective is to reach to the best optimum cost point through allocate the factory resources in a right way.Nowadays most factories in China schedule manually by the controller or coordinator,this does make sense when the client is not sensitive on the delivery date and when the scheduling problems are simple.However manual method doesn't work when the scheduling problems become complicated and mass.Most real JSSP are NP-hard problems,so it's hard to find the best solution.This thesis tried to find a new kind of improved ant colony algorithmsolve the JSSP.This thesis summarized the feature of the JSSP and its research status,gave out a detailed briefing on JSSP,then the paper summarized the origin of the ant colony algorithm,introduced the characteristic,mathematical expression and its application.After the basic ant colony algorithm was applied in JSSP,the paper tried to improve the basic ant colony algorithm through 2 methods:generations were presented into the ant colony to overcome the non-convergence of the algorithm,in this way the best pheromone is released to the path which causes a beneficial trend to the new ants.The author used the neighborhood search to avoid the prematurity,the neighborhood search expend the searching space of the ant colony.The improved ant colony algorithm was verified by a benchmark FT06 JSSP.At the meantime the program can output the Gantt chart automatically which can be used in a real workshop.Finally the improved ant colony algorithm was applied in a real scheduling problem and the performance was proved to be pretty good,the improved algorithm shorten the total completion time and improved the machine utilization.The author also gave some suggestions on how to improve management level in this company.